Selection sort: find the next smallest value

The first swap sorts the entire illustrative input, but the algorithm has only established one fact: position 0 contains the smallest value. It still scans the other positions. This is a useful case for separating what a person can see from what the code has checked.

Follow the scans after the first swap#

At each position, remember the index of the smallest value seen in the unfinished part. Compare it with each later value. Only after the scan finishes should the chosen value move into place.

Next position to fill	Values scanned	Comparisons	Array after the pass
0	7, 2, 5, 1	3	1, 2, 5, 7
1	2, 5, 7	2	1, 2, 5, 7
2	5, 7	1	1, 2, 5, 7

The first value in each scan is the initial candidate, so a scan of four values makes three comparisons. There is no need for a final scan of the last position: every smaller value has already been placed before it.

def selection_sort(values: list[int]) -> None:
    for i in range(len(values) - 1):
        minimum = i
        for j in range(i + 1, len(values)):
            if values[j] < values[minimum]:
                minimum = j
        if minimum != i:
            values[i], values[minimum] = values[minimum], values[i]

minimum stores an index, not a value. The final assignment swaps the selected value with the one currently at position i. The function modifies the original list and returns nothing. Empty and one-element lists require no comparisons.

Count comparisons separately from swaps#

For n values, the scans perform (n−1) + (n−2) + … + 1 = n(n−1)/2 comparisons. That is quadratic growth, written O(n²), regardless of the initial order. The Big-O guide explains this distinction between growth and an exact runtime.

The function keeps only a few indices, so its extra working space is O(1). It performs at most n−1 swaps, and sometimes none. Fewer writes do not imply less total work: a sorted list avoids swaps but still pays for every comparison.

A long-distance swap can also change the order of equal-key records. Suppose records are compared only by their numeric key:

before: (2, A), (2, B), (1, C)
after the first swap: (1, C), (2, B), (2, A)

A and B had equal keys, yet their relative order reversed. An algorithm that preserves the order of equal keys is called stable. This usual swap-based selection sort is not stable. Shifting records instead of swapping can preserve their order, but gives up the low-write property.

Know what the small implementation costs#

This implementation is useful for understanding how a loop finishes one part of a problem at a time. After each pass, the finished positions contain the correct smallest values. That statement stays true throughout the loop; it is a loop invariant.

For ordinary application sorting, prefer the language’s library sort rather than this teaching function. A low swap count may matter in a specialised setting with expensive writes and a small input, but it is not evidence of a general speed advantage. Compare actual requirements before choosing on that basis.

The sorting visualiser offers a way to inspect other sorting procedures. Merge sort explains how to obtain stable sorting with O(n log n) work, with a different memory cost. Selection sort’s lesson is to count the work the code really performs, not just the moves that visibly change the list.

Questions people also ask

2 QUESTIONS

▸ Is selection sort faster on an already sorted input?

Its standard comparison count is unchanged: n(n−1)/2. The conditional-swap version on this page avoids swaps when a value is already in place, but still performs the scans.

▸ Does this function return a sorted copy?

No. It changes the supplied list in place and returns None. Make a copy before calling it when the original order must be retained.