🚀 Alguni Start learning

Unit 28: Sorting

Seven ways to put things in order.

Unit 28 of 31 in Python for kids. Its 8 lessons are Bubble Sort, Selection Sort, Insertion Sort, Merge Sort, Quick Sort, Counting Sort, Radix Sort and Sorting Master — below is everything each one explains, and a question or two from it to try.

Every sample on this page was run through real Python before it shipped, and prints exactly what it says it prints.

This unit opens with a fortnight’s trial of everything — no card needed — or with a family plan, bought in the iPhone app. The first two units of every track are free for ever. Try it in the app.

🫧 Bubble Sort

Swap any neighbours in the wrong order

Bubble sort walks the list comparing each pair side by side, swapping them when they are the wrong way round. The biggest value bubbles up to the end on the first pass.

Python

items = [3, 1, 2]
for i in range(len(items) - 1):
    if items[i] > items[i + 1]:
        items[i], items[i + 1] = items[i + 1], items[i]
print(items)

It prints

[1, 2, 3]

Swapping two values in one line

Python swaps without needing a spare box. Both sides are worked out first, so nothing gets lost.

Python

a = 1
b = 2
a, b = b, a
print(a, b)

It prints

2 1

One pass is not enough

Each pass only guarantees one more value has reached its place, so you need a pass for each item. Watch it settle.

Python

items = [4, 3, 2, 1]
for pass_number in range(len(items)):
    for i in range(len(items) - 1):
        if items[i] > items[i + 1]:
            items[i], items[i + 1] = items[i + 1], items[i]
    print(items)

It prints

[3, 2, 1, 4]
[2, 1, 3, 4]
[1, 2, 3, 4]
[1, 2, 3, 4]

Stopping early when it is already sorted

If a whole pass makes no swaps, the list is in order and you can stop. That is what makes bubble sort quick on nearly-sorted data — and it is its only real virtue.

Python

def bubble(items):
    passes = 0
    while True:
        swapped = False
        passes = passes + 1
        for i in range(len(items) - 1):
            if items[i] > items[i + 1]:
                items[i], items[i + 1] = items[i + 1], items[i]
                swapped = True
        if not swapped:
            return passes

print(bubble([1, 2, 3, 4]))
print(bubble([4, 3, 2, 1]))

It prints

1
4

Try it yourself

Why is bubble sort slow on a big list?

  • It uses too much memory
  • It compares every pair on every pass, so the work grows with the square of the length
  • It cannot sort numbers
  • It is not slow

Answer it in the app

🎯 Selection Sort

Find the smallest, put it first

Selection sort looks through everything left, finds the smallest, and swaps it into place. Then it does the same for the rest.

Python

items = [3, 1, 2]
for start in range(len(items)):
    smallest = start
    for i in range(start + 1, len(items)):
        if items[i] < items[smallest]:
            smallest = i
    items[start], items[smallest] = items[smallest], items[start]
    print(items)

It prints

[1, 3, 2]
[1, 2, 3]
[1, 2, 3]

It remembers where, not what

The inner loop tracks the *position* of the smallest so far, not the value — because it needs to know where to swap from.

Python

items = [7, 2, 9, 4]
smallest = 0
for i in range(1, len(items)):
    if items[i] < items[smallest]:
        smallest = i
print(smallest)
print(items[smallest])

It prints

1
2

Very few swaps, just as many comparisons

Selection sort makes at most one swap per position — far fewer than bubble sort. But it still compares everything against everything, so it is no faster overall.

Python

def selection(items):
    swaps = 0
    comparisons = 0
    for start in range(len(items)):
        smallest = start
        for i in range(start + 1, len(items)):
            comparisons = comparisons + 1
            if items[i] < items[smallest]:
                smallest = i
        if smallest != start:
            items[start], items[smallest] = items[smallest], items[start]
            swaps = swaps + 1
    return swaps, comparisons

print(selection([4, 3, 2, 1]))

It prints

(2, 6)

Try it yourself

When would you prefer selection sort over bubble sort?

  • When the list is huge
  • When swapping is expensive — it makes far fewer swaps
  • When the list is already sorted
  • Never, they are identical

Answer it in the app

🃏 Insertion Sort

The way you sort playing cards

Insertion sort keeps a sorted part at the front. It takes the next item and slides it back until it sits in the right place — exactly what you do holding a hand of cards.

Python

items = [3, 1, 2]
for i in range(1, len(items)):
    value = items[i]
    j = i - 1
    while j >= 0 and items[j] > value:
        items[j + 1] = items[j]
        j = j - 1
    items[j + 1] = value
    print(items)

