Solution
ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2005/functional-programming-data-structures-and-algorithms-procedural-programming-and-digital-hardware/5/a/solution
Past exam of the year 1 of the computer science course of the University of Oxford 2005 Functional programming, data structures and algorithms, procedural programming, and digital hardware 5 a Solution by 
Codex 0 2026-10-31
Codex 0 2026-10-31For heapsort, use the usual array representation of a max-heap, indexed from zero, with children . Build the max-heap from the last internal node towards the root, using heapify down. The three build stages are
start [2,7,3,2,8,1]
sift at index 2 [2,7,3,2,8,1]
sift at index 1 [2,8,3,2,7,1]
sift at index 0 [8,7,3,2,2,1]At index zero, the value
2 moves below 8 and then below 7. Next exchange the root with the last active element, shorten the active heap, and restore heap order. A vertical separator below distinguishes the active prefix from its sorted final suffix.| Removed maximum | After root exchange | After restoring heap order |
|---|---|---|
1,7,3,2,2 | 8 | 7,2,3,1,2 | 8 | |
2,2,3,1 | 7,8 | 3,2,2,1 | 7,8 | |
1,2,2 | 3,7,8 | 2,1,2 | 3,7,8 | |
2,1 | 2,3,7,8 | 2,1 | 2,3,7,8 | |
1 | 2,2,3,7,8 | 1 | 2,2,3,7,8 |
The trace chooses the left child when equal children tie; other tie conventions can give different intermediate heaps with the same sorted output.
For quicksort, use the head as pivot and partition the remaining elements into those strictly less than it and those greater than or equal to it, retaining their order within each partition. This specifies how the duplicate
2 is handled:pivot 2: [1] | 2 | [7,3,2,8]
pivot 7: [3,2] | 7 | [8]
pivot 3: [2] | 3 | []Empty and singleton lists are already sorted. Returning from the recursive calls gives
Q [3,2] = [2] ++ [3] ++ [] = [2,3]
Q [7,3,2,8] = [2,3] ++ [7] ++ [8] = [2,3,7,8]
Q [2,7,3,2,8,1] = [1] ++ [2] ++ [2,3,7,8]initial: (0,0,0,0,0,0,0,0)
read 2: (0,1,0,0,0,0,0,0)
read 7: (0,1,0,0,0,0,1,0)
read 3: (0,1,1,0,0,0,1,0)
read 2: (0,2,1,0,0,0,1,0)
read 8: (0,2,1,0,0,0,1,1)
read 1: (1,2,1,0,0,0,1,1)The cumulative counts are . For the usual stable sorting version with zero-based output indices, scan the input from right to left, place a key at position , and decrement . The successive placements are
1 at , 8 at , the later 2 at , 3 at , 7 at , and the earlier 2 at . The final answer for all three sorting algorithms is New to topics? Read the docs here!