Algorithms · Sorting

Selection Sort

The idea

Picking a football team by height: scan the whole line for the shortest kid and put them first. Scan everyone left for the next shortest, put them second. You always scan the entire rest of the line — even if it already looks sorted.

The problem

Another natural way to sort: find the smallest item in the whole list and put it first. Then find the smallest of what remains and put it second. Keep "selecting" the next smallest until everything is in place.

Why it's slow

Selection sort ALWAYS does the full n(n-1)/2 comparisons — 10 for our 5 items, 4,950 for 100 — even when the list is already sorted, because it can never trust a scan it has not finished. That is O(n²) with no best-case mercy. Its one redeeming trick: at most one swap per pass, far fewer moves than bubble sort.

Pseudocode

  1. repeat for each position i from the left
    Explain this line

    Position i is where the next-smallest value will be locked in.

  2. assume a[i] is the smallest; call it min
    Explain this line

    min tracks the smallest item seen so far in this scan.

  3. scan the rest, comparing each item with min
    Explain this line

    The scan never stops early — it must check everything.

  4. found something smaller? that becomes the new min
    Explain this line

    Watch the min marker hop when a smaller item shows up.

  5. swap min into position i and lock it
    Explain this line

    One single swap per pass — that is selection sort's specialty.

Complexity

Best Average Worst Space
O(n²) O(n²) O(n²) O(1)

The stubborn one: identical work no matter the input. Redeemed only by its minimal number of swaps — at most n-1.

Code

python 
def selection_sort(a):
    n = len(a)
    for i in range(n - 1):
        m = i
        for j in range(i + 1, n):
            if a[j] < a[m]:
                m = j
        a[i], a[m] = a[m], a[i]
    return a
java 
void selectionSort(int[] a) {
    for (int i = 0; i < a.length - 1; i++) {
        int m = i;
        for (int j = i + 1; j < a.length; j++) {
            if (a[j] < a[m]) m = j;
        }
        int t = a[i];
        a[i] = a[m];
        a[m] = t;
    }
}
cpp 
void selectionSort(std::vector<int>& a) {
    for (size_t i = 0; i + 1 < a.size(); ++i) {
        size_t m = i;
        for (size_t j = i + 1; j < a.size(); ++j) {
            if (a[j] < a[m]) m = j;
        }
        std::swap(a[i], a[m]);
    }
}
javascript 
function selectionSort(a) {
  for (let i = 0; i < a.length - 1; i++) {
    let m = i;
    for (let j = i + 1; j < a.length; j++) {
      if (a[j] < a[m]) m = j;
    }
    [a[i], a[m]] = [a[m], a[i]];
  }
  return a;
}
dart 
void selectionSort(List<int> a) {
  for (var i = 0; i < a.length - 1; i++) {
    var m = i;
    for (var j = i + 1; j < a.length; j++) {
      if (a[j] < a[m]) m = j;
    }
    final t = a[i];
    a[i] = a[m];
    a[m] = t;
  }
}

Quick check