It prints

[1, 3, 2]
[1, 2, 3]

Sliding, not swapping

It copies each bigger value one place to the right to open a gap, then drops the held value in. That is fewer moves than swapping over and over.

Python

items = [1, 3, 5, 2]
value = items[3]
j = 2
while j >= 0 and items[j] > value:
    items[j + 1] = items[j]
    j = j - 1
items[j + 1] = value
print(items)

It prints

[1, 2, 3, 5]

It is genuinely fast on nearly-sorted lists

If everything is almost in place, each item slides hardly at all. This is why real sorting libraries use insertion sort for small or nearly-ordered chunks.

Python

def insertion(items):
    moves = 0
    for i in range(1, len(items)):
        value = items[i]
        j = i - 1
        while j >= 0 and items[j] > value:
            items[j + 1] = items[j]
            j = j - 1
            moves = moves + 1
        items[j + 1] = value
    return moves

print(insertion([1, 2, 3, 4, 5]))
print(insertion([5, 4, 3, 2, 1]))

It prints

0
10

Try it yourself

Which sort does almost no work on an already-sorted list?

  • Selection sort
  • Insertion sort
  • They all take the same time
  • None of them

Answer it in the app

🧬 Merge Sort

Joining two sorted lists is easy

Start with this piece. Given two lists that are each already sorted, you can zip them into one sorted list by always taking whichever front item is smaller.

Python

def merge(left, right):
    out = []
    i = 0
    j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            out.append(left[i])
            i = i + 1
        else:
            out.append(right[j])
            j = j + 1
    return out + left[i:] + right[j:]

print(merge([1, 4], [2, 3]))

It prints

[1, 2, 3, 4]

Split until there is nothing to sort

Merge sort halves the list until each piece holds one item — which is sorted by definition — then merges the pieces back together in order.

Python

def merge(left, right):
    out = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            out.append(left[i])
            i = i + 1
        else:
            out.append(right[j])
            j = j + 1
    return out + left[i:] + right[j:]

def merge_sort(items):
    if len(items) <= 1:
        return items
    middle = len(items) // 2
    return merge(merge_sort(items[:middle]), merge_sort(items[middle:]))

print(merge_sort([5, 2, 8, 1, 9]))

It prints

[1, 2, 5, 8, 9]

Watch it split

Each level halves the pieces. Five items split into two levels of halving before every piece is on its own.

Python

def show(items, depth=0):
    print("  " * depth + str(items))
    if len(items) <= 1:
        return
    middle = len(items) // 2
    show(items[:middle], depth + 1)
    show(items[middle:], depth + 1)

show([5, 2, 8, 1])

It prints

[5, 2, 8, 1]
  [5, 2]
    [5]
    [2]
  [8, 1]
    [8]
    [1]

Try it yourself

Why is merge sort so much faster than bubble sort on a big list?

  • It uses less memory
  • Halving means only about log n levels, and each level costs one pass
  • It never compares anything
  • It is not faster

What is merge sort’s one real drawback?

  • It cannot sort words
  • It needs extra space to hold the merged pieces
  • It only works on even-length lists
  • It is unstable

Answer them in the app

⚡ Quick Sort

Pick one, split around it

Quick sort picks a pivot, puts everything smaller on the left and everything bigger on the right, then sorts each side the same way. The pivot is already home.

Python

items = [5, 2, 8, 1, 9]
pivot = items[0]
rest = items[1:]
smaller = [n for n in rest if n < pivot]
bigger = [n for n in rest if n >= pivot]
print(smaller, pivot, bigger)

It prints

[2, 1] 5 [8, 9]

The whole thing in five lines

Because both sides get the same treatment, quick sort is beautifully short when written with comprehensions.

Python

def quick_sort(items):
    if len(items) <= 1:
        return items
    pivot = items[0]
    rest = items[1:]
    smaller = [n for n in rest if n < pivot]
    bigger = [n for n in rest if n >= pivot]
    return quick_sort(smaller) + [pivot] + quick_sort(bigger)

print(quick_sort([5, 2, 8, 1, 9]))

It prints

[1, 2, 5, 8, 9]

A bad pivot ruins it

If the pivot is always the smallest value, one side is empty every time and nothing gets halved — exactly the problem sorted input caused for the search tree in unit 25. Real quick sorts pick the pivot more carefully.

Python

def depth(items, d=1):
    if len(items) <= 1:
        return d
    pivot = items[0]
    rest = items[1:]
    smaller = [n for n in rest if n < pivot]
    bigger = [n for n in rest if n >= pivot]
    return max(depth(smaller, d + 1), depth(bigger, d + 1))

