Skip to content
Tutorials Center
My learning

Topics

Lesson 79 of 225 · Sorting

Selection Sort

Learn selection sort in Python: find the minimum, swap it into place, repeat. Includes a trace, swap counts, why it is not stable, a stable variant and O(n²) analysis.

Imagine sorting a hand of playing cards by looking at all of them, picking the smallest card, and placing it first. Then you look at the remaining cards, pick the smallest of those, and place it second. You continue until no cards are left. That is selection sort: on every round it selects the minimum of the unsorted part and moves it to the front.

Selection sort is as easy to understand as bubble sort, but it has a quirk that makes it worth knowing: it performs the fewest swaps of any simple sort, at most n - 1. On the other hand it always does the same number of comparisons, whatever the input looks like, and it is not stable. In this lesson you will build it, trace it, see exactly why it breaks stability, learn a stable variant, and find out when its low number of writes is actually useful.

The idea

The list is split into two parts: a sorted prefix on the left that grows by one every round, and an unsorted rest on the right.

TEXT
[ sorted | unsorted        ]
[        |  64 25 12 22 11 ]    find min of unsorted = 11 (index 4)
[ 11     |  25 12 22 64    ]    swap it with the first unsorted item (64)
[ 11 12  |  25 22 64       ]    min is 12 (index 2) -> swap with 25
[ 11 12 22 | 25 64         ]    min is 22 -> swap with 25
[ 11 12 22 25 | 64         ]    min is 25 -> already in place
[ 11 12 22 25 64           ]

The invariant: before round i, the first i items are the i smallest values of the whole list, already in their final order. Each round extends that by one.

The algorithm in plain words

  1. For i from 0 to n - 2:
  2. Assume the minimum of the unsorted part is at index i. Call it smallest.
  3. Scan j from i + 1 to the end. Whenever items[j] < items[smallest], remember j as the new smallest.
  4. Swap items[i] and items[smallest] (skip if they are the same index).

The loop stops at n - 2 because once n - 1 items are placed, the last one has nowhere else to go.

Implementation with counters

Python Selection sort with a trace

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Notice the comparison counts: five items always cost 4 + 3 + 2 + 1 = 10 comparisons, no matter whether the input is sorted, reversed or random. Selection sort cannot tell that the list is already in order, because it has to scan the whole unsorted part to be sure that the minimum is where it expects. It is not adaptive.

The swaps, on the other hand, are few: 3 swaps for the trace above (one round found its minimum already in place) and 2 for the reversed list of five (the middle item stays where it is, and two swaps fix both outer pairs).

Complexity

The inner loop makes n - 1, then n - 2, ... then 1 comparisons, so the total is n(n - 1) / 2. That is O(n²) in the best, average and worst case alike.

Comparisons Swaps Time Extra space
Best, average, worst n(n - 1) / 2 at most n - 1 O(n²) O(1)

Compare that with bubble sort, which can need up to n(n - 1) / 2 swaps. When writing an item is much more expensive than comparing two items (for example, writing to flash memory, or moving large records), selection sort's O(n) writes can beat the other simple sorts. In ordinary Python code, writes and comparisons cost about the same, so the advantage rarely matters.

Python Selection sort versus bubble sort: swaps

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The selection column never exceeds n - 1, while the bubble column grows like n² / 4.

Why selection sort is not stable

The swap in step 4 throws the item at position i far away, possibly past items equal to it. Take the records (3, 'a'), (3, 'b'), (1, 'c'), sorted by the number:

TEXT
(3,a) (3,b) (1,c)     min is (1,c) at index 2
swap index 0 and 2:
(1,c) (3,b) (3,a)     (3,a) jumped behind (3,b)  -> order of equal keys changed!
Python Selection sort breaks stability

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

If you have ever sorted a table first by one column and then by another, this is why stability matters (see sorting basics).

A stable variant

You can make selection sort stable by shifting instead of swapping: take the minimum out and insert it at position i, shifting everything in between one step to the right. The relative order of the others is preserved. The price is more writes: up to O(n) per round, so O(n²) overall, which removes the one advantage the algorithm had.

Python Stable selection sort by shifting

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Here pop and insert each move up to n items, so this version is simple but not cheap. Because the comparison is strict (<), the first of several equal minimums is chosen, which is what keeps equal items in order.

Variants

  • Selecting the maximum and placing it at the end gives a mirror-image algorithm with the same costs.
  • Double selection sort finds both the minimum and the maximum in each scan and places them at both ends, halving the number of rounds (but not the number of comparisons by much).
  • Heap sort is selection sort with a smart data structure: it uses a heap to find the maximum in O(log n) instead of scanning, which turns O(n²) into O(n log n).

That last point is the big idea: the slow part of selection sort is the repeated linear scan for the minimum. A priority queue answers "what is the smallest?" much faster.

When to use selection sort

  • When writes are expensive and the data is small.
  • When you want an algorithm whose running time does not depend on the input, which can be useful for predictable timing.
  • To teach the idea of an invariant and of "find the best, put it in place".
  • Not for large data. For anything serious use sorted().

Common mistakes

  • Swapping inside the inner loop each time a smaller item is found, instead of remembering its index and swapping once at the end. This is still correct but does far more swaps.
  • Looping i to n instead of n - 1 (harmless but wasteful) or starting the inner loop at i instead of i + 1.
  • Storing the minimum value instead of its index, then having nothing to swap with.
  • Assuming it is stable because the code looks innocent.
  • Expecting an early exit on sorted input. Selection sort has none.

Check your understanding

Quick check · 5 questions

of 5 answered You scored / 5 · perfect!

  1. 1. How many comparisons does selection sort make on a list of 6 items that is already sorted?

    It always makes 5 + 4 + 3 + 2 + 1 = 15 comparisons, because it must scan the whole unsorted part to find the minimum, whatever the order.
  2. 2. What is the maximum number of swaps selection sort performs on n items?

    Each round does at most one swap, and there are n - 1 rounds. This is the fewest swaps among the simple sorts.
  3. 3. Why is the usual swap-based selection sort not stable?

    The item that was at position i is thrown to the minimum's old position, possibly behind equal items that it used to precede.
  4. 4. What is the time complexity of selection sort in the best case?

    There is no early exit: the n(n - 1) / 2 comparisons are made in every case, so best, average and worst are all O(n²).
  5. 5. Which algorithm is selection sort improved with a heap?

    Heap sort repeatedly selects the maximum (or minimum), but a heap finds it in O(log n) instead of scanning in O(n), giving O(n log n) overall.

Summary

  • Selection sort repeatedly selects the minimum of the unsorted part and swaps it into the next position.
  • It makes n(n - 1) / 2 comparisons in every case: O(n²) time, O(1) extra space, no early exit.
  • It performs at most n - 1 swaps, the fewest among simple sorts, which helps when writes are costly.
  • The swap makes it unstable; shifting instead of swapping makes it stable but expensive.
  • Replacing the linear scan by a heap gives heap sort.

Next: Insertion Sort