Binary search and insertion sort

Question

My insertInOrder method is wrong(it prints the list of numbers backwards). I am reading in a list of numbers, and I want to use the insertion sort algorithm to sort the numbers in ascending order using the index position of the binary search. I am not really sure how to go about this and help would be very much appreciated.

static void insertInOrder( int[] arr, int cnt, int newVal ) {

    int index = bSearch( arr, 0, arr.length-1, newVal) ;
    if (index < 0) {
        index  = -1 - index ;
    }
    for ( int i = cnt; i >= index+1 ; --i) {
       arr[i] = arr[i-1];
    }

    arr[index] = newVal;
}


public static int bSearch(int[] a, int lo, int hi, int key) {
    int mid = (lo+hi)/2;
    if(lo>hi)
        return -1;
    else if (a[mid]==key)
        return mid;
    else if (a[mid]<key)
        return bSearch(a, mid+1, hi, key);
    else
        return bSearch(a, lo, mid-1, key);
}

Reading in: 5 13 7 9 21
Current Output: 21 9 7 13 5
Desired Output: 5 7 9 13 21

This is insertInOrder in my main

    int[] arr = new int[INITIAL_CAP];
    int arrCnt= 0;
    while (infile.hasNextInt())
    {
        if ( arrCnt==arr.length )
            arr = doubleMyLength(arr);
        insertInOrder( arr, arrCnt, infile.nextInt() );
        ++arrCnt;
    }
    infile.close();

    arr = trimMyLength( arr, arrCnt );
    System.out.println("Sorted array of " + arr.length + " ints from " + args[0] + " after insert in order:" );
    printArray( arr );  // we trimmed it so count == length so we don't bother to pass in count

Please show some examples of how `insertInOrder(i[],i,i)` is being called. — aliteralmind, Mar 01 '14 at 02:17
I am reading in the numbers in one by one, but I want to use the binary search to find the insertion index for the next incoming number — user3287300, Mar 01 '14 at 02:20
A bubble sort is for sorting an array as it's being populated. Every item bubbles to its correct position. Elements constantly change position (swap with their neighbor) until the last item is inserted. — aliteralmind, Mar 01 '14 at 02:21
I assume you are required to use an array, but you would be better served with a HashSet (if there will be no duplicates), or an ArrayList (if there may be duplicates). After all values are inserted, just convert it to an array. http://stackoverflow.com/a/21974362/2736496 — aliteralmind, Mar 01 '14 at 02:26
There are no duplicates, it is just the sorting that is tripping me up. — user3287300, Mar 01 '14 at 02:27

score 0 · Answer 1 · answered Mar 01 '14 at 02:24

0

When newVal is not found in the array (which is pretty likely to happen), your bSearch() returns -1. Then, insertInOrder() always insert the item to position index = -1 - index, which is 0. That's why the result is wrong.

To get it correct, your bSearch() need to return the smallest index in which the value is greater than newVal.

answered Mar 01 '14 at 02:24

timrau

22,578
4
51
64

@user3287300 What's your test result then? – timrau Mar 01 '14 at 02:41

score 0 · Answer 2 · answered Mar 01 '14 at 02:39

There are two problems in your code. One, as @timrau indicated, is that you return the wrong value -1 from the binary search method if the entry isn't found. You should return -lo - 1. (It's the point where you should insert the value - returning a negative value is used to indicate that the value wasn't found in the binary search. But in your case, you don't care about getting duplicates in the sorted list, so you could just as well return lo directly.)

Second, you pass the wrong array length to your binary search method. It should be cnt - 1 rather than arr.length - 1.

The code becomes:

static void insertInOrder(int[] arr, int cnt, int newVal) {
    int index = bSearch(arr, 0, cnt - 1, newVal);
    if (index < 0) {
        index = -1 - index;
    }
    for (int i = cnt; i >= index + 1; --i) {
        arr[i] = arr[i - 1];
    }

    arr[index] = newVal;
}

public static int bSearch(int[] a, int lo, int hi, int key) {
    int mid = (lo + hi) / 2;
    if (lo > hi)
        return -lo - 1;
    else if (a[mid] == key)
        return mid;
    else if (a[mid] < key)
        return bSearch(a, mid + 1, hi, key);
    else
        return bSearch(a, lo, mid - 1, key);
}

Binary search and insertion sort

2 Answers2