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.
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
- Implement the insertion sort using the algorithm above as a guide. Test that it works with an unsorted list
- Add a counter to report how many comparisons have been done during the sorting process.
- Compare the number of comparisons for the insertion sort with the bubble sort