Insertion Sort

Insertion sort maintains a sub-list which is always sorted. The array is searched sequentially and unsorted items are moved and inserted into the sorted sub list.

The lower part of an array is maintained to be sorted. An element which is to be inserted in this sorted sub list has to find its appropriate place and then it has to be inserted there.

This algorithm is not suitable for large data sets as its average and worst case complexity are of O(n²).

Ex:

14        33        27        10        35        19        42        44

Insertion sort compares first two elements. Here both are already in ascending order. now 14 is in sorted sub list.

14        33        27        10        35        19        42        44

Insertion sort now compares 33 with 27 and finds 33 is not in correct position. It swaps 33 with 27.

14        27        33        10        35        19        42        44

It also checks all elements in sub list of sorted order. Here sub list is sorted.

Similarly 10 compared with 33

14        27        10        33        35        19        42        44

14        10        27        33        35        19        42        44

10        14        27        33        35        19        42        44

 

comparing 33 and 35, they are in order

10        14        27        33        35        19        42        44

compare 35 with 19, they are not in order, a swap is performed

10        14        27        33        19        35        42        44

Now sublist is sorted

10        14        19        27        33        35        42        44

This process is continued until all unsorted values are placed in the sorted sub list.

 

Insertion sort function code:

void InsertionSort(int A[], int n)

{

int i, j, element;

for(i = 1; i < n; i++)

{

element = A[i];

// insert ith element in 0 to i − 1 array

j = i;

while((j > 0) && (A[j − 1] > element))

//compare if A[j − 1] > element

{

A[j] = A[j − 1]; // shift elements

j = j − 1;

}

A[j] = element; // place element at jth position

}

}