Sorting and Searching Algorithms
Algorithm Design and Problem Solving
Searching and sorting are often combined in real programs:
| Situation | Strategy |
|---|---|
| One-off search in unsorted data | Linear search; sorting first would be wasted effort |
| Constant additions, occasional searches | Stay with linear search, or maintain order as items arrive |
| Sorted data displayed to a user | Bubble sort or another sort first, then display |
Common exam question
Sorting parallel arrays in the 15-mark program
Question: Write a program that sorts two arrays sharing an index (names and their values) into ascending or descending order of value, then outputs the top two or three (15 marks, shared with the other requirements).
Set in 2 of the 17 papers. The scheme names nested iteration and sorting as the techniques for this requirement, and its example answer is a bubble sort, so write a recognisable one: an outer loop repeating until a pass makes no swap (a flag reset to FALSE each pass), an inner FOR loop from 1 to one less than the number of items, and a comparison of each element with the next. Swap both arrays at once, through two temporary variables, so each name stays with its own value; moving only the values breaks the pairing. For descending order reverse the comparison and swap when the left value is the smaller. Once sorted, the top entries are simply the first elements.
A typical pattern: a school's student records are sorted by surname once when loaded, so they can be displayed in order and scanned quickly.