Selection Sort

Situation	Comparisons	Swaps	Total Time Complexity
Worst	$O(n^2)$	$O(n)$	$O(n^2)$
Best	$\Omega(n^2)$	$\Omega(1)$	$\Omega(n^2)$
Tight	$\Theta(n^2)$	-	$\Theta(n^2)$

From the invariant we used to prove the correctness of the bubble sort algorithm, we could come up with a new sorting algorithm.

\[\text{Invariant(i)}: \text{After the $i$th iteration, the $i$ largest elements are in the correct position.} \]

Rather then bubbling up the largest element to the end of the array, we could instead find the largest element and just move it to the end of the array. This is the idea behind the so called Selection Sort algorithm. The name comes from the fact that the algorithm works by repeatedly selecting the largest remaining element and moving it to the end of the array until the entire array is sorted. This selection process is what gives the algorithm its name.

This process makes the selection sort algorithm probably one of the most intuitive sorting algorithms and the one I actually use when sorting a deck of cards. A common variation of the selection sort is rather than moving the largest element to the end of the array, we move the smallest element to the front of the array. The effect would be the same, but we would then have to change the invariant to reflect this.


public void selectionSort(int[] arr) {
    // sort by moving the largest element to the end of the array
    for (int i = arr.length - 1; i > 0; i--) {
        int maxIndex = 0;
        for (int j = 1; j <= i; j++) {
            if (arr[j] > arr[maxIndex]) {
                maxIndex = j;
            }
        }
        // swap largest element to the correct position
        int temp = arr[i];
        arr[i] = arr[maxIndex];
        arr[maxIndex] = temp;
    }
}

Visualization of the selection sort algorithm. This is the variation where the smallest element is moved to the front of the array, not the largest to the end.

Correctness

The correctness of the selection sort algorithm is basically given by the invariant and will not be proven here.

Analysis

Just like with the bubble sort algorithm we will analyze the number of comparisons and swaps to determine the time complexity of the selection sort algorithm.

The number of comparisons is just like in the bubble sort algorithm the same no matter the content of the array. The number of comparisons is given by number of iterations of the outer loop times the number of iterations of the inner loop. Which is the same as in the improved bubble sort algorithm, $\frac{n(n-1)}{2} = \frac{1}{2}(n^2 - n)$. Meaning the number of comparisons is in $\Theta(n^2)$.

In the implementation above we always make a swap. Making the worst case number of swaps the number of outer loop iterations in $O(n)$. However, if $\text{maxIndex} = i$ we don’t need to make a swap. If we checked for this at the end of the inner loop we would add $n-1$ comparisons, which wouldn’t asymptotically change the number of comparisons but would reduce the number of swaps in the best case, where the array is already sorted, to $\Omega(1)$.


//same as above
if (maxIndex != i) {
    int temp = arr[i];
    arr[i] = arr[maxIndex];
    arr[maxIndex] = temp;
}

Situation	Comparisons	Swaps	Total Time Complexity
Worst	\(O(n^2)\)	\(O(n)\)	\(O(n^2)\)
Best	\(\Omega(n^2)\)	\(\Omega(1)\)	\(\Omega(n^2)\)
Tight	\(\Theta(n^2)\)	-	\(\Theta(n^2)\)