Insertion sort algorithm flaw in Java code

Question

So I am going through some of the common sorting algorithms and have written this:

Code:

public void insertionSort() {
    int key; 
    int i;   
    for ( int j = 1; j < this.a.length; j++ ) {
        key = a[j];
        i = j;

        while ( i > 0 && a[i-1] > key ) {
            a[i] = a[i-1];
            i = i - 1;
        }
        a[i] = key;
    }
}

Result:

jan@janspc:~/Dropbox/programming/java/algorithms$ javac sort.java
jan@janspc:~/Dropbox/programming/java/algorithms$ java Test 
49, 68, 60, 14, 70, 8, 83, 96, 29, 7, 92, 35, 17, 84, 31, 62, 48, 95, 16, 22, 31, 97, 72, 55, 88, 63, 1, 63, 96, 32, 74, 15, 92, 77, 50, 13, 12, 36, 90, 93, 20, 15, 67, 88, 23, 31, 95, 90, 86, 65, 35, 27, 60, 4, 90, 11, 22, 97, 65, 88, 23, 1, 25, 21, 9, 81, 87, 56, 2, 4, 63, 52, 55, 86, 62, 30, 55, 64, 19, 10, 45, 92, 87, 43, 39, 95, 20, 43, 3, 30, 74, 64, 4, 90, 91, 93, 94, 44, 87, 21, 

49, 1, 1, 2, 3, 4, 4, 4, 7, 8, 9, 10, 11, 12, 13, 14, 15, 15, 16, 17, 19, 20, 20, 21, 21, 22, 22, 23, 23, 25, 27, 29, 30, 30, 31, 31, 31, 32, 35, 35, 36, 39, 43, 43, 44, 45, 48, 50, 52, 55, 55, 55, 56, 60, 60, 62, 62, 63, 63, 63, 64, 64, 65, 65, 67, 68, 70, 72, 74, 74, 77, 81, 83, 84, 86, 86, 87, 87, 87, 88, 88, 88, 90, 90, 90, 90, 91, 92, 92, 92, 93, 93, 94, 95, 95, 95, 96, 96, 97, 97, 

Execution took: 110628 nano sek?

As you can see from testing, the first value is not affected by sort. What's wrong with my algorithm?

Answer 1

In the first iteration, the while loop doesn't execute, because i < 0. In the next iteration, the while loop doesn't run because i == 0.

You should probably use while (i >= 0 && a[i] > key) (not tested though)

Answer 2

You need >= here:

    while ( i >= 0 && a[i] > key ){

Without this change it never compares the following elements against the first one.

Answer 3

Below is the pseudo code of Insertion sort(taken from CLR "Introduction to algorithms" book).

Insertion-Sort(A)

for (j=2 to A.length)

key = A[j]> 
i = j-1
while i>0 && A[i]>key
    A[i+1] = A[i]
    i = i-1
A[i+1] = key

Your code is almost similar to above pseudo code. All you need is to change initialization of int j=0 to int j=1 in for loop:

for ( int j = 1; j < this.a.length; j++ ) {
    key = a[j];
    i = j - 1;

    while ( i > 0 && a[i] > key ) {
        a[i + 1] = a[i];
        i = i - 1;
    }
    a[i+1] = key;
}

Answer 4

while ( i > 0 && a[i] > key ){ should be while ( i >= 0 && a[i] > key ){

Best luck...

Answer 5

In Insertion Sort we need to check each and every element from array and compare with other element getting more accurate result. The problem in your code in while loop we need line

while ( i >= 0 && a[i] > key )

Answer 6

Here is another implementation of insertion sort in java

public class InsertionSort {

static int intArray[] = { 1000, 1, 100, 101, 15 };

public static void doSort() {
    for (int outer = 1; outer < intArray.length; outer++) {
        for(int inner=outer;inner>0; inner--){
            if(intArray[inner]<intArray[inner-1]){
                int temp=intArray[inner];
                intArray[inner]=intArray[inner-1];
                intArray[inner-1]=temp;
                continue;
            }
        }
    }
}

public static void printArray() {
    for (int i = 0; i < intArray.length; i++) {
        System.out.print("  " + intArray[i]);
    }
}

public static void main(String args[]) {
    System.out.print("Array Before Sorting->");
    printArray();
    doSort();
    System.out.print("\nArray After Sorting ->");
    printArray();
}

}

Detailed explanation of the code and/or the algortithm can be seen at - http://www.javabrahman.com/algorithms-in-java/insertion-sort-in-java/

Answer 7

here is a very easy implementation of insertion sort

package insertion_sort;

public class insertion_sort {
    public static void main(String ar[]) {
        int[] a = {24, 13, 9, 64, 7, 23, 34, 47, 87, 9, 37, 1992};
        insertion(a,12);
    }

    public static void insertion(int[] a, int n) {
        for (int i = 1; i <= n - 1; i++) {
            int value = a[i];
            int hole = i;
            while (hole > 0 && a[hole - 1] > value) {
                a[hole] = a[hole - 1];
                hole = hole - 1;    
            }
            a[hole] = value;
        }
        print(a);    
    }

    public static void print(int[] A) {    
        for (int i = 0; i < A.length; i++) {    
            System.out.print(A[i] + " ");    
        }    
        System.out.println();
    }    
}

Answer 8

Corrected code:

public void insertionSort() {
    int key; 
    int i;   
    for ( int j = 1; j < this.a.length; j++ ) {
        key = a[j];
        i = j;

        while ( i > 0 && a[i-1] > key ) {
            a[i] = a[i-1];
            i = i - 1;
        }
        a[i] = key;
    }
}

Answer 9

public static int[] insrtSort(int array[]){

    for(int i=0 ; i<array.length-1;i++){
        int value=array[i+1],k=i;

        while(value<array[k] ){

            array[k+1]=array[k];
            if(k!=0)
            k--;
            else
                array[0]=value;
        }
        if(k!=0)
        array[k+1]=value;
    }
    return array;
    }

Answer 10

This is the same code but as a method that can be passed an array of ints to sort.

public static int[] insertionSort(int[] array) {
    int key; 
    int i;   


    for ( int j = 1; j < array.length; j++ ) {
        key = array[j];
        i = j;

        while ( i > 0 && array[i-1] < key ) {
            array[i] = array[i-1];
            i = i - 1;
        }
        array[i] = key;
    }
    return array;
}