Selection sort

Selection sort is an $\Theta(n^2)$ time complexity in-place comparison sort. Regardless of data it always has the same running time. Although the time complexity is always $n^2$, selection sort minimises the number of swaps and this makes it a useful algorithm for applications where the cost of swapping is high.

The algorithm sorts the list building the sorted section front to back. Each pass through the list finds the minimum element in the unsorted range and swaps the element so that it is at the end of the sorted portion of the list.

Properties

• $O(1)$ space
• $\Theta(n^2)$ comparisons
• $\Theta(n)$ swaps
• Not stable
• Not adaptive