CM20008: Algorithms and Complexity - Simple Sorting Algorithms

Sorting Algorithms

Sorting data into a useful order is essential throughout computation.
- Sorted data can be searched efficiently (logarithmic time algorithms such as binary search scale very well).
- Sorted data is easier to understand.
- It used to be said that 25% of computation time is spent on sorting, though this is likely outdated.

Plan

Correctness and complexity of some simple sorting algorithms
- Selection Sort
- Insertion Sort
Some more interesting sorting algorithms:
- Shell Sort
- Mergesort – a divide and conquer algorithm
Complexity of mergesort and its optimality
Calculating complexity by solving recurrence relations: the Master Theorem

Selection Sort

Selection sort involves finding the minimum element of the as-yet-unsorted data and putting it into position, repeating this process.
Java implementation:

for (int i=0; i<a.length; i++){
    int j = findMin(a,i);
    swap(a,i,j);
}

Correctness of Selection Sort

Observation 1: At the $i$ -th iteration, the part of the array from $a[0]$ up to $a[i-1]$ is sorted.
- a[0] a[1] … a[i - 1] a[i] …
- sorted unsorted
Observation 2: At the $i$ -th iteration, the part of the array from $a[0]$ up to $a[i-1]$ contains elements which are all smaller than those from $a[i]$ onwards:
- a[0] a[1] … a[i - 1] a[i] …
- smaller larger
- sorted unsorted
- Therefore, the minimum element in the section from $a[i]$ onwards is:
- Larger than anything in $a[0]$ to $a[i-1]$
- Smaller than anything else from $a[i]$ to the end
After swapping this element with $a[i]$ the situation is:
- a[0] a[1] … a[i - 1] a[i] a[i+1] …
- smaller larger
- sorted unsorted
- Incrementing $i$ restores the previous state.

Loop Invariant

The setup a[0] a[1] … a[i - 1] a[i] … where the first part is smaller sorted and the second part is larger unsorted is a loop invariant.
A loop invariant is a logical predicate describing the state of the program, such that:
- The loop invariant holds each time we enter the loop.
- Executing the loop body restores the invariant.
This situation holds at the beginning when $i$ is zero, and therefore also holds when the loop terminates, at which point the sorted portion is the entire array.

Generic Loop Code and Invariants

Generic loop code:

setup-code(); // the code we execute before entering the loop
while (guard) { // the guard decides whether we enter the loop
    loop-body(); // whatever the loop is doing
} // end of loop

A loop invariant is a logical predicate on the program state such that:
- In any state where the loop invariant is true and the guard is true, executing loop-body() leads to a state where the loop invariant is true.
Each time the computer tries to execute the loop, if the invariant is true at the start, then it is true afterward.
To be useful:
1. The invariant is established by the setup code: after running setup-code(), the invariant is true.
2. The invariant tells us something helpful: if the invariant is true and the guard is false, then we know something useful about the program state.

Informal Correctness Proof

Invariant: The array a is a permutation of the original array, such that the elements from a[0] to a[i-1] are sorted, and all of them are smaller than every element from a[i] onwards.
The array is a permutation of the original; otherwise, we could do all sorts of bad things and maintain the invariant.
This invariant is established at the start of the program when we set $i$ to zero.
It is maintained by every execution of the loop, as shown above.
Therefore, it remains true at the termination of the loop.
The loop terminates when the guard i<a.length is false.
At this point $i$ is greater than or equal to the length of the array a.
Therefore, the invariant tells us that all elements of the array are sorted, and the array is a permutation of the original one.

Formalization (non-examinable aside)

Proofs like this can be made completely formal, using logical systems such as Floyd-Hoare Logic.
Such proofs can then be embedded in automated software verification tools so that you know for sure that your code is correct.
This is a fascinating and important topic in modern computer science.
An extension of Floyd-Hoare logic called separation logic was developed by Peter O’Hearn to reason about things like local memory and concurrency.
Tony Hoare (who also invented quicksort) won the Turing award in 1980.
O’Hearn (together with Stephen Brookes) won the Gödel prize in 2016 for concurrent separation logic.
Floyd-Hoare Logic:

${𝑃 ∧ 𝐵} 𝑆 {𝑃}$
${𝑃} \text{while } 𝐵 \text{ do } 𝑆 {\neg 𝐵 ∧ 𝑃}$

Definition of Invariant: Some Pedantry

