Phase 3 Checkpoint: 15 questions on sorting and selection. A = [5, 2, 9, 1, 7, 3] unless stated.
⏱️
15 questions · 23 marks · 45 minutes. Negative marking on MCQ only: −1/3 mark for a wrong 1-mark MCQ, −2/3 for a wrong 2-mark MCQ. No negative marking for MSQ or NAT; MSQ has no partial credit.
Q1NAT1 markInversions
Number of inversions in A?
Numerical answer: ________
Q2MCQ1 markBubble
Bubble sort on A: array after two passes?
- (A) [2, 1, 3, 5, 7, 9]
- (B) [2, 1, 5, 3, 7, 9]
- (C) [2, 5, 1, 7, 3, 9]
- (D) [1, 2, 3, 5, 7, 9]
Q3NAT1 markSelection
Selection sort comparisons on 15 elements?
Numerical answer: ________
Q4NAT2 marksInsertion
Insertion sort on [1, 3, 5, 7, 2, 4, 6, 8]. Number of shifts?
Numerical answer: ________
Q5MSQ2 marksProperties
Which are true?
- (A) Selection sort is Θ(n) on sorted input.
- (B) Insertion sort is Θ(n) on sorted input.
- (C) Bubble sort swaps equal inversions.
- (D) Insertion sort is stable.
Q6NAT1 markMerge
Maximum comparisons to merge sorted lists of 10 and 15 elements?
Numerical answer: ________
Q7NAT2 marksMerge sort
Merge sort (left half = first ⌊n/2⌋) on A. Total comparisons?
Numerical answer: ________
Q8NAT2 marksWorst merge sort
Worst-case comparisons of merge sort on 32 elements?
Numerical answer: ________
Q9NAT2 marksQuicksort
Quicksort (Lomuto, pivot last) on the sorted array [1, 2, …, 12]. Total comparisons?
Numerical answer: ________
Q10MCQ1 markQuicksort split
If quicksort always picks the median as pivot (found in linear time), its worst-case time is:
- (A) Θ(n²)
- (B) Θ(n log² n)
- (C) Θ(n)
- (D) Θ(n log n)
Q11NAT2 marksHeap
Build-heap on A. Element at position 3 (1-based)?
Numerical answer: ________
Q12MCQ1 markHeap extract
Max-heap [16, 14, 10, 8, 7, 9, 3, 2, 4, 1]. After one extract-max, the root is:
- (A) 14
- (B) 8
- (C) 10
- (D) 9
Q13NAT1 markLower bound
Minimum worst-case comparisons to sort 6 elements by comparisons?
Numerical answer: ________
Q14NAT2 marksCounting sort
Counting sort on [2, 5, 3, 0, 2, 3, 0, 3] (keys 0 … 5). Prefix-sum value C[3]?
Numerical answer: ________
Q15NAT2 marksSecond largest
Minimum comparisons to find the largest and second largest of 64 elements?
Numerical answer: ________
✓Answer Vault
Answer Vault
Try the questions first. Open when you are ready to check.
Q1 Answer: 81 mark
(5,2), (5,1), (5,3), (2,1), (9,1), (9,7), (9,3), (7,3).
Re-read: Lesson 3.1.2 — Insertion sort and inversions; stable and in-place sorting
Q2 Answer: (B)1 mark
Pass 1: [2, 5, 1, 7, 3, 9]; pass 2: [2, 1, 5, 3, 7, 9].
- (A) is wrong: 5 and 3 swap only once 3 reaches them.
- (C) is wrong: After one pass.
- (D) is wrong: After three.
Re-read: Lesson 3.1.1 — Bubble sort and selection sort: passes, comparisons, swaps
Q3 Answer: 1051 mark
15 × 14 / 2.
Re-read: Lesson 3.1.1 — Bubble sort and selection sort: passes, comparisons, swaps
Q4 Answer: 62 marks
Equals the inversions: (3,2), (5,2), (5,4), (7,2), (7,4), (7,6).
Re-read: Lesson 3.1.2 — Insertion sort and inversions; stable and in-place sorting
Q5 Answer: (B) (C) (D)2 marks
Selection sort always compares n(n − 1)/2 times.
- (A) is wrong: Θ(n²).
Re-read: Lesson 3.1.2 — Insertion sort and inversions; stable and in-place sorting
Q6 Answer: 241 mark
10 + 15 − 1.
Re-read: Lesson 3.2.1 — Merge sort: merging, recurrence, comparison counts
Q7 Answer: 102 marks
1 + 2 (left), 1 + 1 (right), 5 (final).
Re-read: Lesson 3.2.1 — Merge sort: merging, recurrence, comparison counts
Q8 Answer: 1292 marks
32 × 5 − 32 + 1.
Re-read: Lesson 3.2.1 — Merge sort: merging, recurrence, comparison counts
Q9 Answer: 662 marks
11 + 10 + … + 1.
Re-read: Lesson 3.2.2 — Quicksort: partitioning, best, worst and average cases
Q10 Answer: (D)1 mark
Halves every time: 2T(n/2) + Θ(n).
- (A) is wrong: No bad splits.
- (B) is wrong: No.
- (C) is wrong: Each level is Θ(n), and there are log n levels.
Re-read: Lesson 3.2.2 — Quicksort: partitioning, best, worst and average cases
Q11 Answer: 52 marks
Heap [9, 7, 5, 1, 2, 3].
Re-read: Lesson 3.2.3 — Heapsort: build-heap in O(n), heapify, extract-max
Q12 Answer: (A)1 mark
1 moves up and sinks; 14 becomes the root.
- (B) is wrong: Smaller than 14.
- (C) is wrong: 14 is larger.
- (D) is wrong: Smaller than 14.
Re-read: Lesson 3.2.3 — Heapsort: build-heap in O(n), heapify, extract-max
Q13 Answer: 101 mark
⌈log 720⌉.
Re-read: Lesson 3.3.1 — The Ω(n log n) lower bound for comparison sorting; comparing all sorts
Q14 Answer: 72 marks
Keys ≤ 3: seven of them.
Re-read: Lesson 3.3.2 — Counting sort, radix sort and bucket sort
Q15 Answer: 682 marks
64 + 6 − 2.
Re-read: Lesson 3.3.3 — Selection: minimum and maximum, second largest, k-th smallest