Insertion sort

Insertion sort

This is an in-place comparison-based sorting algorithm. Here, a sub-list is maintained which is always sorted. For example, the lower part of an array is maintained to be sorted. An element which is to be 'insert'ed in this sorted sub-list, find its appropriate place and then it has to be inserted there.

How Insertion sort works ?

14    33    27    10    35    19    42    44

Insertion sort compares the first two elements.

14    33    27    10    35    19    42    44

It finds that both 14 and 33 are already in ascending order. For now, 14 is in sorted sub-list.

14    33    27    10    35    19    42    44

Insertion sort moves ahead and compares 33 with 27.

14    33    27    10    35    19    42    44

finds that 33 is not in the correct position.

14    33    27    10    35    19    42    44

It swaps 33 with 27. It also checks with all the elements of sorted sub-list. Here we see that the sorted sub-list has only one element 14, and 27 is greater than 14. Hence, the sorted sub-list remains sorted after swapping.

14    27    33    10    35    19    42    44

By now we have 14 and 27 in the sorted sub-list. Next, it compares 33 with 10.

14    27    33    10    35    19    42    44

These values are not in a sorted order,swapped it.

14    27    10    33    35    19    42    44

However, swapping makes 27 and 10 unsorted,swapped again.

14    10    27    33    35    19    42    44

We find 14 and 10 are in the worng order,swapped it.

10    14    27    33    35    19    42    44

After the last swapped ,every number is in the right order.

10    14    19    27    33    35    42    44

Algorithm

Step 1 − If it is the first element, it is already sorted. return 1;

Step 2 − Pick next element

Step 3 − Compare with all elements in the sorted sub-list

Step 4 − Shift all the elements in the sorted sub-list that is greater than the  value to be sorted

Step 5 − Insert the value

Step 6 − Repeat until list is sorted

Pseudocode

procedure insertionSort( A : array of items )

   int holePosition

   int valueToInsert

               for i = 1 to length(A) inclusive do:  /* select value to be inserted */

      valueToInsert = A[i]

      holePosition = i  /*locate hole position for the element to be inserted */

 while holePosition > 0 and A[holePosition-1] > valueToInsert do:

         A[holePosition] = A[holePosition-1]

         holePosition = holePosition -1

      end while /* insert the number at hole position */

      A[holePosition] = valueToInsert

       end for

end procedure