Tutorial 6

📥

Insertion Sort

9618 A-Level

i

It may be useful to search (CTRL + F) for "insertion sort" questions in the (combined) past papers

If you find any bugs/edge cases in this code, please contact me

1

Insertion Sort

For IGCSE/O-Level/AS, you should be familiar with bubble sort along with its two optimisations

Both sorting algorithms have a time complexity of O(n2) - e.g. in the worst case, if we have an array of 10 elements, we might have to do approximately 100 comparisons, if we have 1 million elements, we might have to do 1 trillion comparisons etc

There are more efficient sorting algorithms available (good video comparing their performance), however these are either too difficult/time-consuming to code for an A-Level exam and/or require significant additional memory - bubble sort and insertion sort are both "in place" sorting algorithms, meaning they don't require additional data structures/copies of the data to function

Let's see how insertion sort works:

  1. Start at n + 1 (e.g. the 2nd element on the first loop) and copy it to a temporary variable
  2. If the previous value (n) is greater than the temp variable, then shift it one position right in the array
  3. Continue shifting elements right until you find an element smaller than the temp variable
  4. "Drop" the temp variable at this index location
  5. Increment from n and repeat from step 1 - do this for all remaining indexes of n

This .gif from Wikipedia shows the algorithm visually:

More detailed comments can be seen in the code

DECLARE nums : ARRAY[1:9] OF INTEGER DECLARE start, temp, index : INTEGER nums ← [7, 4, 2, 6, 1, 8, 5, 3, 9] FOR start ← 2 TO LENGTH(nums) OUTPUT "--- Start ", start, " ---" temp ← nums[start] //store current element index ← start - 1 //compare with previous //while valid index and current element is bigeger than temp WHILE index > 0 AND nums[index] > temp DO OUTPUT "Temp: ", temp, " | Shift ", nums[index], " right" nums[index + 1] ← nums[index] //shift element right index ← index - 1 //go to previous index ENDWHILE nums[index + 1] ← temp //needs +1 since our index points to the previous element, not the position we want to insert NEXT start OUTPUT "--- Sorted Array ---" FOR index ← 1 TO LENGTH(nums) OUTPUT nums[index] NEXT index

Extension details/answers will be added: compare with bubble sort - try with completely random arrays, nearly sorted, completely unsorted (e.g. reverse order) - which algorithm generally performs less comparisons?