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 simple Python examples, where a quiet pass means the list is sorted and the optimised version stops early.
Time Complexity: Why Selection Sort Is Always O(n^2)
For n items, the passes compare n minus 1, then n minus 2, down to 1. That sum is about n squared divided by 2, so the time is O(n^2) in the best, average and worst case alike. Input order changes the swap count, never the comparison count. Extra memory is O(1). If Big O itself feels fuzzy, our guide to Big O notation explained simply, with everyday examples builds the idea from scratch.
The swap count is the best thing here: at most one swap per pass, so never more than n minus 1 swaps. On our test list, bubble sort needed 5 swaps where selection sort needed 3, with the same 10 comparisons.
Selection Sort vs Bubble Sort vs sorted()
In real Python code you would sort with sorted(), which returns a new sorted list in one line:
print(sorted([29, 10, 14, 37, 13]))
[10, 13, 14, 29, 37]
The official Python sorting guide explains that sorted() uses Timsort, which spots runs of ordered data and merges them, making it fast and stable. The sequence types documentation covers lists and the list sort() method. We timed both on the same 1,000 random numbers (seed 42):
List size: 1000
Selection sort: 0.0217 seconds
Built-in sorted(): 0.000188 seconds
sorted() was about 116 times faster in this run
Timings vary by machine, but the gap widens as lists grow, because O(n log n) pulls away from O(n^2) quickly. Our overview of Python data structures explained with examples shows where lists fit among tuples, sets and dictionaries.
| Case or feature | Selection sort | Bubble sort | Python sorted() (Timsort) |
|---|---|---|---|
| Best case | O(n^2) | O(n), optimised, on sorted input | O(n) on ordered data |
| Average case | O(n^2) | O(n^2) | O(n log n) |
| Worst case | O(n^2) | O(n^2) | O(n log n) |
| Swaps | At most n minus 1 | Up to O(n^2) | Moves runs |
| Extra memory | O(1), in place | O(1), in place | O(n) worst case |
| Stable | No, classic form | Yes | Yes |
| Best use | Learning, few swaps | Learning, tiny lists | Real code, any size |
When Selection Sort Is and Is Not Useful
Selection sort is useful for learning how a search inside a loop works, for interview questions about swaps, and where writing data costs far more than reading it, because its swap count is the lowest of the simple sorts.
It is not useful for large data or everyday Python code: no reward for nearly sorted input, not stable in this form, and sorted() beats it by a wide margin.
Common Mistakes and Troubleshooting
Swapping inside the inner loop. If the swap sits inside the search loop, values move before the search finishes and the result comes out wrong. Search first, remember the index, swap once after the inner loop ends.
Swapping a value instead of a position. The search tracks an index, min_idx, not a value. Always swap a[i] with a[min_idx]; swapping with a saved value breaks when duplicates appear.
Starting the inner loop at 0. The search must start at i + 1, just past the position being filled. Starting earlier rechecks the sorted front or compares a position with itself.
Expecting a best case speedup. Same speed on sorted and shuffled input is not a bug. That flat line is selection sort working exactly as designed.
Frequently Asked Questions
Why is it called selection sort?
Because each pass selects the smallest value from the unsorted part and places it next.
Is selection sort stable?
No, not in this classic form. The long swap can jump a value over an equal value and change their order.
Which is better, selection sort or bubble sort?
Both are O(n^2) on comparisons. Selection sort swaps far less, at most n minus 1 times, while optimised bubble sort can finish in one pass on sorted input. For real code, both lose to sorted().
Should I use selection sort in real Python projects?
Almost never. Use sorted() or the list sort() method: faster, stable and tested. Selection sort earns its place in learning and interviews.
Conclusion
Selection sort searches everything, every time, and swaps as little as possible. You saw [29, 10, 14, 37, 13] settle into order in 4 passes, counted 10 comparisons and 3 swaps, watched a sorted list still cost all 10 comparisons, and measured sorted() about 116 times faster on 1,000 items. Learn it for the search pattern, then sort real lists the Python way.
![Terminal listing of the real selection sort run tested for this article: the list [29, 10, 14, 37, 13] sorted pass by pass with the smallest index chosen in each pass, 10 comparisons and 3 swaps, an already sorted list still needing 10 comparisons with 0 swaps, and sorted() about 116 times faster on 1000 items](https://media2.dev.to/dynamic/image/width=800%2Cheight=%2Cfit=scale-down%2Cgravity=auto%2Cformat=auto/https%3A%2F%2Fdev-to-uploads.s3.us-east-2.amazonaws.com%2Fuploads%2Farticles%2Fqhgc9y1maaiqmi7pe6fb.png)
Top comments (0)