Insertion Sort (Cambridge (CIE) A Level Computer Science): Revision Note

Insertion sort

What is an insertion sort?

• In A Level Computer Science, the insertion sort sorts one item at a time by placing it in the correct position of an unsorted list

• This process repeats until all items are in the correct position

• Specifically, the current item being sorted is compared to each previous item

• If it is smaller than the previous item then the previous item is moved to the right and the current item takes its place

• If the current item is larger than the previous item then it is in the correct position and the next current item is then sorted as illustrated below

Performing the insertion sort

Figure 2: Performing the Insertion sort

Time complexity of an insertion sort

• In the above algorithm, one statement is present, a for loop with three statements and a nested while loop that contains two statements

• The time complexity for the insertion sort would be 3n*2n + 1, giving 6n² + 1. 3n comes from the for loop having three statements inside it, not including the while. 2n comes from the while loop having two statements inside it

• Removing coefficients and dominated factors leaves O(n²) as the worst case scenario

• The best case scenario would be an already sorted list which means each item is checked one at a time giving a time complexity of O(n)

The average case scenario would be a half sorted list giving O(n²/2), which when coefficients are removed still gives O(n²)

Space complexity of an insertion sort

• As the insertion sort requires no additional space, it is space complexity O(1)

Tracing an insertion sort

• Tracing through the insertion sort involves starting at element 1 (not 0)

• i increments through each element one at a time and each item is compared to the one previous. If the previous item is bigger or equal it is set to list[position]

• If position equals 0 then the iteration is at the start of the list and the next iteration begins

Trace Table of the Insertion sort

Implementing an insertion sort

Pseudocode

PROCEDURE insertionSort(list : ARRAY OF INTEGER)
    DECLARE n, i, position : INTEGER
    DECLARE item : INTEGER

    n ← LENGTH(list)

    FOR i ← 1 TO n - 1
        item ← list[i]
        position ← i

        WHILE position > 0 AND list[position - 1] > item
            list[position] ← list[position - 1]
            position ← position - 1
        ENDWHILE

        list[position] ← item
    NEXT i
ENDPROCEDURE

DECLARE list : ARRAY[0:8] OF INTEGER
list ← [5, 9, 4, 2, 7, 1, 2, 4, 3]

CALL insertionSort(list)

OUTPUT list

• Procedure definition:
  insertionSort takes an array called list and sorts it in ascending order

• Initialisation:

  • n ← LENGTH(list) stores the number of items

  • The sort begins from index 1 because the first item (index 0) is considered sorted

• Outer FOR loop (i ← 1 TO n - 1):

  • Each iteration picks the next item in the list to be inserted into the correct position in the sorted portion to its left

• Store the current item:

  • item ← list[i] stores the current value to be positioned

  • position ← i is used to track where item should go

• Inner WHILE loop:

  • Shifts elements in the sorted portion to the right while they are greater than item

  • Stops when either:

    • The start of the list is reached (position = 0)

    • Or the correct spot is found (list[position - 1] <= item)

• Insert the item:

  • list[position] ← item inserts the value in the correct position

• Repeat:

  • The next item is considered, and the process repeats until the entire list is sorted

• After sorting:

  • OUTPUT list displays the sorted array

Python

def insertion_sort(data):
     for i in range(1, len(data)):
        item = data[i]
        position = i
        while position > 0 and data[position - 1] > item:
            data[position] = data[position - 1]
            position -= 1
        data[position] = item
    return data

Java

public class InsertionSort {

    public static void insertionSort(int[] data) {
        for (int i = 1; i < data.length; i++) {
            int item = data[i];
            int position = i;
            while (position > 0 && data[position - 1] > item) {
                data[position] = data[position - 1];
                position--;
            }
            data[position] = item;
        }
    }