Overview
Selection sort is a straightforward comparison-based method used in computer science to arrange items into order. The algorithm repeatedly finds the smallest (or largest) remaining element and places it into the next position of the output sequence. Although easy to understand and implement, it is not as efficient as many more advanced sorting algorithms such as quicksort or mergesort for large data sets.
How the algorithm works
At each step, selection sort scans the unsorted portion of the array to find the minimum element, then swaps that element with the first item of the unsorted region. The sorted region grows by one with each iteration while the unsorted region shrinks. The process continues until every element has been placed in its final position.
Characteristics and complexity
Selection sort performs about n(n-1)/2 comparisons in the worst, average, and best cases, so its running time is quadratic: O(n²). The number of swaps, however, is at most n-1, because each iteration does at most one swap. Memory overhead is minimal (O(1)) since it sorts in place and requires no additional arrays beyond a few variables.
Variants and stability
By default, selection sort is not stable: equal elements may change their relative order because of swaps. Stability can be preserved at the cost of additional moves (for example by shifting elements rather than swapping). Common variants include selecting the maximum each pass (which is equivalent but reverses direction) and double-ended selection that finds both minimum and maximum on each pass.
Practical uses and comparison
Selection sort is rarely used for performance-critical code, but it has a few niches. It is useful where memory is extremely limited because it sorts in place and requires constant extra space. It also minimizes the number of swaps, which can matter when writes are expensive. In teaching contexts it is favored for illustrating basic algorithmic ideas and for comparing with insertion and bubble sort.
Simple example and steps
Given an array [5, 2, 4, 6, 1, 3], selection sort would:
- Find 1 and swap with first element: [1, 2, 4, 6, 5, 3]
- Find 2 (already in place): [1, 2, 4, 6, 5, 3]
- Find 3 and swap into third position: [1, 2, 3, 6, 5, 4]
- Find 4 and swap into fourth position: [1, 2, 3, 4, 5, 6]
Selection sort remains a useful pedagogical tool and a practical choice for tiny arrays or special environments despite its quadratic time complexity compared with more scalable methods.
Further reading: see introductory algorithm texts or online resources about sorting for step-by-step pseudocode and visualizations (overview, comparisons, related methods, complexity details).