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.
| Property | Value |
|---|---|
| Time (best, average, worst) | O(n2) in all cases |
| Comparisons | always n(n - 1)/2 |
| Swaps | at most n - 1 |
| Extra space | O(1), sorts in place |
| Stable | no |
Selection sort example
The following is a basic implementation of selection sort.
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.
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.
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.
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.
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.
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.
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.
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
List all Python tutorials.