ZetCode

Python selection sort

last modified November 18, 2026 Python 3.15

In this article we explain the selection sort algorithm in Python. We implement and trace it, count its comparisons and swaps, examine its stability, and compare it with the built-in sorted function.

Selection sort is one of the simplest sorting algorithms. It is slow for large inputs, but it has one useful property: it performs at most n - 1 swaps. This matters when writing an element is much more expensive than reading it.

Selection sort algorithm

Selection sort divides the list into a sorted part on the left and an unsorted part on the right. In each step it selects the smallest element of the unsorted part and swaps it with the first unsorted element. The sorted part then grows by one element. Unlike in insertion sort, the elements of the sorted part are already in their final positions.

PropertyValue
Time (best, average, worst)O(n2) in all cases
Comparisonsalways n(n - 1)/2
Swapsat most n - 1
Extra spaceO(1), sorts in place
Stableno

Selection sort example

The following is a basic implementation of selection sort.

selection_sort.py
def selection_sort(vals):
    n = len(vals)
    for i in range(n - 1):
        min_idx = i
        for j in range(i + 1, n):
            if vals[j] < vals[min_idx]:
                min_idx = j
        vals[i], vals[min_idx] = vals[min_idx], vals[i]


nums = [64, 25, 12, 22, 11]
selection_sort(nums)
print(nums)

The outer loop moves the boundary between the sorted and the unsorted part. The inner loop finds the index of the smallest element in vals[i:]. The element is then swapped into position i. The last element needs no step of its own; when the others are in place, it is too.

$ python selection_sort.py
[11, 12, 22, 25, 64]

Tracing the algorithm

We print the selected minimum and the list after each step.

selection_trace.py
def selection_sort(vals):
    n = len(vals)
    for i in range(n - 1):
        min_idx = i
        for j in range(i + 1, n):
            if vals[j] < vals[min_idx]:
                min_idx = j
        print(f'step {i + 1}: min {vals[min_idx]:>2} at index {min_idx}, '
              f'swap with index {i}')
        vals[i], vals[min_idx] = vals[min_idx], vals[i]
        print(f'        {vals[:i + 1]} | {vals[i + 1:]}')


selection_sort([29, 10, 14, 37, 13, 5])

In step 2 the minimum is already in place, so the element is swapped with itself. Every element left of the vertical bar is in its final position.

$ python selection_trace.py
step 1: min  5 at index 5, swap with index 0
        [5] | [10, 14, 37, 13, 29]
step 2: min 10 at index 1, swap with index 1
        [5, 10] | [14, 37, 13, 29]
step 3: min 13 at index 4, swap with index 2
        [5, 10, 13] | [37, 14, 29]
step 4: min 14 at index 4, swap with index 3
        [5, 10, 13, 14] | [37, 29]
step 5: min 29 at index 5, swap with index 4
        [5, 10, 13, 14, 29] | [37]

Comparisons and swaps

Selection sort is not adaptive: it scans the whole unsorted part in every step, no matter how the input looks. On the other hand, it moves elements rarely. We count both operations and compare them with bubble sort.

operations.py
import random


def selection_sort(vals):
    comparisons = swaps = 0
    n = len(vals)
    for i in range(n - 1):
        min_idx = i
        for j in range(i + 1, n):
            comparisons += 1
            if vals[j] < vals[min_idx]:
                min_idx = j
        if min_idx != i:
            vals[i], vals[min_idx] = vals[min_idx], vals[i]
            swaps += 1
    return comparisons, swaps


def bubble_sort(vals):
    comparisons = swaps = 0
    n = len(vals)
    for i in range(n - 1):
        swapped = False
        for j in range(n - 1 - i):
            comparisons += 1
            if vals[j] > vals[j + 1]:
                vals[j], vals[j + 1] = vals[j + 1], vals[j]
                swaps += 1
                swapped = True
        if not swapped:
            break
    return comparisons, swaps


rng = random.Random(2)
n = 100
inputs = {
    'sorted': list(range(n)),
    'random': rng.sample(range(n), n),
    'reversed': list(range(n, 0, -1)),
}

print(f'{"input":<10}{"selection":>20}{"bubble":>20}')
for name, vals in inputs.items():
    sc, ss = selection_sort(vals.copy())
    bc, bs = bubble_sort(vals.copy())
    print(f'{name:<10}{sc:>8} cmp {ss:>4} swp{bc:>8} cmp {bs:>4} swp')

Here we swap only when the minimum is not already in place. Selection sort makes 4950 comparisons for every input of 100 elements, even for a sorted one, where bubble sort with an early exit needs only 99. But it swaps at most 99 times; on the random list it swaps 95 times, while bubble sort swaps 2661 times. The reversed list needs only 50 swaps: each swap puts two elements into their final positions.

$ python operations.py
input                selection              bubble
sorted        4950 cmp    0 swp      99 cmp    0 swp
random        4950 cmp   95 swp    4950 cmp 2661 swp
reversed      4950 cmp   50 swp    4950 cmp 4950 swp

Selection sort is not stable

The long-distance swap can move an element past another element with an equal key. This makes selection sort unstable.

unstable.py
def selection_sort(vals, key):
    n = len(vals)
    for i in range(n - 1):
        min_idx = i
        for j in range(i + 1, n):
            if key(vals[j]) < key(vals[min_idx]):
                min_idx = j
        vals[i], vals[min_idx] = vals[min_idx], vals[i]


cards = [('4', 'hearts'), ('5', 'spades'), ('3', 'diamonds'),
         ('4', 'clubs'), ('2', 'hearts')]

selection_sort(cards, key=lambda c: c[0])
print(cards)

