We start by removing the sixth element from the array. We now compare this with all of the elements to the left to determine where to place it. Every time the value to the left is greater than the item we are trying to place we move that item one space to the right. In this example the value 12 is the lowest element in the array and we end up moving all of the items one slot to the right. This highlights a circumstance that we will have to consider when writing the function to perform insertion sort – if the item is the lowest in the array our technique must stop scanning left when the gap reaches slot 0.
One this pass has finished this dataset is sorted, and control can be returned to the calling function.
Now try the following task. If you have problems completing it, contact your tutor
Write a function called insertsort and add it to the program that you have developed for the previous sections. Use the function to sort the datasets generated by the program, and count how many comparisons and moves insertion sort requires to sort the data sets.
Next: Selection Sort