print(depth([1, 2, 3, 4, 5]))
print(depth([3, 1, 4, 2, 5]))

It prints

5
3

Try it yourself

Why use >= rather than > when building the bigger side?

  • To make it faster
  • So values equal to the pivot are kept, instead of being dropped
  • It makes no difference
  • To sort them backwards

What does this print?

Python

items = [4, 7, 4, 1]
pivot = items[0]
rest = items[1:]
print([n for n in rest if n < pivot])
print([n for n in rest if n >= pivot])

Answer them in the app

🗳️ Counting Sort

Sorting without comparing anything

Every sort so far asked "is this bigger than that?". Counting sort never does. It just counts how many of each value there are, then writes them out in order.

Python

items = [2, 0, 1, 2, 0]
counts = [0, 0, 0]
for n in items:
    counts[n] = counts[n] + 1
print(counts)

It prints

[2, 1, 2]

Then just read the tallies back

Walk the counts in order and write each value out as many times as it appeared. The list comes out sorted, and nothing was ever compared.

Python

def counting_sort(items, top):
    counts = [0] * (top + 1)
    for n in items:
        counts[n] = counts[n] + 1
    out = []
    for value in range(top + 1):
        for _ in range(counts[value]):
            out.append(value)
    return out

print(counting_sort([2, 0, 1, 2, 0], 2))

It prints

[0, 0, 1, 2, 2]

Where it wins, and where it is silly

Sorting a million test scores from 0 to 100 is perfect for it — one pass, 101 buckets. Sorting three numbers up to a million would need a million buckets to hold three values.

Python

print("1,000,000 scores, 0-100  -> 101 buckets, brilliant")
print("3 numbers up to 1,000,000 -> 1,000,001 buckets, silly")

It prints

1,000,000 scores, 0-100  -> 101 buckets, brilliant
3 numbers up to 1,000,000 -> 1,000,001 buckets, silly

Try it yourself

What does counting sort need that the others do not?

  • A sorted list to start with
  • To know the range of values, and a bucket for every possible one
  • More comparisons
  • Recursion

What does this print?

Python

counts = [0] * 4
for n in [3, 1, 3, 0]:
    counts[n] = counts[n] + 1
print(counts)

Answer them in the app

🔟 Radix Sort

One digit at a time

Radix sort sorts numbers by their last digit, then their next digit, and so on. Because each round keeps the previous order among equals, the numbers end up fully sorted.

Python

items = [170, 45, 75, 90]
buckets = [[] for _ in range(10)]
for n in items:
    buckets[n % 10].append(n)
for digit in range(10):
    if buckets[digit]:
        print(digit, buckets[digit])

It prints

0 [170, 90]
5 [45, 75]

Collect and repeat

Pour the buckets back into one list in bucket order, then do it again for the tens digit. // 10 % 10 picks out the tens.

Python

items = [170, 45, 75, 90]

place = 1
while place <= 100:
    buckets = [[] for _ in range(10)]
    for n in items:
        buckets[(n // place) % 10].append(n)
    items = []
    for bucket in buckets:
        for n in bucket:
            items.append(n)
    print(items)
    place = place * 10

It prints

[170, 90, 45, 75]
[45, 170, 75, 90]
[45, 75, 90, 170]

Stopping when you run out of digits

Keep going until the biggest number has no digits left at that place. This is the whole algorithm.

Python

def radix_sort(items):
    items = list(items)
    place = 1
    while max(items) // place > 0:
        buckets = [[] for _ in range(10)]
        for n in items:
            buckets[(n // place) % 10].append(n)
        items = []
        for bucket in buckets:
            for n in bucket:
                items.append(n)
        place = place * 10
    return items

print(radix_sort([170, 45, 75, 90, 802, 24, 2, 66]))

It prints

[2, 24, 45, 66, 75, 90, 170, 802]

Try it yourself

Why must radix sort start with the LAST digit, not the first?

  • It is faster that way
  • So that later rounds can reorder without destroying the work already done
  • It does not matter
  • Because of how % works

Which values does this version of radix sort NOT handle?

  • Big numbers
  • Negative numbers
  • Numbers with repeats
  • Numbers ending in 0

Answer them in the app

🏆 Sorting Master

Try it yourself

What does this print?

Python

items = [3, 1, 2]
for i in range(len(items) - 1):
    if items[i] > items[i + 1]:
        items[i], items[i + 1] = items[i + 1], items[i]
print(items)

Answer it in the app