Insertion Sort (OCR A Level Computer Science)

Insertion sort

What is an Insertion Sort?

• 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(n), where n is the number of items in the list

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 insertsionSort(list)
	n = len(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

list = [5, 9, 4, 2, 7, 1, 2, 4, 3]
insertionSort(list)
print(list)

• In the algorithm above, each item is iterated over starting with the first value (9) as the 5 is already in the correct position

• The 9 (the current item) is compared to each previous value using the “position” pointer. While the “position” pointer is greater than the 0th index and the previous item (5) is also larger than 9 then the 5 will be moved right. 5 is less than 9 so no move happens. The 9 is therefore in the correct position

• The process repeats with 4 which is compared to the 9, which is larger and therefore moved right, then 4 is compared to 5, which is larger and is also moved right

• Moving an item right is defined using the “list[position] = list[position-1]” which sets the previous item into the current “position”

• The for loop iterates over all items in the list and each is compared until the correct position is found for each item

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;
        }
    }