Sorting the Canteen Queue Data
A student writes an algorithm to process canteen orders stored as a list of records (order ID, timestamp, item, quantity). The program must output the ten most recent orders, grouped by item, with a total quantity per item. The student's first version sorts the whole list by timestamp using a simple bubble sort, then scans it to build a dictionary of item totals. With 12,000 orders, the program takes about 9 seconds on the school laptops, which the teacher says is too slow for the demonstration. The student proposes switching to Python's built-in sort and limiting the scan. A classmate argues that the bubble sort is 'fine because it is O(n) when nearly sorted'. The data is not nearly sorted - it arrives in random order from the canteen system.
1. Evaluate the classmate's claim about bubble sort and the student's proposed change.
Read the worked answer
Classmate's claim: Bubble sort is O(n) only in the best case, when the list is already sorted (with an early-exit flag). The stated data is randomly ordered, so the relevant case is average/worst, which is O(n²). At 12,000 records, that is roughly 144 million comparisons in the worst case - consistent with the 9-second runtime. The claim is therefore irrelevant to this input.
Student's proposal: Switching to a built-in sort (Timsort, O(n log n) average and worst) is sound: 12,000 log₂ 12,000 ≈ 12,000 × 13.6 ≈ 163,000 comparisons, a large reduction. Limiting the scan is also sensible - only the ten most recent orders are needed.
Judgement: The proposed change addresses the actual bottleneck. However, the student should verify the built-in sort is stable and that ties in timestamps are handled, and should measure before/after rather than assume.
2. The student wants the program to remain correct if two orders share the same timestamp. Explain how to achieve this and what could go wrong if ignored.
Read the worked answer
Approach: Sort by a composite key: primary key = timestamp, secondary key = order ID (or arrival index). This gives a deterministic, total order. If the built-in sort is stable, sorting by timestamp alone preserves original arrival order for ties, which may be acceptable if arrival order is meaningful - but this must be documented, not assumed.
What could go wrong if ignored:
- Ties may be ordered arbitrarily, so 'ten most recent' could omit or include different orders between runs, making output non-reproducible.
- Group totals could be correct but the selected ten could vary, causing inconsistent demonstrations and hard-to-reproduce test failures.
- If the scan stops after ten items without a defined tie-break, the result depends on sort internals.
Judgement: Define the tie-break explicitly and test with duplicate timestamps; do not rely on incidental stability.