Stretch tasks Sorting Algorithms

Round 1: Quiz Blitz

1. Adjacent pairs of items It swaps each adjacent pair that is in the wrong order.
2. When a whole pass makes no swaps A pass with no swaps proves the list is in order.
3. 5 At most n minus 1: once 5 items are in place, the last one has nowhere else to be.
4. [3, 1, 5, 8] Pass 1 gives [3, 5, 1, 8]. Pass 2 swaps 5 and 1, giving [3, 1, 5, 8].
5. True It holds the sub-lists in memory while merging. Bubble sort works in place.
6. Without it, one of the two values would be overwritten temp ← a, a ← b, b ← temp keeps both values safe.
7. Every sub-list has one item A list of one item is already sorted, so all the work happens in the merging.
8. It sorts in place, using little extra memory; It is simple to write Simple and memory-light, but slow on large lists.
9. [1, 2, 3, 5, 7, 9] Keep taking the smaller of the two front items.
10. 100 times longer Bubble sort does roughly n squared comparisons, so 10 x 10 = 100.
11. True A pass with no swaps comes early, and the sort stops.
12. Divide and conquer Split the problem, solve the small parts, combine the results.

Round 2: Quick Fire

1. • It compares adjacent pairs of items
   • It swaps them if they are in the wrong order
   • After each pass the largest remaining item is at the end
   • It stops when a pass makes no swaps
   Model answer

   A bubble sort compares each pair of adjacent items and swaps them if they are in the wrong order. After each pass, the largest remaining item has moved to the end. It stops when a pass is completed with no swaps.

2. • It splits the list in half, again and again
   • Until every sub-list holds a single item
   • Then sub-lists are combined back together in order
   • By repeatedly taking the smaller of the two front items
   Model answer

   It splits the list in half, then halves each half, until every sub-list holds a single item. Then pairs of sub-lists are combined back together in order, by repeatedly comparing the front items and taking the smaller.

3. • Bubble sort: little memory, and simple to write
   • Merge sort: much faster on large lists
   Model answer

   Bubble sort uses very little memory, because it sorts in place. Merge sort is much faster on large lists.

4. • It may need many passes, comparing every adjacent pair each time
   • About n squared comparisons, so ten times the data is a hundred times the work
   Model answer

   It may need many passes, each comparing every adjacent pair, so it does roughly n squared comparisons: ten times as much data means about a hundred times as much work.

Round 3: Big Think

1. • Bubble sort swaps adjacent items in the wrong order
   • It stops when a pass makes no swaps
   • Merge sort splits into single items, then puts them back in order
   • Merge sort is far faster on large lists
   • Bubble sort needs roughly n squared comparisons
   • Bubble sort sorts in place, using little memory
   • Merge sort needs extra memory for the sub-lists
   • Bubble sort is simpler; merge sort is more complex
   • The best choice depends on list size and memory
   Model answer

   Bubble sort repeatedly compares adjacent items and swaps them if they are in the wrong order, stopping when a pass makes no swaps. Merge sort splits the list into halves until every sub-list has one item, then merges them back in order. Merge sort is far faster on large lists, because it halves the problem, whereas bubble sort needs roughly n squared comparisons. But bubble sort sorts in place, using very little memory, while merge sort needs extra memory to hold the sub-lists, and it is more complex to write. Which is better depends on the size of the list and the memory available.

2. • 5 and 3 are compared and swapped
   • 5 and 8 are compared and not swapped
   • 8 ends up in its final position at the end
   • It stops when a whole pass makes no swaps
   Model answer

   5 and 3 are compared and swapped. 5 and 8 are compared and not swapped. 8 and 1 are compared and swapped, giving [3, 5, 1, 8], so 8, the largest value, is now in its final position at the end. The algorithm keeps making passes, and stops when a pass is completed with no swaps.

This or That

1. Bubble sort Bubble sort swaps items inside the original list. Merge sort builds sub-lists.
2. Merge sort Merge sort calls itself on each half.
3. One A one-item list is already sorted, which is what makes the method work.
4. The list after each pass Showing every swap when passes were asked for loses marks.
5. The smaller of the two front items Taking the smaller front item each time keeps the result in order.
6. No: it suits small, nearly sorted lists On a short or almost sorted list it finishes quickly, with no extra memory.
7. Doubles the work About n log n comparisons: far better than bubble sort's n squared.
8. Whether this pass made any swap If a pass ends with swapped still False, the list is sorted.

Memory Match

• A 5 Bubble sort: Swaps adjacent items in the wrong order
• B 1 Merge sort: Splits to single items, then merges
• C 6 Pass: One complete run through the list
• D 2 Swap: Exchanging two adjacent items
• E 3 Temporary variable: Holds a value safe during a swap
• F 4 In place: Sorting with almost no extra memory

Sort It

1. Bubble sort Good for very small or nearly sorted lists A pass with no swaps comes quickly.
2. Merge sort Good for large lists where speed matters Doubling the data only roughly doubles the work.
3. Bubble sort Sorts in place It needs almost no extra memory.
4. Bubble sort Uses a temporary variable to swap Swapping two items needs somewhere to hold one.
5. Bubble sort Stops when a pass makes no swaps That is bubble sort's stopping condition.
6. Bubble sort Compares adjacent items Bubble sort works through adjacent pairs.
7. Bubble sort Roughly n squared comparisons That is why it is slow on large lists.
8. Merge sort Needs extra memory for the sub-lists The sub-lists are held while merging.
9. Merge sort Uses divide and conquer Split, solve, combine.
10. Merge sort Splits the list until each part has one item Merge sort divides, then merges.
11. Merge sort Roughly n log n comparisons That is why it is fast on large lists.
12. Merge sort Usually written recursively Each half is sorted by the same routine.