Simple and predictable
The work is always about n squared regardless of input. There is no fast case, which makes its cost easy to predict.
Selection sort
Selection sort finds the smallest remaining item and puts it at the front, then repeats on the rest. It makes the fewest swaps of any simple sort.
What you will see
9
About 2 min of reading
Quick check
Before this new lesson, one small question about the lesson you just finished. Recall it, do not look it up.
Try It
Run selection sort and count swaps.
1
Sort three numbers.
def select(a):
for i in range(len(a)):
m = i
for j in range(i + 1, len(a)):
if a[j] < a[m]:
m = j
a[i], a[m] = a[m], a[i]
return a
print(select([5, 2, 4]))
Before you run it, say out loud what it will print. Then open the answer.
What it prints
[2, 4, 5]
2
Show the smallest first.
nums = [5, 2, 4]
print(min(nums))
Before you run it, say out loud what it will print. Then open the answer.
What it prints
2
3
Count one swap per spot.
nums = [3, 2, 1]
swaps = 0
for i in range(len(nums)):
swaps += 1
print(swaps)
Before you run it, say out loud what it will print. Then open the answer.
What it prints
3
4
Print the rough cost of three.
print(len([1, 2, 3]) ** 2)
Before you run it, say out loud what it will print. Then open the answer.
What it prints
9
Put it in order
Before you write anything, put these lines back in the right order. Click a line to move it up one step. This support step is easier than writing code from scratch, and it is here to make the last example stick.
Data Flow
Selection sort repeatedly finds the smallest remaining item and swaps it forward, using the fewest swaps but still n squared comparisons.
1
find smallest remaining
↓
2
swap it forward
↓
3
one spot fixed per round
↓
4
few swaps, n squared scans
Line by line
Read the first example one line at a time. A line that prints shows what appears on screen; the rest set things up quietly.
def select(a):
sets nothing on screen
for i in range(len(a)):
sets nothing on screen
m = i
sets nothing on screen
for j in range(i + 1, len(a)):
sets nothing on screen
if a[j] < a[m]:
sets nothing on screen
m = j
sets nothing on screen
a[i], a[m] = a[m], a[i]
sets nothing on screen
return a
sets nothing on screen
print(select([5, 2, 4]))
[2, 4, 5]
Why this works
When you have a choice
Swaps versus comparisons
Selection sort minimizes swaps but not comparisons. When writing to memory is expensive, few swaps help; when comparing is expensive, it does not.
Examples
Find the smallest
nums = [5, 2, 4]
print(min(nums))The smallest is 2. Selection sort starts by putting that value at the front.
Swap it forward
nums = [5, 2, 4]
i = nums.index(min(nums))
nums[0], nums[i] = nums[i], nums[0]
print(nums)Swapping the smallest to the front fixes one spot. The rest is sorted the same way.
Repeat on the rest
def select(a):
for i in range(len(a)):
m = i
for j in range(i + 1, len(a)):
if a[j] < a[m]:
m = j
a[i], a[m] = a[m], a[i]
return a
print(select([5, 2, 4]))Each round fixes one more spot from the left. After n rounds the row is ordered.
Fewest swaps
nums = [3, 2, 1]
swaps = 0
for i in range(len(nums)):
swaps += 1
print(swaps)At most one swap per spot. Selection sort swaps far less than bubble sort.
Still n squared
print(len([1, 2, 3]) ** 2)Finding the smallest each round scans the rest, so the comparisons are still n squared.
Swaps matter for big items
rows = [[9, "x"], [1, "y"]]
print(rows[0])When items are heavy, moving them is costly. Selection sort moves each item at most once.
Not stable by default
rows = [[2, "a"], [2, "b"], [1, "c"]]
print(rows[0] == rows[1])A swap can jump an equal item past another. Plain selection sort is not stable.
The scan is the cost
nums = [4, 1, 3, 2]
print(len(nums) - 1)Each round scans the remaining items once. That scan, not the swap, is the work.
Words this lesson uses
Each one is defined here on this site. Open the entry for the full definition and the other words it points at.
← Insertion sort
Previous Lesson
Insertion sort