Given a task of implementing insertion sort, many people end up with following code
void insertionSort(int a[]){
for (int i = 0; i < a.length; i++) {
for (int j = i; j > 0; j--) {
int k = j-1;
if( a[j] < a[k]){
int temp = a[j];
a[j] = a[k];
a[k] = temp;
}
}
}
}
Although the code works as expected & sorts the given data in O(n^2) time, but this is the wrong implementation of insertion sort.
Do You Know Why ?
The reason is best case time complexity of insertion sort is O(n) but this code has O(n^2), in short no matter what sequence of data you through at this code it will take O(n^2) time i.e best, avg. & worst case time complexity of this code is O(n^2).Note: If you have clear your "Analysis of Algorithms & Design" paper you will understand what is written above.
If you have understand the above statements than you can fix the wrong implementation on your own, the above implementation can be corrected by just adding one statement which i left it for you as an exercise.
In case you are in hurry you can adopt My way to write insertion sort
Correct Implementation
int[] insertionSort(int [] a ){
for (int j = 1; j < a.length; j++) {
int i = j-1;
while ( ( i >= 0 ) && a[i] > a[i+1] ) {
int k = a[i];
a[i] = a[i+1];
a[i+1] = k;
i -= 1;
}
}
return a;
}
The best case time complexity(i.e when array elements are already in ascending order) of this code is O(n) & worst case time complexity is O(n^2), which proves that this code is correct implementation of Insertion Sort.
