Insertion Sort

Tags

algorithm comp-sci

A sorting algorithm that replicates how one orders [see page 11, playing cards].

for j in range(1, len(arr)):
    key = arr[j]
    i = j - 1
    while i >= 0 and arr[i] > key:
	arr[i + 1] = arr[i]
	i -= 1
    arr[i + 1] = key

You can see the insertion sort algorithm in alg:insertion-sort. The main idea behind insertion sort is to compare each element we encounter with all the elements before it and then shuffle it down until we find the first element smaller than it.

The loop invariant for this example is that at the start of each iteration of the outer for loop the subset of elements from \( 0 \) to \( j-1 \) are in-order. To [see page 15, prove] this at:

1. Initialisation: At this point \( j = 0 \), meaning \( arr[0:j-1] \) has only one element therefore its sorted (trivially).
2. Maintenance: The while loop moves \( arr[j-1], arr[j-2], \ldots \) one position to the right and inserts \( a[j] \) at the correct position \( i+1 \). Then \( A[0:j-1] \) contains the original \( A[0:j-1] \) but in sorted order.
3. Termination: The for loop ends when \( j = len(arr) + 1 \) meaning the subset of elements from \( 0 \) to \( len(arr) + 1 - 1 \), I.E. \( arr[0:len(arr)] \) is in order.