Selection Sort in Python: Simple Guide and Examples
Resumen
Pixel shares a practical guide to selection sort, using a pass-by-pass example to sort [29, 10, 14, 37, 13] and complete Python code. It explains comparisons, swaps, runtime behavior on sorted input, and stability, helping the community understand the algorithm and compare it with bubble sort and Python's built-in sorted().
DEV Community
Selection Sort Explained with Simple Python Examples
Originally published on CodingCush. Selection sort is a simple sorting algorithm that scans the unsorted part of a list, finds the smallest value, and swaps it into the next free position at the front. It repeats that search until every position is filled. In this guide you will dry run selection sort pass by pass, write the complete Python version, count its comparisons and swaps, see why sorted input never speeds it up, and compare it with bubble sort and Python's built in sorted(). Every output comes from running this article's code on Python 3.12.3. How Selection Sort Works, in Plain Words Imagine exam papers on a desk, shuffled. You want them in marks order, lowest first. You search the whole pile, pick the lowest mark, and place it at the front. Then you search the rest for the next lowest. Nobody calls this fast, but nobody gets confused by it either, and that is why teachers love it. Two details define the algorithm. The list always has two parts: a sorted part growing at the front and an unsorted part shrinking behind it. And each pass makes at most one swap: a lot of looking, very little moving. That is selection sort's one real talent. One interview detail: this classic version is not stable. The swap can jump a value over an equal value, so equal items can change their relative order. We return to this in the questions below. A Dry Run on a Small List, Pass by Pass Let us sort [29, 10, 14, 37, 13] by hand. Pass 1 scans the whole list: the smallest value is 10 at index 1, so it swaps with 29 at index 0: Start: [29, 10, 14, 37, 13]
End of pass 1: [10, 29, 14, 37, 13]
End of pass 2: [10, 13, 14, 37, 29]
End of pass 3: [10, 13, 14, 37, 29]
End of pass 4: [10, 13, 14, 29, 37]
Sorted: [10, 13, 14, 29, 37]
Pass 2 scans from index 1: the smallest value is 13 at index 4, so 13 swaps with 29. Pass 3 is quiet: the smallest value left is 14, already at index 2, so nothing swaps. Pass 4 finds 29 smaller than 37 and swaps them. Notice the pattern. Pass 1 makes 4 comparisons, then 3, then 2, then 1: 10 in total, and only 3 passes end with a swap. Selection sort is a picky shopper: it reads every label, then buys one item per trip. Selection Sort in Python, Step by Step Here is the complete version. It copies the input first, so the caller's list never changes: def selection_sort(numbers):
a = numbers[:]
n = len(a)
for i in range(n - 1):
min_idx = i
for j in range(i + 1, n):
if a[j] < a[min_idx]:
min_idx = j
if min_idx != i:
a[i], a[min_idx] = a[min_idx], a[i]
return a
print(selection_sort([29, 10, 14, 37, 13]))
Output: [10, 13, 14, 29, 37]
The outer loop chooses the position we are filling. The inner loop is the search: min_idx starts at i, and every later value gets one chance to beat it. Only a strictly smaller value replaces it, so the first smallest wins when values repeat. The swap sits outside the inner loop, at most once per pass, and the if min_idx != i check skips it when the smallest value is already home. Adding two counters to the same search gave this real result: Result: [10, 13, 14, 29, 37]
Comparisons: 10
Swaps: 3
Ten comparisons is no coincidence: 4 plus 3 plus 2 plus 1. Double the list and the comparisons roughly quadruple. The next sections prove why. A terminal listing of the real selection sort run tested for this article: pass by pass choices and swaps, the sorted list check, and the timing test against sorted(). Why Sorted Input Does Not Help Selection Sort Some algorithms get a free lunch on sorted input. Selection sort does not: it cannot know the rest is ordered without looking at every value, so it looks anyway. Running the same code on the sorted list [10, 13, 14, 29, 37] gave: Result: [10, 13, 14, 29, 37]
Comparisons: 10
Swaps: 0
Zero swaps, but still the full 10 comparisons. There is no early exit to add, because a pass with no swap proves nothing here. That is the opposite of our bubble sort explained with simp...

Powered by Readybot.io