# 3.1 Selection Sort

> Find the smallest remaining item and swap it to the front. Repeat. Simple, at most n − 1 swaps, but always O(n²) comparisons.

Chapter: Simple Sorting & Searching · ~35 min · easy
URL: https://dsa.fetehadin.com/learn/selection-sort

## Mental model

You're picking a football team, best player first. You look at **everyone** still available, pick the best, and they step forward. Then you look at everyone remaining again… That is selection sort, except we pick the *smallest* each time.

### The idea

The array has two parts: a **sorted** part on the left (initially empty) and an **unsorted** part on the right.

1. Scan the unsorted part to find the **minimum**.
2. **Swap** it with the first unsorted item. The sorted part grows by one.
3. Repeat n − 1 times.

### Why it's always O(n²)

To be sure an item is the minimum, you must look at every remaining item. Pass 1 makes n − 1 comparisons, pass 2 makes n − 2, and so on:

$$(n-1) + (n-2) + \dots + 1 = \frac{n(n-1)}{2}$$

That happens **no matter what the input is**, even if it's already sorted.

### Its one strength

It does **at most n − 1 swaps**. If moving data is very expensive (huge records, flash memory), that matters. For huge records, see *pointer sort* next.

## C++ code: selection-sort.cpp

```cpp
#include <iostream>
#include <utility>
using namespace std;

void selectionSort(int a[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int minIdx = i;
        for (int j = i + 1; j < n; j++)
            if (a[j] < a[minIdx])
                minIdx = j;
        swap(a[i], a[minIdx]);   // at most one swap per pass
    }
}

int main() {
    int a[] = {29, 10, 14, 37, 13, 5};
    int n = sizeof(a) / sizeof(a[0]);
    selectionSort(a, n);
    for (int i = 0; i < n; i++) cout << a[i] << " ";
    cout << "\n";
}
```

Expected output:

```text
5 10 13 14 29 37
```

## Complexity

| Case | Cost |
| --- | --- |
| Best case | O(n²): it still scans for the minimum every pass |
| Average case | O(n²) |
| Worst case | O(n²): n(n−1)/2 comparisons |
| Swaps | at most n − 1 (the fewest of the simple sorts) |

Space: O(1)
Stable: no
In-place: yes

Good when **writing** to memory is expensive (few swaps). Bad when the data is already nearly sorted, because it cannot stop early.

## Videos

- [Selection sort algorithm](https://youtu.be/GUDLRan2DWM) (mycodeschool): Derives the algorithm from the "find the minimum" idea and analyses it carefully.
- [Selection sort in 3 minutes](https://youtu.be/g-PGLbMth_g) (Michael Sambol): A 3-minute animation. Ideal as a pre-exam refresher.

## Exam lens

Likely questions:

- Trace selection sort on `64, 25, 12, 22, 11`, showing the array after each pass.
- How many comparisons and swaps does selection sort make for n items?
- Why is selection sort not stable? Give an example.
- Compare selection sort and bubble sort in terms of swaps.

Common mistakes:

- Swapping inside the inner loop every time a smaller item is found. Swap **once**, after the inner loop.
- Starting the inner loop at `j = i` instead of `j = i + 1` (compares an item with itself).
- Claiming selection sort has an O(n) best case. It has none; it always scans.

## Quick check

1. After 2 passes of selection sort on `5, 3, 8, 1, 2` the array is:
   A. `1, 2, 8, 5, 3`
   B. `1, 3, 8, 5, 2`
   C. `1, 2, 3, 5, 8`
   D. `3, 5, 1, 2, 8`
   Answer: A. Pass 1 swaps 5↔1 → `1, 3, 8, 5, 2`. Pass 2 swaps 3↔2 → `1, 2, 8, 5, 3`.

2. Maximum number of swaps for n items?
   A. n − 1
   B. n²
   C. n(n−1)/2
   D. log n
   Answer: A. One swap per pass, n − 1 passes.

3. Selection sort on an already sorted array runs in…
   A. O(1)
   B. O(n)
   C. O(n log n)
   D. O(n²)
   Answer: D. It still compares every remaining pair to be sure it found the minimum.

4. Is selection sort stable on `2a, 2b, 1`?
   A. Yes
   B. No: after sorting, 2b comes before 2a
   Answer: B. Pass 1 swaps 2a with 1 → `1, 2b, 2a`. The equal items swapped order.

## Practice

**Trace by hand.** Trace selection sort on `64, 25, 12, 22, 11`. Show the array after each pass and count comparisons.

Solution:

- Pass 1: min 11 → `11 25 12 22 64`
- Pass 2: min 12 → `11 12 25 22 64`
- Pass 3: min 22 → `11 12 22 25 64`
- Pass 4: min 25 → `11 12 22 25 64`

Comparisons: 4 + 3 + 2 + 1 = **10** = 5·4/2.


**Implement it.** Write `selectionSortMax` that sorts ascending by repeatedly finding the **maximum** and placing it at the **end**.

Hint: Outer loop: `for (int end = n - 1; end > 0; end--)`. Inner loop finds the index of the max in `[0..end]`.

```cpp
void selectionSortMax(int a[], int n) {
    for (int end = n - 1; end > 0; end--) {
        int maxIdx = 0;
        for (int j = 1; j <= end; j++)
            if (a[j] > a[maxIdx]) maxIdx = j;
        swap(a[maxIdx], a[end]);
    }
}
```


**Problems:**

- [Sort Colors](https://leetcode.com/problems/sort-colors/) (medium). Hint: Selection sort works (n ≤ 300). Then try the one-pass "Dutch national flag" approach with three pointers.
- [Height Checker](https://leetcode.com/problems/height-checker/) (easy). Hint: Copy the array, sort the copy with your own selection sort, then count positions that differ.
- [Third Maximum Number](https://leetcode.com/problems/third-maximum-number/) (easy). Hint: This is three passes of "find the max", the core step of selection sort. Watch out for duplicates.

## Mastery checklist

- [ ] I can trace selection sort pass by pass.
- [ ] I can write it from memory with exactly one swap per pass.
- [ ] I can state its comparisons (n(n−1)/2) and swaps (≤ n − 1).
- [ ] I can show with an example why it is unstable.