CODEWITHSUNDEEP
javaarrayssortingbinary-searchinsertion-sort
Gucci Product Wearer
Gucci Product Wearer

Reputation: 11

Insertion Sort with Binary Search?

I cannot find what's wrong with my insertion sort. I need to implement binary search into my sort and it will not work.

public  void insertionSort(String[] data){
    for (int i=1; i<data.length; i++){
        String item = data[i];
        int move = binarySearch(data, item, 0, i - 1);
        for (int j = i; j < move; j++){
            data[j] = data[j-1];
        }
        data[move]= item;
    }
}

public int binarySearch(String[] data, String item, int low, int high) {
    int mid;
    while(low<=high){
        mid=(low+high)/2;
        if(item.compareTo(data[mid]) > 0)
            low=mid+1;
        else if(item.compareTo(data[mid]) < 0)
            high=mid-1;
        else
            return mid;
    }
    return low;
}

Upvotes: 1

Views: 397

Answers (2)

QandA
QandA

Reputation: 11

Well, first off it does not seem useful to have to incorporate binary search into insertion sort. Binary search will simply find the position at which your key is located in your data array. Insertion sort, for data[i], will find the position at which it belongs before the ith index.

In your for-loop for insertion sort, you should be decrementing j instead of incrementing.

Upvotes: 0

Ted Hopp
Ted Hopp

Reputation: 234795

Your insertion loop is wrong. Because move will always be between 0 and i (inclusive), the loop will start out with j >= move so you need to decrement j, not increment it:

for (int j = i; j > move; j--){
    data[j] = data[j-1];
}

Upvotes: 3

Related Questions