Essay, code-tracing, bug-fixing and coding questions are in the week's question bank:
Data Structures and Algorithms (DSA27) · Week 9
Basic sorting (Lecture 09)
These quizzes are for self-study. Your answers are saved on this device only and are not sent anywhere.
-
A sorting algorithm is stable when:
Stability is about equal keys and their arrival order. (a) is "in place"; (d) is a property of selection sort.
-
A sort is in place when:
The course sorts return a new list, but they rearrange their working
Arraywith O(1) extra slots — so they are in place in this sense. (b) is what Python'slist.sortdoes; it is not the definition. -
Which of these sorts is not stable, as written in the course?
Its long-distance swap can jump an element over an equal one. Bubble and insertion sort move a value only past strictly greater ones; a merge that takes from the left on a tie is stable (Week 10).
-
Bubble sort, with the early exit, on
[1, 2, 3, 4, 5, 6]makes how many comparisons?The first pass compares the 5 neighbour pairs, swaps nothing, and the early exit stops the sort: n - 1 = 5.
-
Selection sort on
[1, 2, 3, 4, 5, 6]makes how many comparisons?5 + 4 + 3 + 2 + 1 = 15 = n(n-1)/2. Selection sort scans the whole rest in every round, sorted or not.
-
The array after the first pass of bubble sort on A is:
The 9 is carried to the end; the pass swaps 5 and 2, then 9 and 1, 9 and 7, 9 and 3. (a) is the first round of selection sort; (c) is after the second pass.
-
The array after the first round of selection sort on A is:
The minimum, 1 at index 3, is swapped with the 5 at index 0. (a) is bubble sort's first pass.
-
Insertion sort on A. The array after the round that inserts
a[3](the value 1) is:Before that round the prefix is
[2, 5, 9]; the 1 shifts all three right and lands at index 0. -
How many inversions does
[3, 1, 2]have?(3, 1) and (3, 2). The pair (1, 2) is in order.
-
The number of shifts insertion sort makes is always equal to:
Each shift moves
currentpast one larger value before it — one inverted pair — and changes the order of no other pair (W9-E3). -
The best case of insertion sort is:
One comparison per round and no shifts: n - 1 comparisons.
-
Selection sort is the best of the three basic sorts when:
At most n - 1 swaps, whatever the input. It is not stable (c), gains nothing from sorted input (a), and (d) is counting sort.
-
The largest number of swaps selection sort makes on 10 values is:
At most one swap per round, and there are n - 1 rounds. 45 (b) is the number of comparisons.
-
counting_sort([4, 0, 4, 1])makes acountsarray of how many slots?k = max + 1 = 5: one counter for each value 0, 1, 2, 3, 4.
-
Counting sort on n values from the range 0 .. k - 1 takes:
One pass to count (n), one over the counters (k), n writes.
-
Counting sort is a bad choice when:
Sorting two values up to a million needs a million counters and a loop over all of them.
-
In the worst case, every comparison sort of n values needs at least:
A decision tree with at least n! leaves has height at least log2 n!, which is Θ(n log n).
-
The fewest comparisons that can sort any 4 values in the worst case, by comparing, is at least:
4! = 24 orders, and 24 = 16 < 24 ≤ 32 = 25: at least ⌈ log2 24 ⌉ = 5 comparisons in the worst case.
-
The decision-tree argument for the lower bound uses the fact that:
Two different input orders must end at different leaves, and h yes/no answers can tell apart at most 2h cases.
-
A
_stepsgenerator yields its working list itself (not a copy) before each comparison. Thenframes = list(generator)holds:Every frame holds a reference to the same list; by the time you look, it is sorted.
step_sliderhides the bug by copying each frame as it arrives;list(generator)does not. -
A plain sort runs its
_stepsgenerator to the end, and the generator copies the array before each of its about n2/2 comparisons. The plain sort costs:n2/2 copies of n values each: Θ(n3). The reference fixes it with
snapshot=_livein the plain sort (Lecture 09, "The price of watching"). -
Bubble sort on
[6, 5, 4, 3, 2, 1]makes how many swaps?Reversed input has every pair inverted: 6 × 5 / 2 = 15 inversions, and bubble sort makes one swap per inversion.
20 marks
Written questions
5 written questions (20 marks). Write your answer first, then open the model answer and its marking points, and mark yourself honestly: each point is worth about one mark.
Written total: 0 / 20
-
Define stable and in place. Say which of bubble, selection and insertion sort are stable, and why, from their code. Give a small input on which selection sort is not stable, and explain why stability matters when you sort by two keys.
Model answer and marking points
- Stable: elements with equal keys come out in the order they went in. In place: only O(1) memory besides the array being sorted.
- Bubble sort swaps neighbours only when
a[j] > a[j + 1]— strictly — so two equal values are never swapped and never pass each other: stable. Insertion sort shifts only values> current, socurrentstops at an equal key: stable. Selection sort swapsa[i]with a minimum far to its right, which can jumpa[i]over an equal value: not stable. All three are in place. - Example: cards
2a, 2b, 1ccompared by number. Round 0 swaps1cwith2a:1c, 2b, 2a—2aand2bhave changed order. - Two keys: to sort by grade, and by name within a grade, sort by name first, then stably by grade. The second sort leaves students with equal grades in name order. An unstable second sort scrambles them.
-
Compare bubble, selection and insertion sort: the comparisons they make at best and at worst, and the swaps or shifts. For each, describe a situation in which it is the best of the three.
Model answer and marking points
comparisons, best comparisons, worst swaps or shifts bubble (early exit) n - 1 (sorted) n(n-1)/2 I swaps (inversions) selection n(n-1)/2 n(n-1)/2 at most n - 1 swaps insertion n - 1 (sorted) n(n-1)/2 I shifts - Insertion sort for small or nearly sorted data, or when stability is needed: it adapts to the input (O(n + I)) and does about half the comparisons of bubble sort on random data.
- Selection sort when writes are expensive (large records, flash memory): it writes O(n) times whatever the input.
- Bubble sort has no real niche — insertion sort is at least as good in every case. Its one merit is teaching: with the early exit it detects sorted input in one pass, and "neighbours swap" is the easiest sort to explain and to animate.
-
Define an inversion. Prove that insertion sort makes exactly one shift per inversion, and use that to give its best, worst and average case. Why do library sorts such as Timsort use insertion sort inside?
Model answer and marking points
- Inversion: a pair of positions i < j with a[i] > a[j].
- One shift per inversion: when
currentis inserted, it moves left past exactly the values before it that are larger — each such pair was an inversion, and after the move it is not. The relative order of every other pair is unchanged (the shifted values keep their order among themselves). So each shift removes exactly one inversion, and the sort ends when none are left: shifts = I, and comparisons ≤ I + n - 1. - Cases: sorted, I = 0: Θ(n). Reversed, I = n(n-1)/2: Θ(n2). Random: each pair inverted with probability ½, so the expected I is n(n-1)/4 — Θ(n2), half the worst.
- Libraries: real data is often nearly sorted, and short pieces are common inside divide-and-conquer sorts. On both, insertion sort is near-linear, has a tiny constant, needs no memory and is stable. Timsort (Python, Java) extends short runs with binary insertion sort; introsort (C++) finishes small pieces with insertion sort.
-
Explain the
_stepsgenerator pattern ofdsa/sorting.py: what it yields and when, how the plain sort reuses it, the two rules its frames must obey, and what "the price of watching" is and how it is fixed.Model answer and marking points
- What it yields:
(values, highlight)— a snapshot of the array and the indices the next step concerns. Bubble sort yields once at the start, before every comparison, and once at the end. - Reuse: the plain sort runs the generator to the end and keeps the last state (
_finish). One implementation: the animation shows exactly the code the tests grade. - Rules: each frame must be its own list (
list(a)), or the frames all show the final state (test_step_frames_are_independent_snapshots); and the last frame must be sorted (test_step_form_is_a_generator_ending_sorted). - The price of watching: a copy costs O(n); made before each of n2/2 comparisons, it makes the plain sort Θ(n3) — measured, the time grows about 8× per doubling instead of 4×. Fix: a
snapshotparameter,listby default for animations; the plain sort passes_live, which returns the workingArraywithout copying, and_finishmakes one copy at the end.
- What it yields:
-
State the lower bound for comparison sorting and give the decision-tree argument for it. Explain why counting sort does not contradict it, and when counting sort is the right choice.
Model answer and marking points
- Bound: every sort that learns about its input only by comparing two elements needs at least ⌈ log2 n! ⌉ comparisons in the worst case, and log2 n! = Θ(n log n).
- Argument: draw the sort's comparisons as a binary decision tree; one run is a root-to-leaf path. Different input orders need different rearrangements, so they must reach different leaves: at least n! leaves. A binary tree of height h has at most 2h leaves, so h ≥ log2 n!. Since n! ≥ (n/2)n/2, log2 n! ≥ n/2log2n/2. For n = 10: at least 22 comparisons.
- Counting sort: does not compare.
counts[v] += 1uses the value as an address — one step with k outcomes, not 2 — so the bound, which is about comparison sorts only, does not apply. It pays with O(k) memory and with keys restricted to small non-negative integers. - When: integer keys whose range k is at most about n — marks, ages, letters, grades. Not for phone numbers, floats or strings.