Worksheet

F5.10 Project: sort the readings

Algorithms · GCSE · about 25 min

What this lesson is about

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

• The brief
• Plan: which algorithms?
• Step 1: the survey
• Step 2: sort records, not numbers
• Step 3: answer questions from sorted data
• Testing

Questions 4 marks in all

1. [1 mark]After sorting survey records nearest first, where is the farthest direction?

   1. AIn the last record
   2. BIn the first record
   3. CIn the middle record
   4. DIt must be searched for

2. [1 mark]The sorted distances are 15, 16, 16, 26, 26, 31, 31, 34, 34, 35, 51, 57. What is the median?

3. [1 mark]To sort records by distance, what does the sort compare?

   1. AThe distance field of each record
   2. BThe whole records
   3. CThe direction field
   4. DThe position in the list

4. [1 mark]Why is any of the three sorts fine for 12 readings?

   1. AWith so few items, the difference in speed is too small to matter
   2. BThey all do exactly the same number of comparisons
   3. COnly merge sort works on records
   4. DTwelve is an even number

The 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)

Plan your program here, then type it in and press Run.

Do it on the robot
www.bugbotlab.com/learn/f5-10-project-sort-the-readings/
The simulator checks it and tells you when it passes. Nothing to install, no account.

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.