Saturday 19 January 2013

Correct Implementation of Insertion Sort

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.

2 comments:

  1. how much time difference will be there in O(n) and O(n^2) ?? what are these terms??

    ReplyDelete
    Replies
    1. dear ayush,

      from your website it looks like you are in high school & to understand this things you have to wait & study hard for atleast 3 yrs. from now.

      So looking at your level i will not go into much technical details, but simply just understand this ...let n = 10 then n^2 = 100 looking at this numbers you can say that a algorithm whose complexity is O(n) ( forget about 'O' for time being ) runs faster than algorithm whose complexity is O(n^2).

      This concepts are far much difficult to understand so keep patience.

      Delete