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.*

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

ReplyDeletedear ayush,

Deletefrom 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.