Stretch tasks Searching and Sorting Algorithms

Round 1: Quiz Blitz

1. It must be sorted On an unsorted list it can give the wrong answer.
2. 1000 The target may be last, or missing, so every item is checked.
3. 16 It starts with the middle item.
4. [3, 7, 2, 9] Swap 7 and 3, leave 7 and 9, swap 9 and 2. The 9 has bubbled to the end.
5. True The swapped flag tells it the list is in order.
6. 7 n items give n minus 1 comparisons.
7. Divide and conquer Split into halves, then combine the sorted pieces.
8. A list of one item is already sorted Merging two sorted lists is then easy.
9. It needs extra memory for the sub lists Bubble sort works in place with almost no extra memory.
10. False It can discard the half that holds the target, and return the wrong answer.
11. The list is small; The list is unsorted and searched only once It needs no sorting, and on a small list it is quick enough.
12. [1, 2, 4, 6, 8] Compare the front items and take the smaller each time.

Round 2: Quick Fire

1. • Each comparison discards half the remaining items
   • Linear search rules out only one item per comparison
   Model answer

   Each binary search comparison discards half of the items that are left, so a million items need about 20 comparisons. Linear search checks each item in turn, ruling out only one item per comparison.

2. • It holds the sub lists separately, needing extra memory
   • Bubble sort works in place, needing almost no extra memory
   Model answer

   Merge sort has to hold the sub lists separately while it merges them, so it needs extra memory roughly the size of the original list. Bubble sort sorts in place, needing room for only one temporary variable.

3. • It records whether any swap happened during a pass
   • If a pass makes no swaps, the algorithm stops early
   Model answer

   The flag records whether any swap was made during a pass. If a whole pass makes no swaps, the list must be in order, so the algorithm stops instead of making pointless extra passes.

4. • A pass is one complete run through the list
   • A comparison tests two neighbouring values, and a pass makes n - 1 of them
   Model answer

   A pass is one complete run through the list. A comparison is a single test of two adjacent values, and one pass over n items makes n minus 1 comparisons.

Round 3: Big Think

1. • Linear search checks each code in turn
   • So it may need 50,000 comparisons
   • Linear search works on a list in any order
   • Binary search checks the middle and discards half each time
   • So it needs only about 16 comparisons
   • The codes are already sorted, so its precondition costs nothing
   • Over thousands of searches the saving is enormous
   • A justified choice of binary search
   Model answer

   Linear search checks each code in turn from the start, so in the worst case it makes 50,000 comparisons, although it works on a list in any order. Binary search checks the middle code and discards half of the remaining codes with each comparison, so it needs at most about 16 comparisons. Its precondition, a sorted list, costs nothing here, because the codes are already sorted. Over thousands of searches a day the saving is enormous, giving faster responses and less work for the server. I would choose binary search.

2. • The list is split in half again and again
   • Until each sub list holds a single item
   • Sorted pieces are combined by taking the smaller front item
   • Merge sort is much faster on large lists
   • Bubble sort makes many slow passes
   • Merge sort needs extra memory, while bubble sort works in place
   • Bubble sort is easier to write, and good on nearly sorted data
   • A conclusion weighing the two
   Model answer

   Merge sort splits the list in half again and again: [6, 2] and [8, 4, 1], then [6], [2], [8] and [4, 1], until every sub list holds a single item, which is already sorted. It then combines pairs of sorted lists by comparing their first items and taking the smaller each time: [2, 6], then [1, 4], then [1, 4, 8], and finally [1, 2, 4, 6, 8]. Compared with bubble sort, merge sort is much faster on large lists, because it needs only about log n rounds, whereas bubble sort makes many slow passes. However, merge sort needs extra memory for the sub lists, while bubble sort works in place and is easier to write. For five items either is fine, so on balance merge sort only wins clearly when the list is large.

This or That

1. Linear search Binary search needs a sorted list, and sorting first would cost more than the search saves.
2. Bubble sort Bubble sort finishes in a pass or two, and sorts in place with almost no extra memory.
3. Binary search Linear search rules out just one item per comparison.
4. 9 A pass compares neighbours, so n items give n minus 1 comparisons.
5. Bubble sort That bubbling up is where the name comes from.
6. No: down to single items Division continues until every sub list holds exactly one item.
7. No: it needs more memory Merge sort holds the sub lists separately, so it needs extra memory.
8. Linear search Linear search starts at the front. Binary search starts in the middle.

Memory Match

• A 3 Linear search: Checks each item in turn
• B 5 Binary search: Checks the middle, discards half
• C 1 Bubble sort: Swaps neighbours until a pass has no swaps
• D 6 Merge sort: Splits to single items, then combines in order
• E 2 Divide and conquer: Solve smaller copies of a problem, then combine
• F 4 In place: Uses almost no extra memory

Sort It

1. Linear search Works on an unsorted list Linear search makes no demands on the data.
2. Linear search Checks each item in turn from the start That is linear search.
3. Linear search Worst case of n comparisons Linear search may have to check every item.
4. Bubble sort Stops when a pass makes no swaps Bubble sort's swapped flag.
5. Bubble sort Sorts in place, with almost no extra memory Bubble sort needs just one temporary variable.
6. Merge sort Needs extra memory to hold the sub lists Merge sort's main cost.
7. Merge sort Splits the list until each piece holds one item That is merge sort's divide step.
8. Binary search Needs the list to be sorted first Binary search's precondition.
9. Merge sort Combines sorted pieces by taking the smaller front item That is merge sort's merge step.
10. Binary search Discards half the remaining items each time That is binary search.
11. Binary search About 16 comparisons for 50,000 items Halving 50,000 takes about 16 steps.
12. Bubble sort Swaps neighbours that are the wrong way round That is bubble sort.