Insertion Sort

The insertion sort uses the principle of a marker moving along a list with a sorted side to the left side of the marker and the unsorted side to the right of the marker.

Insertion sort

The list of steps is as follows:

This video tutorial from Virginia Tech shows this being demonstrated using a set of cards.

Here is the algorithm for the insertion sort:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
Procedure InsertionSort (List, First, Last)
    For CurrentPointer <- First + 1 To Last
        CurrentValue <- List[CurrentPointer]
        Pointer <- CurrentPointer − 1
        While List[Pointer] > CurrentValue AND Pointer > 0
            List[Pointer+1] <- List[Pointer]
            Pointer <- Pointer − 1
        EndWhile
        List[Pointer+1] <- CurrentValue
    EndFor
EndProcedure

Exercises

  1. Implement the insertion sort using the algorithm above as a guide. Test that it works with an unsorted list
  2. Add a counter to report how many comparisons have been done during the sorting process.
  3. Compare the number of comparisons for the insertion sort with the bubble sort