Project: sort the readings

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

F5.10AlgorithmsGCSE25 min

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:

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.

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.

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.