up vote 0 down vote favorite

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

code:

public void insertionSort(){
    int key; 
    int i;   
    for ( int j = 0; 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;
    }
}

This is the result:

jan@janspc:~/Dropbox/programming/java/algorithms$ vim sort.java 
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, 

Executon took: 110628 nano sek?

As you can see from testing. of the 100 int values 99 of them is sorted, whats wrong with my algorithm?

share|improve this question
Note that in the first loop starting with int j = 0 in an imprecision. Think about it.. Also, I would refactor 'j' to 'index' and 'i' to 'previous' – Gevorg Jan 14 '12 at 15:04

6 Answers

up vote 4 down vote accepted

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)

share|improve this answer
up vote 2 down vote

You need >= here:

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

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

share|improve this answer
up vote 0 down vote

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

Best luck...

share|improve this answer
up vote 0 down vote

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;
    }
}
share|improve this answer
up vote 0 down vote

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;
}

~cheers, CM

share|improve this answer
up vote 0 down vote

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 )
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.