Insertion Sort

 Insertion Sort InsertionSort(A, n)
{
for i = 2 to n
  {
key = a[i]                  //next key
j=i--                         // go left
while (j > 0) and (A[j] > key)
{                               //find place for key


     A[j+1] = A[j]      //shift sorted right
     j = j – 1              //go left
}
a[j+1] = key            // put key in place

}
}

   
Example:

Insertion sort compares the first two elements.

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

Insertion sort moves ahead and compares 33 with 27.

And finds that 33 is not in correct position.

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

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

These values are not in sorted order.

So we swap them.

But swapping makes 27 and 10 unsorted.

So we swap them too.

Again we find 14 and 10 in unsorted order.

And we swap them. By the end of third iteration we have a sorted sublist of 4 items.

This process goes until all the unsorted values are covered in sorted sublist. And now we shall see some programming aspects of insertion sort.

Bubble Sort:

Example:

- First Pass:
( 5 1 4 2 8 ) ( 1 5 4 2 8 ), Here, algorithm compares the first two elements, and swaps them.
( 1 5 4 2 8 ) ( 1 4 5 2 8 ), Swap since 5 > 4
( 1 4 5 2 8 ) ( 1 4 2 5 8 ), Swap since 5 > 2
( 1 4 2 5 8 ) ( 1 4 2 5 8 ), Now, since these elements are already in order (8 > 5), algorithm does not swap them.
– Second Pass:
( 1 4 2 5 8 ) ( 1 4 2 5 8 )
( 1 4 2 5 8 ) ( 1 2 4 5 8 ), Swap since 4 > 2
( 1 2 4 5 8 ) ( 1 2 4 5 8 )
( 1 2 4 5 8 ) ( 1 2 4 5 8 )
Now, the array is already sorted, but our algorithm does not know if it is completed. The algorithm needs one whole pass without any swap to know it is sorted.
Third Pass:
( 1 2 4 5 8 ) ( 1 2 4 5 8 )
( 1 2 4 5 8 ) ( 1 2 4 5 8 )
( 1 2 4 5 8 ) ( 1 2 4 5 8 )
( 1 2 4 5 8 ) ( 1 2 4 5 8 )
Finally, the array is sorted, and the algorithm can terminate.