C++UCS301
Sorting AlgorithmsC++17

Selection Sort

Selection sort repeatedly selects the minimum remaining value and places it at the next output position.

Open this in the visual lab

What to understand

  • Minimum selection
  • Fixed comparison count
  • Low swap count
  • Instability

Remember this

  1. 1Always Θ(n²) comparisons
  2. 2At most n−1 swaps
  3. 3In-place but normally unstable

Detailed notes

Selection sort divides the array into a sorted prefix and unsorted suffix. It scans the entire suffix for its minimum, then exchanges that minimum with the first unsorted position.

The comparison count is fixed regardless of input order, but the algorithm uses at most n−1 swaps. This can matter when writes are far more expensive than comparisons.

How it works

  1. 1Treat index i as the next output position.
  2. 2Find the smallest key in [i, n).
  3. 3Swap it into i.
  4. 4Advance the sorted-prefix boundary.

Where it is used

  • Small embedded cases where writes are costly
  • Teaching selection invariants
  • Partial selection of a few smallest values

Common mistakes

  • Claiming a sorted input improves its comparison complexity
  • Assuming the standard swap version is stable
  • Swapping on every inner-loop improvement instead of once per pass

Complexity analysis

OperationBestAverageWorstExtra space
SortO(n²)O(n²)O(n²)O(1)

C++ implementation

C++17 reference
main.cpp

Selection sort

The prefix before i is sorted and contains the i smallest input values.

void selectionSort(vector<int>& values) {
    for (int i = 0; i < static_cast<int>(values.size()); ++i) {
        int minimum = i;
        for (int j = i + 1; j < static_cast<int>(values.size()); ++j)
            if (values[j] < values[minimum]) minimum = j;
        swap(values[i], values[minimum]);
    }
}
8 linesUTF-8 · C++ study reference

Exam & viva

Open a prompt when you are ready to check your answer.