A leaderboard after every match
An online game shows a leaderboard of the top players. Every time a match ends, scores change and the board must be put back in order.
With a million players, a slow way of sorting would keep everyone waiting. Today you meet three ways to sort, and see how different they are.
By the end of this lesson
Note
I can sort a list with bubble, insertion and merge sort.
Key words
| Word | What it means |
|---|---|
| Sort | to put items in order |
| Swap | to make two items change places |
| Pass | one trip through the whole list |
| Bubble sort | swapping neighbours again and again until nothing moves |
| Insertion sort | sliding each new item left into its place |
| Merge sort | splitting a list up, then joining sorted parts |
The cells students fill in are left blank in this preview.
Bubble sort swaps neighbours
Bubble sort walks along the list comparing each pair of neighbours. If a pair is the wrong way round, it swaps them.
After the first pass the biggest item has bubbled to the end. After the second, the two biggest are in place. So each pass can stop one place earlier than the last.
Watch bubble sort pass by pass
# Bubble sort: compare neighbours and swap them if they are the wrong way round.
scores = [5, 1, 4, 2, 8]
for done in range(len(scores) - 1):
for place in range(len(scores) - 1 - done):
if scores[place] > scores[place + 1]:
bigger = scores[place]
scores[place] = scores[place + 1]
scores[place + 1] = bigger
print("after pass", done + 1, ":", scores)
# Change scores to [9, 7, 5, 3, 1], the worst order.
# How many passes change something now?
A common mistake
Warning
Many people think one pass of bubble sort sorts the list. One pass only carries the biggest item to the end. A list in reverse order needs a pass for almost every item, so keep passing until a whole pass makes no swap.
Insertion sort slides items into place
Insertion sort works like sorting a hand of cards. The left part of the list is kept in order.
Take the next item and slide it left past every bigger item. Drop it where it fits. On a list that is nearly sorted, most items hardly move, so insertion sort is very quick there.
Watch insertion sort place each card
# Insertion sort: take the next card and slide it left into place.
cards = [7, 3, 9, 2, 6]
for place in range(1, len(cards)):
card = cards[place]
spot = place
while spot > 0 and cards[spot - 1] > card:
cards[spot] = cards[spot - 1]
spot = spot - 1
cards[spot] = card
print("placed", card, ":", cards)
# Change cards to [1, 2, 3, 5, 4], nearly sorted.
# How many cards have to move?
Merge sort splits, then merges
Merge sort splits the list into halves, then halves again, until every part holds one item. One item is always sorted.
Then it merges neighbours. To merge two sorted lists, compare their first items and take the smaller. Repeat until both are empty. Each round of merging doubles the size of the sorted parts.
Worked example: merge sort on eight numbers
| Stage | The parts |
|---|---|
| Start | [6, 2, 8, 4, 7, 1, 5, 3] |
| Split down to single items | [6] [2] [8] [4] [7] [1] [5] [3] |
| Merge pairs | [2, 6] [4, 8] [1, 7] [3, 5] |
| Merge into fours | [2, 4, 6, 8] [1, 3, 5, 7] |
| Merge into one | [1, 2, 3, 4, 5, 6, 7, 8] |
The cells students fill in are left blank in this preview.
The last merge, step by step
# Merge two sorted lists into one sorted list.
left = [2, 4, 6, 8]
right = [1, 3, 5, 7]
merged = []
a = 0
b = 0
while a < len(left) and b < len(right):
if left[a] <= right[b]:
merged.append(left[a])
a = a + 1
else:
merged.append(right[b])
b = b + 1
# One list has run out: copy what is left of the other.
merged = merged + left[a:] + right[b:]
print(merged)
# Change right to [9, 10]. Why does the last line matter now?
Sorting in the lab
Python already has a sort built in, sorted. It is a careful mix of merge sort and insertion sort.
The first Run sorts a short list. The second times sorted on 10,000 jumbled numbers. Then type the cell below into your notebook. It races your own bubble sort against sorted on 2,000 numbers.
Sort a short list in the lab
docker exec jupyter python3 -c "print(sorted([31, 7, 19, 2, 25]))"Shown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
Time sorted on 10,000 numbers
docker exec jupyter python3 -m timeit -s "import random" -s "data = random.Random(1).sample(range(100000), 10000)" "sorted(data)"Shown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
Type this in your notebook: a race
import random
def bubble_sort(items):
items = list(items)
for done in range(len(items) - 1):
for place in range(len(items) - 1 - done):
if items[place] > items[place + 1]:
bigger = items[place]
items[place] = items[place + 1]
items[place + 1] = bigger
return items
# The same 2,000 numbers every time, in a jumbled order.
numbers = random.Random(7).sample(range(10000), 2000)
print(bubble_sort(numbers) == sorted(numbers))
%timeit bubble_sort(numbers)
%timeit sorted(numbers)
Going further: count the swaps
Add a counter to bubble_sort in your notebook that goes up by one at every swap. Sort [5, 1, 4, 2, 8], then [9, 7, 5, 3, 1].
Then try a list already in order. Which order makes bubble sort do the most swaps, and why?