Project: sort the readings

Survey the room, sort the records, answer questions from sorted data, and choose the algorithms.

F5.10AlgorithmsGCSE25 min

Do this lesson in the simulator

Print it: worksheet (PDF) · answers (PDF) · as a web page

A robot that knows where the open space is can plan where to go. In this project BugBot surveys the room in twelve directions, sorts its readings with an algorithm you write, uses the sorted data to answer questions about the room, and heads for the most open direction. You will choose the algorithms, and justify the choice.

The brief

The robot looks in 12 directions, 30 degrees apart, and stores each look as a record with a direction and a distance. It sorts the records from nearest to farthest using a sorting algorithm you write. Then it prints the distances in order, the median distance (halfway along the sorted list), and the farthest direction. Finally it turns to face the farthest direction and beeps.

Plan: which algorithms?

Before coding, decide, and write down why:

Job Choice Why
sort 12 records by distance bubble, insertion or merge sort 12 items is short, so a simple sort is fine; merge sort would also work
find the farthest the last record once sorted sorting has already done the work
find the median the middle record once sorted the middle of a sorted list

With only twelve items, any of the sorts is fast enough. Pick one you can write correctly and explain. If the robot took a thousand readings, the choice would matter, and merge sort would be the one to justify.

Step 1: the survey

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

survey = []
for i in range(12):
    survey.append({"direction": i * 30, "distance": distance()})
    turn_right(30, angle=30)
for r in survey:
    print(r)

Run this in the simulator

Step 2: sort records, not numbers

The sorts in this module compared numbers. To sort records, compare one field of each record, and move the whole record:

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

survey = [{"direction": 0, "distance": 31.0}, {"direction": 30, "distance": 36.5},
          {"direction": 60, "distance": 45.2}, {"direction": 90, "distance": 51.0}]

swapped = True
while swapped:
    swapped = False
    for i in range(len(survey) - 1):
        if survey[i]["distance"] < survey[i + 1]["distance"]:      # this sorts farthest first
            survey[i], survey[i + 1] = survey[i + 1], survey[i]
            swapped = True
for r in survey:
    print(r)

Run this in the simulator

This made-up survey is sorted farthest first, the opposite of what the brief asks, so you can see the comparison is the only thing that decides the order. Flip it for the task.

The four made-up records before and after the sort: each record moves as a whole, direction and distance together, and only the distance decides the orderbeforeafter: farthest first0°31.0 cm30°36.5 cm60°45.2 cm90°51.0 cm90°51.0 cm60°45.2 cm30°36.5 cm0°31.0 cmdirectiondistance: comparedmoves with it
The comparison looks only at the green distance, but the swap moves the whole record, so each direction stays with its own distance. Here the made-up survey ends farthest first, because the comparison uses <.

Step 3: answer questions from sorted data

Once the records are sorted nearest first:

  • the farthest direction is the last record, survey[-1];
  • the median is the middle: with 12 records, the average of the 6th and 7th distances, survey[5] and survey[6];
  • the nearest is the first, survey[0].

Sorting once turns three separate searches into three look-ups. That is often why data is sorted in the first place.

Twelve records sorted nearest first: the nearest is index 0, the median is the average of indexes 5 and 6, and the farthest is index 11, the last01234567891011nearestfarthestsurvey[-1]survey[0]survey[5] and survey[6]median: the average of these twodistances get bigger along the list6 below, 6 above
Once the list is sorted, each answer is found by its place alone, with no search. With an even number of records there is no single middle one, so the median is halfway between the 6th and the 7th.

Testing

Test the sort on the made-up survey first, where you can check the order by eye. Then test on a list that is already sorted, and one in reverse order: a sort that fails on either has a bug in its loop limits.

Task: sort the readings

Do the survey from the brief. Sort the records nearest first with a sorting algorithm you write (no sort or sorted). Print one line sorted: followed by the distances in order, then median: <cm> cm and farthest: <degrees> degrees. Turn to face the farthest direction and beep.

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

survey = []
for i in range(12):
    turn_right(30, angle=30)

Challenges

  1. Sort with a different algorithm from the one you used, and check both give the same order.
  2. Count the comparisons your sort made, and compare with the other sorts from this module on the same survey.
  3. Use binary search on the sorted distances to find whether any direction has exactly a given distance.