For this unit, a loop invariant is a predicate maintained by every execution of the loop body.
- It is not required that it is established by the setup code, or that it tells us something useful.
Useless invariants for any given loop:
- The always-true predicate
- The always-false predicate: vacuous loop invariant, because the requirement is that “if this predicate is true at the start of a loop body execution…”, which never holds.
- The negation of the loop guard: also vacuously a loop invariant.
To help with a correctness proof, we need to find an invariant which is established by the setup code and which says something worthwhile.
- Some authors insist on this for the definition of invariant, while others prefer the definition used in Floyd-Hoare logic.

Complexity of Selection Sort

findMin has linear time complexity: $O(n)$
The loop runs findMin on arrays of size 1, 2, …, up to the length of a
Therefore, the time complexity of the algorithm is $O(1) + O(2) + … + O(n) = O(n^2)$
This uses the fact that:

$1 + 2 + … + n = \frac{n(n + 1)}{2}$

Insertion Sort

Basics

Insertion sort is a sorting algorithm based on swapping adjacent elements of the array to place them correctly.
Builds up a sorted section at the start of the array, like selection sort.

Example

Suppose we have sorted the first four elements: 0 1 4 5 3 2
- sorted next
The algorithm now looks at the fifth element, here 3.
The goal is to place it correctly among the first five elements.
Compare it to its neighbor on the left:
- If it is greater than the neighbor, the first five elements are sorted already
- If it is less than the neighbor, swap them
Keep swapping to shift this element left until it is in the right place among the first five elements.
Now we have five elements sorted, and can look at the next one (in this case, 2)

Insertion Sort in Action

0 1 4 5 3 2
0 1 4 3 5 2
0 1 3 4 5 2
Now five elements are sorted; deal with the sixth
0 1 3 4 2 5
0 1 3 2 4 5
0 1 2 3 4 5
And we’re done!

Insertion Sort in Java

public void insertionSort(int[] a) {
    for (int i = 1; i < a.length; i++) {
        insert(a,i);
    }
}

public void insert(int[] a, int i) {
    while (i>0 && a[i-1]>a[i]) {
        swap(a,i-1,i);
        i--;
    }
}

Towards Correctness of Insertion Sort

Loop invariant for the main loop:
- At each iteration:
- The array a is a permutation of the original array, and
- The first $i$ elements are in sorted order.
Any single element is always sorted, so the invariant holds when is 1 – it is established by the setup code.
By inserting $a[i]$ in the right place, we move from $i$ sorted elements to $i+1$ sorted elements.
So incrementing $i$ keeps the invariant true: it is maintained by the loop body.
The invariant tells us that the whole array is sorted at the end.
To complete the argument, we would need to show correctness of the insertion algorithm; we won’t bother to do that here.

Complexity of Insertion Sort

Number of steps (comparisons and swaps) depends on the order of the array.
- Case 1: The array is already sorted:
- Each element is compared to the one on its left
- No swap is made
- The next element is considered
- In this case, for an array of length $n$ , we make $n − 1$ comparisons and no swaps.
- Case 2: The array is in descending order:
- The second element is swapped with the first: one comparison, one swap
- The third element is swapped with the second, then the first: two comparisons, two swaps
- …
- The final element is swapped with all the earlier elements: $n − 1$ comparisons, $n − 1$ swaps.
- The total is $n(n − 1)$ operations (half of them comparisons, half swaps.)

Best-Case and Worst-Case Complexity

For many algorithms, the actual number of steps taken will depend on the input data, as well as the size of the input.
The best-case complexity is the complexity of the algorithm for the input configuration it handles most efficiently.
The worst-case complexity is the complexity of the algorithm for the input configuration it handles least efficiently.
We are often interested in the worst-case complexity.
Sometimes we will consider the average-case complexity: the expected complexity for a random input of a given size.

Complexity for Insertion Sort

Best-case complexity: $O(n)$
Worst-case complexity: $O(n^2)$
Average-case complexity:
- There are $n!$ possible configurations of an array of length $n$
- Add up the total time needed to process them all, and divide by $n!$
- This turns out to be $O(n^2)$ as well.

Virtues of Insertion Sort

Next week, we will show that there are more efficient ways of sorting a list.
Advantages include:
- It’s easy to understand and use in everyday life (e.g., sorting a hand of cards or a stack of exam scripts).
- It only needs a few lines of code to implement (why might this be beneficial?).
- It’s efficient for small input, and for lists that are almost sorted.
- Insertion sort is an in-place sorting algorithm, so it doesn’t require much additional memory space. It's an In-place sorting algorithm.