Sort once, search many
Show on a big screenA conductor, who sells bus tickets, gets many fare questions. Should the board be sorted first?
- 3 questions: walk 21, sort then halve 30.
- 5 questions: walk 35, sort then halve 36.
- 6 questions: walk 42, sort then halve 39.
- 12 questions: walk 84, sort then halve 57.
The rule
It depends on the number of questions. On this board, sorting first needs fewer comparisons from 6 questions.
Walking needs no order. Halving needs the list sorted first. Sorting costs comparisons, paid once. Count the questions before you pay for order.
Take a board of 7 fares. A walk needs at most 7 comparisons per question. Halving needs at most 3.
Sorting 7 fares costs 21 comparisons in the worst case, paid once. That is 7 × 6 ÷ 2.
Count the worst case. Each question then saves 4 comparisons, 7 minus 3. After 5 questions, 20 are saved, less than the 21. After 6 questions, 24 are saved, more than the 21.
| Plan | Comparisons |
|---|---|
| Walk every time | 7 × q |
| Sort once, then halve | 21 + 3 × q |
At 5 questions, walking costs 35 and sorting first costs 36. At 6 questions, walking costs 42 and sorting first costs 39.
There is a third plan: halve without sorting. It is cheap, but it can be wrong. The six sample questions are 18, 9, 36, 15, 24 and 21. On the unsorted board, halving answers 2 of them wrongly.
Slide to the fewest questions where sorting wins.
Loading lab…
Try the lab to finish this lesson.