Implementing a binary insertion sort using binary

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;
    }
}

Answer 1

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);
    }

Answer 2

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.

Answer 3

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();
}

}

Answer 4

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;
    }
}