Selection sort is a simple sorting algorithm which starts by splitting the input array into two parts, a sorted part and an unsorted part, the unsorted part is then iterated through and the smallest element is swapped with the element at the start of the unsorted part.

void swap(int &a, int &b) {
	int temp = a;
	
	a = b;
	b = temp;
}

void selectionSort(vector<int>& arr) {
	for (int i = 0; i < arr.size(); i++) {
		int m = i;
		
		for (int j = m; j < arr.size(); j++) {
			if (arr[j] < arr[m]) {
				minIndex = j;
			}
		}
		
		swap(arr[i], arr[m]);
	}
}

Usage

Selection sort can sometimes be useful in a few systems where reads are super quick but writes are very expensive and where there isn't a large amount of data.

Analysis

Runtime Complexity

Looking at the two for loops, we can see that the first loop always iterates from 0 to arr.size(), the inner loop on the other hand iterates from i to arr.size(). Using this knowledge we can construct a formula for the runtime

where = arr.size()

Swap Operations

In asymptotic terms we can see that the quantity of swap operations in this algorithm is modelled by as the swap function is only called once per outer loop and never in the inner loop.

Correctness

Firstly, we can read through the code and see the form of the minIndex function which was already proven in this example. We can thus assume that m is always the index of the smallest unsorted element. Using this knowledge we can see that the function swaps the element at index i with the element at the index of the smallest unsorted element m.

Running through a few examples we can see that arr[0..i-1] always contains the smallest elements in the array.

Loop Invariant: Before iteration i of the loop, arr[0..i-1] contains the i smallest elements of arr in ascending order.

Base Case: i=0

• Before executing the iteration for i=0, the invariant states that arr[0..-1] contains the 0 smallest elements of arr in ascending order
• Since the interval arr[0..-1] contains no elements the invariant holds in the base case.

Inductive Step: i = k, 0 <= k < arr.size()

• Assume the loop invariant holds prior to processing index k, ie. arr[0..k-1] contains the k smallest elements of arr in ascending order.
• The code from this example correctly identifies the index of the smallest item from arr[k..arr.size()-1]
• This element is swapped with arr[k]
• Thus after processing index k arr[0..k] contains the k+1 smallest elements of arr in ascending order and the loop invariant holds.

Termination: i=arr.size()

• Invariant property states that arr[0..arr.size()-1] contains the arr.size() smallest elements of arr in ascending order
• This interval contains the entire array, and thus the entire array is now in sorted order.
• Since arr.size() is finite, and i increments each iteration towards arr.size() the program must terminate.