Sort your hand of cards

You hold five playing cards. You want them in order, from the smallest to the largest. How do you do it?

Some people swap cards that are in the wrong order, again and again. Others take one card at a time and slide it into the right place. These are two real sorting methods. Computers use them too.

Key words

Word	What it means	Example
Sorting algorithm	A set of steps that puts items in order.
Bubble sort	Compare neighbours and swap them if they are in the wrong order. Repeat in passes.
Insertion sort	Take one item at a time and slide it into its place in the sorted part.
Pass	One trip through the list from start to end.	not the Python word pass
Swap	Two items change places.
Comparison	Checking one value against another.
In order	Smallest first. This is called ascending order.

The cells students fill in are left blank in this preview.

Bubble sort: swap the neighbours

In a bubble sort you go along the list. Compare each item with the one next to it. If they are in the wrong order, swap them.

The biggest item "bubbles" to the end in the first pass. Do more passes. Stop when a whole pass makes no swaps.

Try it: bubble sort

Code: python

numbers = [5, 3, 8, 1]
swapped = True
pass_number = 0

while swapped:
    swapped = False
    pass_number = pass_number + 1
    for i in range(len(numbers) - 1):
        if numbers[i] > numbers[i + 1]:
            temp = numbers[i]
            numbers[i] = numbers[i + 1]
            numbers[i + 1] = temp
            swapped = True
    print("After pass", pass_number, numbers)

# Try [1, 2, 3, 4]. How many passes now?

Worked example: bubble sort

Pass	List at the start	What happens	List at the end
1	5, 3, 8, 1	5 and 3 swap. 5 and 8 stay. 8 and 1 swap	3, 5, 1, 8
2	3, 5, 1, 8	3 and 5 stay. 5 and 1 swap. 5 and 8 stay	3, 1, 5, 8
3	3, 1, 5, 8	3 and 1 swap. The rest stay	1, 3, 5, 8
4	1, 3, 5, 8	No swaps at all. The list is sorted: stop	1, 3, 5, 8

The cells students fill in are left blank in this preview.

Insertion sort: slide into place

In an insertion sort the left part of the list is always sorted. At the start it is just the first item.

Pick the next item. Slide it left, past every bigger item, until it fits. Now the sorted part is one item longer. Repeat until the end.

Worked example: insertion sort

Step	Item picked	What happens	List after the step
Start		The sorted part is just the 5	5, 3, 8, 1
1	3	5 is bigger, so it moves right. 3 goes in front	3, 5, 8, 1
2	8	5 is smaller, so 8 stays where it is	3, 5, 8, 1
3	1	8, 5 and 3 are all bigger and move right. 1 goes at the front	1, 3, 5, 8

The cells students fill in are left blank in this preview.

Try it: insertion sort

Code: python

numbers = [5, 3, 8, 1]

for i in range(1, len(numbers)):
    current = numbers[i]
    position = i - 1
    while position >= 0 and numbers[position] > current:
        numbers[position + 1] = numbers[position]
        position = position - 1
    numbers[position + 1] = current
    print("After picking", current, numbers)

# Try [9, 7, 5, 3, 1].