What is Wrong with my Binary Insertion Code?

Question

I am a beginner in Java trying to create a class that implements the binary insertion sort and sorts out random arrays of the data sizes 50, 500, 5000, 50000, and 500000.

The program works fine when I implemented it as an insertion sort.

public double InsertionSort(long array[]) {
            setType("Insertion Sort");
            long temp;
            int y;
            double numOfSwap = 0, numOfComparisons = 0;
            double startTime = System.nanoTime();
            for (int x = 1; x < array.length; x++) {
                temp = array[x];
                numOfSwap++;
                y = x;
                numOfComparisons++;
                while ((y > 0)) {
                    numOfComparisons++;
                    if ((array[y - 1]) > temp) {
                        array[y] = array[y - 1];
                        numOfSwap++;
                        y = y - 1;
                    } else
                        break;
                }
                array[y] = temp;
                numOfSwap++;
            }
            double endTime = System.nanoTime();
            setSwap(numOfSwap / 3);
            setComparisons(numOfComparisons);
            setTime(endTime - startTime);
            return getTime();

        }

But when I tried to insert a binary search, it did not work anymore.

 public double binaryInsertionSort(long array[], int value, int left, int right) {
            setType("Binary Insertion Sort");
            long temp;
            int y;
            int left, right;
            double numOfSwap = 0, numOfComparisons = 0;
            double startTime = System.nanoTime();
            for (int x = 1; x < array.length; x++) {
                temp = array[x];
                numOfSwqp++;
                int left = y;
                int right = x;
                if (left>right)
                    return -1;
                int middle = (left + right)/2;
                if (array[middle] == value)
                    return middle;
                numOfComparisons++;
                else if (array[middle]>value)
                    return binaryInsertionSort(array, value,left, middle -1);
                numOfComparisons++;
                else
                    return binaryInsertionSort (array, value, middle +1, right);
                numOfComparisons++;
            }
            double endTime = System.nanoTime();
            setSwap(numOfSwap / 3);
            setComparisons(numOfComparisons);
            setTime(endTime - startTime);
            return getTime();
        }

Can someone please help me fix my code?

Answer 1

There were mistakes in your code. I corrected them. First of all your left and right variables are defined in this line :-

public double binaryInsertionSort(long array[], int value, int left, int right)

why are you again defining them inside method body. So I removed their double declaration. Second you assigned value of left variable to y which was wrong. Actually you have to assign value of y toleft. Third error in your code was your method calls were wrong. You defined binaryInsertionSort with four parameters and you were calling it by single parameter so I modified your method calls like this:-

sortTime = binaryInsertionSort(sortedArray,10,20,30);

Rest were minor mistakes. Here is corect code of your `binaryInsertionSort method :-

public double binaryInsertionSort(long array[], int value, int left, int right) {

setType("Binary Insertion Sort");

long temp;

int y=0;

//int left, right;

double numOfSwap = 0, numOfComparisons = 0;

double startTime = System.nanoTime();

for (int x = 1; x < array.length; x++) {

temp = array[x];

numOfSwap++;

y=left;

right = x;

if (left>right){
return -1;
}

int middle = (left + right)/2;

if (array[middle] == value){

    numOfComparisons++;
    return middle;

} else if (array[middle]>value){

    numOfComparisons++;
    return binaryInsertionSort(array, value,left, middle -1);

} else{

    numOfComparisons++;    
    return binaryInsertionSort (array, value, middle +1, right);
    }

}

double endTime = System.nanoTime();

setSwap(numOfSwap / 3);

setComparisons(numOfComparisons);

setTime(endTime - startTime);

return getTime();

}
`

I mailed you complete corrected code of your program. Check your mail box. Acknowledge me whether you find my answer useful or not. Happy Coding :)