Selection Sort in Python
Find the smallest remaining value and move it to the front, one position at a time.
- Sorted and unsorted regions
- Finding the minimum of the rest
- Why it always does O(n²) comparisons
Select the minimum, swap it in
The problem
Some sorting algorithms try to make as few moves as possible, which matters when moving an item is expensive. Selection sort shows a different strategy from bubble sort: find the right item first, then move it once.
Think of it like this
Selection sort is like picking a team by height. You scan everyone still waiting, call out the shortest, and put them at the next spot in the line. Then you scan the rest again for the next shortest, until nobody is left.
for start in range(len(result)):📍 The next free spot in the lineminimum = start🤔 Assume this person is the shortestresult[index] < result[minimum]🔎 Scan the rest for someone shorterresult[start], result[minimum] = ...🔄 Move the shortest into the free spotSelection sort repeatedly finds the smallest item in the unsorted part of the list and swaps it into the next position of the sorted part, taking O(n²) comparisons but at most n - 1 swaps.
Key points
- Everything left of
startis already sorted; everything fromstarton is not. minimumremembers the index of the smallest value found so far in the unsorted part.- The inner loop
for index in range(start + 1, len(result)):scans the rest of the list. result[start], result[minimum] = result[minimum], result[start]makes one swap per position.
When should you use it?
- Learning sorting strategies and comparing them.
- Situations where writing or moving items is expensive and comparisons are cheap.
- Finding the k smallest items by stopping after k passes.
When not to use it
- Real programs:
sorted()is much faster. - Nearly sorted data: selection sort still scans everything, while insertion sort finishes quickly.
Selection Sort in Python visualizer
O(n²)Use Play or Step to follow each comparison and data movement.
Example code
def selection_sort(values):
result = values.copy()
for start in range(len(result)):
minimum = start
for index in range(start + 1, len(result)):
if result[index] < result[minimum]:
minimum = index
result[start], result[minimum] = result[minimum], result[start]
return result
print(selection_sort([64, 25, 12, 22, 11]))
Result of running the code
[11, 12, 22, 25, 64]
Code explanation
Each pass finds the minimum value in the unsorted suffix and swaps it into place. Time complexity is O(n²), with at most O(n) swaps.
Change the values and run the program in the CodeUtility online Python compiler without installing Python locally.
Practice exercises
Modify the runnable example with the exercises below to build understanding beyond copying the result.
- Try empty, single-item, and duplicate-value inputs.
- Print state after every step to observe the algorithm.
- Benchmark 100, 1,000, and 10,000 items, then compare another approach.
Common mistakes
Swapping inside the inner loop
That turns it into a slower, messier sort with many swaps.
for index in range(start + 1, len(result)):
if result[index] < result[start]:
result[start], result[index] = result[index], result[start]
for index in range(start + 1, len(result)):
if result[index] < result[minimum]:
minimum = index
result[start], result[minimum] = result[minimum], result[start]
Finished this lesson?
Mark it as learned to track your progress.
Practice with a challenge
Use what this lesson covers to solve a real problem. Each challenge runs in your browser with instant tests and an AI review.
- Array Minimum Find the smallest value in a list. Easy
- K-th Smallest Element Find the k-th smallest value without fully sorting. Medium