Stretch tasks Searching and Sorting Algorithms

Round 1: Quiz Blitz

1. It must be sorted Binary search discards halves, which only works if the order tells you which half to keep.
2. Compares adjacent items and swaps them if they are in the wrong order After each pass, the largest remaining value has bubbled to the end.
3. True It stores the sub-lists separately. Bubble sort works in place.
4. 50 In the worst case the item is last, or missing, so every item is checked.
5. Find the middle item → If it is the target, stop → Discard the half that cannot contain the target → Repeat on the remaining half Each comparison removes half of the remaining items.
6. Insertion sort Most items need almost no movement, so insertion sort is very fast here.
7. [3, 5, 1, 8] Swap 5 and 3, leave 5 and 8, swap 8 and 1. The largest, 8, is now at the end.
8. 16 The middle item. 23 is larger than 16, so the lower half is discarded.
9. Bubble sort; Insertion sort Merge sort needs extra memory for its sub-lists.
10. False Linear search works on any list. Binary search is the one that needs sorted data.
11. Merge sort Divide, then merge: a list of one item is already sorted.
12. linear search Linear search is simple, and works on any list, but is slow on large ones.

Round 2: Quick Fire

1. • Each comparison removes half of the remaining items
   • Linear search removes only one item with each comparison
   Model answer

   Each comparison in a binary search removes half of the remaining items, whereas a linear search checks each item in turn, removing only one at a time.

2. • It builds a sorted section at the start of the list
   • Each next item is put into its correct place in that section, shifting larger items along
   Model answer

   Insertion sort builds a sorted section at the start of the list. It takes the next unsorted item and inserts it into its correct position in the sorted section, shifting larger items along to make room.

3. • Advantage: much faster on large lists
   • Disadvantage: uses more memory, and is more complex
   Model answer

   Advantage: merge sort is much faster on large lists. Disadvantage: it uses more memory, because the sub-lists must be stored separately.

4. • Each pair of adjacent items is compared
   • They are swapped if in the wrong order, so the largest ends up at the end
   Model answer

   Each pair of adjacent items is compared in turn, and swapped if they are in the wrong order. By the end of the pass, the largest remaining value has moved to the end.

Round 3: Big Think

1. • Compare with the middle item first
   • 23 is larger, so discard the lower half
   • The next middle item is 42: 23 is smaller, so discard the upper half
   • Found on the third comparison
   Model answer

   Check the middle item, 16. 23 is larger, so discard the lower half, leaving 23, 42 and 50. The middle of those is 42. 23 is smaller, so discard the upper half, leaving 23. The middle item is now 23, so it is found, on the third comparison.

2. • Binary search
   • Because the list is already sorted
   • Each comparison halves the remaining items
   • So about 21 comparisons, instead of up to 2 million
   • Linear search could check every item, which is too slow
   • If unsorted: merge sort
   • Merge sort is fast on large lists
   • But it needs more memory
   Model answer

   I recommend binary search, because the list is already sorted by product code. Each comparison halves the remaining items, so about 21 comparisons are enough to find any product, whereas a linear search could check every item, up to 2 million comparisons. If the list were not sorted, I would use merge sort first, because it is much faster than bubble sort on large lists, although it uses more memory.

This or That

1. Linear search Binary search needs sorted data. Linear search checks every item, so order does not matter.
2. Merge sort Merge sort divides until each list has one item, then merges them in order.
3. Insertion sort You slot each new card into place among the sorted ones.
4. Bubble sort Bubble sort works in place. Merge sort needs memory for its sub-lists.
5. After a pass with no swaps A pass with no swaps proves the list is in order.
6. Unreliable answers Discarding halves only works when the order tells you which half to keep.
7. Half of the remaining items That is why it is so much faster on large lists.
8. Merge sort Merge sort's performance is consistent. Bubble sort slows down badly on jumbled lists.

Memory Match

• A 4 Linear search: Checks each item in turn
• B 5 Binary search: Halves a sorted list each time
• C 6 Bubble sort: Swaps adjacent pairs in the wrong order
• D 2 Insertion sort: Places each item into a sorted section
• E 1 Merge sort: Splits into single items, then merges
• F 3 In place: Sorts using almost no extra memory

Sort It

1. Binary search Halves the search area with every comparison That is why binary search is so fast.
2. Merge sort Splits the list until every list has one item Merge sort divides, then merges.
3. Insertion sort Like sorting a hand of playing cards Each new card is slotted into place.
4. Merge sort Fast and consistent on large, jumbled lists Merge sort's performance does not depend on how jumbled the list is.
5. Merge sort Uses extra memory to hold the sub-lists Merge sort's speed costs memory.
6. Bubble sort After the first pass, the largest value is at the end The largest value bubbles to the end on every pass.
7. Binary search Checks the middle item first Binary search always compares with the middle.
8. Insertion sort Builds a sorted section at the start of the list Insertion sort grows a sorted section.
9. Binary search Only works on a sorted list Binary search needs order to know which half to discard.
10. Insertion sort Very efficient when the list is nearly sorted Most items barely need to move.
11. Bubble sort Compares adjacent pairs and swaps them That is how bubble sort works.
12. Bubble sort Stops after a pass with no swaps No swaps means the list is sorted.