Insertion sort

Building a sorted part one item at a time, on the robot's readings.

F5.8AlgorithmsGCSE15 min

Insertion sort is how most people sort a hand of cards: pick up the cards one at a time, and slide each new card into the right place among the ones you already hold. The part of the list you have dealt with is always sorted, and it grows by one item each step.

The algorithm

1. The first item on its own is a sorted part of one.
2. Take the next item from the unsorted part.
3. Move it left, past every item in the sorted part that is bigger than it.
4. Put it down in the gap. The sorted part is now one item longer.
5. Repeat until no unsorted items are left.

Watch it on [31, 15, 51, 20]. The bar | marks where the sorted part ends:

51 did not move at all, because it was already bigger than everything before it.

In Python

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

items = [31, 15, 51, 20, 41, 19]
for i in range(1, len(items)):
    current = items[i]
    j = i - 1
    while j >= 0 and items[j] > current:
        items[j + 1] = items[j]      # shift the bigger item one place right
        j = j - 1
    items[j + 1] = current           # drop the item into the gap
    print("after inserting", current, ":", items)
print("sorted:", items)

Run this in the simulator

The while walks left through the sorted part, shifting each bigger item one place to the right to open a gap. It stops at the first item that is not bigger, or at the start of the list, and current goes into the gap.

Sorting the robot's readings

The robot looks in eight directions, then sorts the distances nearest first:

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

readings = []
for i in range(8):
    readings.append(distance())
    turn_right(30, angle=45)
print("as measured:", readings)

for i in range(1, len(readings)):
    current = readings[i]
    j = i - 1
    while j >= 0 and readings[j] > current:
        readings[j + 1] = readings[j]
        j = j - 1
    readings[j + 1] = current
print("nearest first:", readings)

Run this in the simulator

Bubble sort or insertion sort?

Both are simple, and both need about n × n steps in the worst case, so both are slow for big lists. Insertion sort usually does fewer comparisons, and it is very quick on a list that is nearly sorted, because each new item only moves a little way. That makes it a good choice for adding a few new readings to a list that is already in order.

Task: sort the survey

Look in eight directions, 45 degrees apart, recording distance() in a list. Sort the list with insertion sort, written yourself (no sort or sorted), printing the list after each insertion. Finally print sorted: <the list>.

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

readings = []
for i in range(8):
    readings.append(distance())
    turn_right(30, angle=45)

Challenges

1. Count how many items were shifted in total. Try it on a list that is already sorted, and one in reverse order.
2. Sort a list of names alphabetically with insertion sort.
3. Keep a list sorted as you build it: insert each new reading into its place as soon as it is measured, instead of sorting at the end.