Insertion sort algorithm flaw in Java code
-
28-10-2019 - |
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?
Solution
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)
OTHER TIPS
You need >=
here:
while ( i >= 0 && a[i] > key ){
Without this change it never compares the following elements against the first one.
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;
}
while ( i > 0 && a[i] > key ){
should be while ( i >= 0 && a[i] > key ){
Best luck...
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 )
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/
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();
}
}
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;
}
}
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;
}
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;
}