Implementing a binary insertion sort using binary search in Java

Question

I'm having trouble combining these two algorithms together. I've been asked to modify Binary Search to return the index that an element should be inserted into an array. I've been then asked to implement a Binary Insertion Sort that uses my Binary Search to sort an array of randomly generated ints.

My Binary Search works the way it's supposed to, returning the correct index whenever I test it alone. I wrote out Binary Insertion Sort to get a feel for how it works, and got that to work as well. As soon as I combine the two together, it breaks. I know I'm implementing them incorrectly together, but I'm not sure where my problem lays.

Here's what I've got:

public class Assignment3
{
    public static void main(String[] args)
    {   
        int[] binary = { 1, 7, 4, 9, 10, 2, 6, 12, 3, 8, 5 };

        ModifiedBinaryInsertionSort(binary);

    }

    static int ModifiedBinarySearch(int[] theArray, int theElement)
    {
        int leftIndex = 0;
        int rightIndex = theArray.length - 1;
        int middleIndex = 0;

        while(leftIndex <= rightIndex)
        {
            middleIndex = (leftIndex + rightIndex) / 2;

            if (theElement == theArray[middleIndex])
                return middleIndex;
            else if (theElement < theArray[middleIndex])
                rightIndex = middleIndex - 1;
            else
                leftIndex = middleIndex + 1;
        }

        return middleIndex - 1;
    }

    static void ModifiedBinaryInsertionSort(int[] theArray)
    {
        int i = 0;
        int[] returnArray = new int[theArray.length + 1];

        for(i = 0; i < theArray.length; i++)
        {
            returnArray[ModifiedBinarySearch(theArray, theArray[i])] = theArray[i];
        }

        for(i = 0; i < theArray.length; i++)
        {
            System.out.print(returnArray[i] + " ");
        }
    }
}

The return value I get for this when I run it is 1 0 0 0 0 2 0 0 3 5 12. Any suggestions?

UPDATE: updated ModifiedBinaryInsertionSort

static void ModifiedBinaryInsertionSort(int[] theArray)
{
    int index = 0;
    int element = 0;
    int[] returnArray = new int[theArray.length];

    for (int i = 1; i < theArray.lenght - 1; i++)
    {
        element = theArray[i];
        index = ModifiedBinarySearch(theArray, 0, i, element);
        returnArray[i] = element;

        while (index >= 0 && theArray[index] > element)
        {
            theArray[index + 1] = theArray[index];
            index = index - 1;
        }
        returnArray[index + 1] = element;
    }
}

Stephane B. · Accepted Answer · 2017-04-10 08:24:57Z

2

Here is my method to sort an array of integers using binary search. It modifies the array that is passed as argument.

public static void binaryInsertionSort(int[] a) {
    if (a.length < 2)
        return;
    for (int i = 1; i < a.length; i++) {
        int lowIndex = 0;
        int highIndex = i;
        int b = a[i];

        //while loop for binary search
        while(lowIndex < highIndex) {
            int middle = lowIndex + (highIndex - lowIndex)/2; //avoid int overflow
            if (b >= a[middle]) {
                lowIndex = middle+1;
            }
            else {
                highIndex = middle;
            }
        }
        //replace elements of array
        System.arraycopy(a, lowIndex, a, lowIndex+1, i-lowIndex);
        a[lowIndex] = b;
    }
}

answered Apr 10, 2017 at 8:24

Stephane B.

5827 silver badges20 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Patashu · Accepted Answer · 2013-06-06 02:59:28Z

1

How an insertion sort works is, it creates a new empty array B and, for each element in the unsorted array A, it binary searches into the section of B that has been built so far (From left to right), shifts all elements to the right of the location in B it choose one right and inserts the element in. So you are building up an at-all-times sorted array in B until it is the full size of B and contains everything in A.

Two things:

One, the binary search should be able to take an int startOfArray and an int endOfArray, and it will only binary search between those two points. This allows you to make it consider only the part of array B that is actually the sorted array.

Two, before inserting, you must move all elements one to the right before inserting into the gap you've made.

