CODEWITHSUNDEEP
javabinary-searchinsertion-sort
Ayodeji Marquis
Ayodeji Marquis

Reputation: 41

Insertion sort with binary search not working properly

Here's the code

for(out=1; out< dictSize; out++){
   String temp = dict[out];
   in=out;
   int lowerBound = 0;
   int upperBound = in-1;
   int curIn;  

   while (lowerBound <= upperBound){
      curIn = (lowerBound+upperBound)/2;
      if(dict[curIn].compareTo(temp) > 0){
           dict[in] = dict[curIn]; 
           dict[curIn]=temp;
           upperBound = curIn-1;
       } else{
           if(dict[curIn].compareTo(temp) < 0){
                 lowerBound=curIn + 1;
            }  
       }         
    }
 }

 //status = "sorted";
 for(String v: dict){
      System.out.println(v);
 }

Here's the output which is not arranged properly:

animal

animal

barter

cases

code

dictionary

file

simon

this

crazy

What's wrong, how can I fix it ?

Upvotes: 2

Views: 109

Answers (1)

rsutormin
rsutormin

Reputation: 1649

Since you deal with array rather than linked list then it's not enough to exchange last element with middle one. You have to move whole part of array (for instance using System.arraycopy). So here is my version:

public static void main(String[] args) {
    String[] dict = {"this", "cases", "animal", "barter", "animal",
            "file", "code", "dictionary", "simon", "crazy"};
    for (int out = 1; out < dict.length; out++) {
        String temp = dict[out];
        int indexToInsert = binarySearch(dict, 0, out - 1, temp);
        if (indexToInsert < out) {
            // Next call copies elements [indexToInsert, out-1]
            // to elements [indexToInsert+1, out] (shift to the right)
            System.arraycopy(dict, indexToInsert, dict, 
                    indexToInsert + 1, out - indexToInsert);
            dict[indexToInsert] = temp;
        }
    }

    //status = "sorted";
    for(String v: dict){
        System.out.println(v);
    }
}

public static int binarySearch(String[] dict, int lowerBound, 
        int upperBound, String value) {
    while (lowerBound <= upperBound){
        int curIn = (lowerBound + upperBound)/2;
        int compRes = dict[curIn].compareTo(value);
        // compRes reflects relation between dict[curIn] and value from
        // input parameters. compRes is {-1,0,+1} for cases when
        // dict[curIn] {<,=,>} value correspondingly. For details see: 
        // http://docs.oracle.com/javase/7/docs/api/java/lang/String.html#compareTo(java.lang.String) .
        if (compRes == 0) {
            return curIn;
        } else if (compRes > 0){
            upperBound = curIn - 1;
        } else {
            lowerBound = curIn + 1;
        }
    }
    return lowerBound;
}

Another way is to use standard java implementation of binary search:

public static int binarySearch(String[] dict, int lowerBound, 
        int upperBound, String value) {
    int ret = Arrays.binarySearch(dict, lowerBound, upperBound + 1, value);
    return (ret < 0) ? -ret - 1 : ret;
}

Upvotes: 1

Related Questions