Imagine lining up a class from shortest to tallest. The most natural method needs no cleverness at all: look across everyone, spot the single shortest person, and walk them to the front. Now pretend that person has vanished, look again at who is left, find the new shortest, and place them second. Keep going until nobody is left to move. That is exactly what Selection Sort does with numbers — each round it selects the smallest value still out of place and drops it straight into its final spot.
Call the list size $n$. The work splits into rounds called passes. In the first pass you compare your current best-guess minimum against every other element, just to be certain you really found the smallest — that costs $n-1$ comparisons. The next pass has one fewer element left to check, so $n-2$ comparisons, then $n-3$, and so on down to $1$. For a tiny list of $n=5$ that is $4+3+2+1=10$ comparisons. The pattern to notice: each pass costs about $n$ checks and there are about $n$ passes, so the effort grows like $n \times n$.
Adding the passes exactly gives the total comparison count:
The striking part is that this total never changes. A list that is already sorted costs exactly the same as a shuffled one, because the inner scan has no way to know it has found the minimum without checking every remaining element — Selection Sort is input-oblivious. Its one redeeming trick is movement: it swaps data only once per pass, at most $n-1$ times in total, which is why it shines on write-expensive memory like flash. In the sim, the n slider sets the list size, the Preset menu picks the starting order, and the red cell marks the current minimum while the blue scanner sweeps to the right.
Try this in the sim above: (1) set the preset to Already sorted and watch the comparison counter still climb all the way to $\frac{n(n-1)}{2}$ — there is no shortcut. (2) Switch to Reverse sorted and confirm the comparison count is identical, then watch the much smaller swap counter. (3) Shrink n and step through one full pass to see the red minimum-marker jump only at the moment a smaller value appears.
Selection Sort is one of the most intuitive sorting algorithms, introduced in early computer science literature. It works by repeatedly finding the minimum element from the unsorted portion and placing it at the beginning. Despite being conceptually simple, its key property is that it performs at most n−1 swaps — exactly one per pass — making it optimal for write-expensive memory (flash storage, magnetic media).
| Symbol | Meaning | Range |
|---|---|---|
| \(n\) | Input array size | \(\mathbb{Z}^+\) |
| \(T(n)\) | Number of comparisons | \(\frac{n(n-1)}{2}\) (all cases) |
| \(S(n)\) | Number of swaps | \([0, n-1]\) |
| \(i\) | Outer loop — current sorted boundary | \(0 \leq i \leq n-2\) |
| \(j\) | Inner loop — scan position | \(i+1 \leq j \leq n-1\) |
| minIdx | Index of current minimum found | \(i \leq \text{minIdx} \leq n-1\) |
In pass \(i\), the inner loop scans positions \(i+1\) through \(n-1\), performing \(n-1-i\) comparisons to find the minimum:
$$\text{Comparisons in pass } i = n - 1 - i$$Unlike Bubble Sort, Selection Sort makes the same number of comparisons regardless of input order — there is no early exit:
$$T(n) = \sum_{i=0}^{n-2}(n-1-i) = \sum_{k=1}^{n-1} k = \frac{n(n-1)}{2}$$Each pass performs at most 1 swap (when minIdx ≠ i). So the total number of swaps is at most \(n-1\):
$$S(n) \leq n - 1 = \mathcal{O}(n)$$Compare this to Bubble Sort's worst-case \(\frac{n(n-1)}{2}\) swaps. For write-costly storage, Selection Sort is dramatically better.
Standard Selection Sort is NOT stable. When the minimum is found and swapped to position \(i\), it can jump over equal elements, disturbing their relative order. Example: swapping A[0]=3 with A[3]=1 in [3a, 3b, 2, 1] places 1 at front but moves 3a past 3b.
Selection Sort cannot be improved by early exit because its inner loop must scan the entire unsorted region to guarantee finding the minimum. \(T(n) = \Theta(n^2)\) in all cases — there is no best case improvement unlike Bubble Sort or Insertion Sort.
Array: [64, 25, 12, 22, 11]
Pass 0 (i=0): Scan [1..4], find min=11 at index 4. Swap A[0]↔A[4] → [11, 25, 12, 22, 64]. Swaps: 1.
Pass 1 (i=1): Scan [2..4], find min=12 at index 2. Swap A[1]↔A[2] → [11, 12, 25, 22, 64]. Swaps: 1.
Pass 2 (i=2): Scan [3..4], find min=22 at index 3. Swap A[2]↔A[3] → [11, 12, 22, 25, 64]. Swaps: 1.
Pass 3 (i=3): Scan [4..4], min=25 at index 3 (no swap needed). Comparisons: 1, Swaps: 0.
Final: [11, 12, 22, 25, 64]. Total comparisons: 10 = \(\frac{5×4}{2}\). Total swaps: 3.
j = i instead of j = i+1.j = i+1. Starting at j = i compares the element at position i with itself, never updating minIdx incorrectly but wasting one comparison per pass. More importantly, it signals a misunderstanding of the invariant: position i starts as the assumed minimum, not a candidate to beat itself.swap(A[i], A[minIdx]) without checking if minIdx != i.if minIdx != i before swapping. An unconditional swap when minIdx == i results in a self-swap (A[i]↔A[i]), which is harmless but wastes a write operation. In write-expensive environments, this doubles the worst-case write count needlessly. The check also makes the algorithm's swap count correctly bounded by \(n-1\).n-1: for i in range(n).n-2 (i.e., range(n-1)). After \(n-1\) passes, the last remaining element is automatically in its correct position — no comparison or swap needed. Running to \(n-1\) causes an inner loop with zero iterations on the last pass — harmless but unnecessary.