We sort cards by rank. The four of hearts comes before the four of clubs in the input. In the first step, the two of hearts is swapped with the four of hearts, which moves the four of hearts to the end of the list, behind the four of clubs. In the result, the order of the two fours is reversed.

$ python unstable.py
[('2', 'hearts'), ('3', 'diamonds'), ('4', 'clubs'), ('4', 'hearts'), ('5', 'spades')]

Stable selection sort

We can make selection sort stable by not swapping. Instead, the minimum is removed and inserted at the boundary, and the elements between shift one position to the right.

stable_selection.py
def stable_selection_sort(vals, key):
    n = len(vals)
    for i in range(n - 1):
        min_idx = i
        for j in range(i + 1, n):
            if key(vals[j]) < key(vals[min_idx]):
                min_idx = j
        vals.insert(i, vals.pop(min_idx))


cards = [('4', 'hearts'), ('5', 'spades'), ('3', 'diamonds'),
         ('4', 'clubs'), ('2', 'hearts')]

stable_selection_sort(cards, key=lambda c: c[0])
print(cards)

The pop and insert methods shift the elements in between. The strict < comparison selects the first of several equal minimums. The fours now keep their input order. The price is O(n) moves per step, which removes the main advantage of selection sort.

$ python stable_selection.py
[('2', 'hearts'), ('3', 'diamonds'), ('4', 'hearts'), ('4', 'clubs'), ('5', 'spades')]

Key functions and descending order

We add the key and reverse parameters. For a descending order, the algorithm selects the maximum instead of the minimum.

selection_key.py
def selection_sort(vals, key=None, reverse=False):
    if key is None:
        key = lambda e: e
    n = len(vals)
    for i in range(n - 1):
        best = i
        best_key = key(vals[i])
        for j in range(i + 1, n):
            k = key(vals[j])
            if (k > best_key) if reverse else (k < best_key):
                best, best_key = j, k
        vals[i], vals[best] = vals[best], vals[i]


countries = ['Slovakia', 'Hungary', 'Poland', 'Austria', 'Czechia', 'Slovenia']

selection_sort(countries)
print(countries)

selection_sort(countries, reverse=True)
print(countries)

selection_sort(countries, key=lambda c: c[-1])
print(countries)

The key of the current best element is stored in best_key so that the key function is called only once per inspected element. The last call sorts the countries by their last letter. Four names end with a; the selection is unstable, so their relative order is not guaranteed in general.

$ python selection_key.py
['Austria', 'Czechia', 'Hungary', 'Poland', 'Slovakia', 'Slovenia']
['Slovenia', 'Slovakia', 'Poland', 'Hungary', 'Czechia', 'Austria']
['Slovenia', 'Slovakia', 'Czechia', 'Austria', 'Poland', 'Hungary']

Double selection sort

A variant of the algorithm finds both the minimum and the maximum in one pass and places them at both ends of the unsorted part.

double_selection.py
def double_selection_sort(vals):
    lo, hi = 0, len(vals) - 1
    passes = 0
    while lo < hi:
        passes += 1
        min_idx = max_idx = lo
        for j in range(lo + 1, hi + 1):
            if vals[j] < vals[min_idx]:
                min_idx = j
            elif vals[j] > vals[max_idx]:
                max_idx = j
        vals[lo], vals[min_idx] = vals[min_idx], vals[lo]
        if max_idx == lo:
            max_idx = min_idx
        vals[hi], vals[max_idx] = vals[max_idx], vals[hi]
        lo += 1
        hi -= 1
    return passes


nums = [9, 4, 7, 1, 8, 2, 6, 3, 5, 0]
passes = double_selection_sort(nums)
print(nums, f'in {passes} passes')

nums = [5, 1, 4, 2, 3]
double_selection_sort(nums)
print(nums)

The number of passes is halved, although the number of comparisons stays roughly the same. One case needs care: if the maximum was at position lo, the first swap has just moved it to min_idx. The if statement updates the index before the second swap. The second list, which starts with its maximum, tests this case.

$ python double_selection.py
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9] in 5 passes
[1, 2, 3, 4, 5]

Benchmark

We compare the pure Python loop, a version that finds the minimum with the built-in min function, and sorted.

benchmark.py
import random
import timeit


def selection_sort(vals):
    n = len(vals)
    for i in range(n - 1):
        min_idx = i
        for j in range(i + 1, n):
            if vals[j] < vals[min_idx]:
                min_idx = j
        vals[i], vals[min_idx] = vals[min_idx], vals[i]


def selection_sort_min(vals):
    n = len(vals)
    for i in range(n - 1):
        min_idx = min(range(i, n), key=vals.__getitem__)
        vals[i], vals[min_idx] = vals[min_idx], vals[i]


rng = random.Random(4)
data = [rng.randint(0, 10_000) for _ in range(2000)]

for func in (selection_sort, selection_sort_min, sorted):
    t = timeit.timeit(lambda: func(data.copy()), number=3) / 3
    print(f'{func.__name__:<20} {t:.6f} s')

The min function with key=vals.__getitem__ runs the search loop in C, but it still calls the key for every index, so the gain is small. Both are O(n2) and hundreds of times slower than sorted on 2000 elements. The times vary between runs and machines.

$ python benchmark.py
selection_sort       0.040029 s
selection_sort_min   0.039571 s
sorted               0.000173 s

Source

Sorting Techniques – Python documentation

min – Python built-in functions

In this article we have implemented selection sort in Python and examined its comparisons, swaps, and stability. See also Python bubble sort, Python insertion sort, Python heap sort, and Python sort list.

Author

I am Jan Bodnar, a programmer and technical writer. I have been writing programming tutorials at ZetCode since 2007 and have published eight e-books. See about the author.

List all Python tutorials.