answered Jun 6, 2013 at 2:59

Patashu

21.8k4 gold badges49 silver badges53 bronze badges

4 Comments

MacSalty Over a year ago

This helped me figure out one of my major problems. I didn't use the proper Binary Insertion Sort algorithm for this. Now I just have to figure out where to plug in my binary search into it and I should be good to go. Thank you.

beaker Over a year ago

@Anonymity Could you post your updated code? You should be performing your binary search on returnArray, i.e. ModifiedBinarySearch(returnArray, startOfArray, endOfArray, theArray[i]) (including Patashu's suggested update).

MacSalty Over a year ago

@Beaker posted. It still doesn't work however, so I'm going to see what I can do today.

Saicharan S M Over a year ago

You are not modifying the returnArray. You are moving the elements in the theArray after the index has been found. Same should be done for returnArray as well.

Taekahn · Accepted Answer · 2014-10-22 01:21:33Z

I realize this is old, but the answer to the question is that, perhaps a little unintuitively, "Middleindex - 1" will not be your insertion index in all cases. If you run through a few cases on paper the problem should become apparent.

I have an extension method that solves this problem. To apply it to your situation, you would iterate through the existing list, inserting into an empty starting list.

public static void BinaryInsert<TItem, TKey>(this IList<TItem> list, TItem item, Func<TItem, TKey> sortfFunc)
        where TKey : IComparable
    {
        if (list == null)
            throw new ArgumentNullException("list");

        int min = 0;
        int max = list.Count - 1;
        int index = 0;

        TKey insertKey = sortfFunc(item);

        while (min <= max)
        {
            index = (max + min) >> 1;

            TItem value = list[index];
            TKey compKey = sortfFunc(value);
            int result = compKey.CompareTo(insertKey);

            if (result == 0)
                break;
            if (result > 0)
                max = index - 1;
            else
                min = index + 1;
        }

        if (index <= 0)
            index = 0;
        else if (index >= list.Count)
            index = list.Count;
        else
            if (sortfFunc(list[index]).CompareTo(insertKey) < 0)
                ++index;

        list.Insert(index, item);
    }

user4398985 · Accepted Answer · 2015-04-12 01:07:06Z

Dude, I think you have some serious problem with your code. Unfortunately, you are missing the fruit (logic) of this algorithm. Your divine goal here is to get the index first, insertion is a cake walk, but index needs some sweat. Please don't see this algorithm unless you gave your best and desperate for it. Never give up, you already know the logic, your goal is to find it in you. Please let me know for any mistakes, discrepancies etc. Happy coding!!

public class Insertion {
private int[] a;
int n;
int c;

public Insertion()
{
    a = new int[10];
    n=0;
}

int find(int key)
{
    int lowerbound = 0;
    int upperbound = n-1;

    while(true)
    {
        c = (lowerbound + upperbound)/2;
        if(n==0)
            return 0;
        if(lowerbound>=upperbound)
        {
            if(a[c]<key)
                return c++;
            else
                return c;
        }
        if(a[c]>key && a[c-1]<key)
            return c;
        else if (a[c]<key && a[c+1]>key)
            return c++;
        else
        {
            if(a[c]>key)
                upperbound = c-1;
            else
                lowerbound = c+1;
        }
    }
}

void insert(int key)
{
   find(key);
   for(int k=n;k>c;k--)
   {
       a[k]=a[k-1];
   }
   a[c]=key;
   n++;
}
void display()
{
    for(int i=0;i<10;i++)
    {
        System.out.println(a[i]);
    }
}

public static void main(String[] args)
{
    Insertion i=new Insertion();
    i.insert(56);
    i.insert(1);
    i.insert(78);
    i.insert(3);
    i.insert(4);
    i.insert(200);
    i.insert(6);
    i.insert(7);
    i.insert(1000);
    i.insert(9);
    i.display();
}

}

Collectives™ on Stack Overflow

Implementing a binary insertion sort using binary search in Java

4 Answers 4

Comments

4 Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

Comments

4 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related