Running time of selection sort and sorting complexity shown through comparisons, swaps, and stability.

Selection Sort Time Complexity: Count Comparisons and Swaps

An already sorted input may suggest that a sort should finish quickly, but the standard selection-sort scan still searches the remaining suffix on every pass. Understanding the running time of selection sort requires counting those comparisons separately from the swaps. Its overall selection-sort cost also depends on memory use and whether the implementation preserves equal elements’ order.

Selection Sort Complexity: Trace One Array

Consider this variant: for each position except the last, scan the remaining elements for the smallest value. Swap it into the current position only if it is elsewhere. Use zero-based indexes and start with [4, 2, 3, 1]:

Pass Unsorted suffix before scan Comparisons Swap Array afterward
0 [4, 2, 3, 1] 3 4 and 1 [1, 2, 3, 4]
1 [2, 3, 4] 2 None [1, 2, 3, 4]
2 [3, 4] 1 None [1, 2, 3, 4]

The first pass finds 1 at index 3 and exchanges it with 4. The array happens to be sorted afterward, but the remaining scans still run. This execution performs six value comparisons and one actual swap. A version that swaps even when the minimum is already in place has a different swap count, though its comparison count is unchanged.

Derive the Comparison Count

For an array of n elements, the first scan compares the candidate minimum against n - 1 values. The next compares against n - 2, continuing down to one. Therefore:

(n - 1) + (n - 2) + ... + 1 = n(n - 1) / 2

This is the selection sort time complexity calculation for the variant above: comparisons grow quadratically, or Θ(n²). For four elements, the formula gives 4 × 3 / 2 = 6, matching the trace. For zero or one element, no comparisons are needed. The formula counts comparisons between values, not loop-condition checks or every machine instruction.

The selection sort complexity is Θ(n²) in the best, average, and worst cases for value comparisons in this implementation. Their input orders differ, but the fixed scans do not stop early. The number of actual swaps can vary: an already sorted array needs none with the conditional swap, while any input needs at most n - 1. A different implementation or cost model should be analyzed on its own terms.

Separate Time, Space, and Stability

The time cost of selection sort is dominated by repeatedly scanning the unsorted suffix. The algorithm can sort in place with O(1) auxiliary space: it holds a few indexes and a temporary value for swapping, regardless of n. That bound excludes the input array itself.

The quadratic time taken by selection sort is distinct from its stability. The swap-based variant is not stable. Label equal keys to track their original order: [2a, 2b, 1] becomes [1, 2b, 2a] after swapping the minimum with the first element. The equal keys 2a and 2b have reversed. A stable selection-based variant can move the minimum by shifting elements instead, but its data movement and implementation differ.

Selection sort remains quadratic in running time even with a small number of swaps: finding each minimum still requires the scans. Conversely, when writes are unusually expensive, limiting swaps may be useful even though comparisons remain quadratic. Measure the relevant operations for the actual workload before choosing an algorithm.

Choose and Verify an Implementation

The runtime of selection sort makes it easy to explain and trace, but quadratic comparisons become costly as the input grows. For large general-purpose inputs, compare it with a suitable library sort and check that algorithm’s guarantees. A stable ordering requirement also rules out assuming the shown swap-based version is sufficient.

To verify an implementation, test empty, single-element, sorted, reverse-ordered, and duplicate-key inputs. Instrument value comparisons and swaps separately; for this exact scan, the comparison count should equal n(n - 1) / 2 for each input of the same length. Confirm that the result is ordered and contains the same elements as the input.