Sorting Algorithms Checkpoint
A review of this module. Skip it if you feel confident; the next module does not need it.
Fix the mistakes
The slips that cost marks in this module. Spot each one, then check the fix.
This checkpoint mixes every sort from the module. First decide which idea the clue points to, then write it and state its cost.
Pick the sort from the clue
Read the clue first. "Guaranteed bound" or "keep equal order" points to merge sort. "K-th value" points to quickselect or a heap. "Small whole numbers" points to counting. "Nearly sorted" or "tiny list" points to insertion sort. Otherwise call sorted().
Merge and partition, the two core steps
Almost every sorting question is one of two moves: merge two sorted lists, or partition around a pivot. Write both from memory; the rest is calling them in the right order.
def merge(left, right): result, i, j = [], 0, 0 while i < len(left) and j < len(right): if left[i] <= right[j]: result.append(left[i]) i += 1 else: result.append(right[j]) j += 1 return result + left[i:] + right[j:]Example 1 · Inversions tell how unsorted a list is
def inversions(items): if len(items) <= 1: return items, 0 mid = len(items) // 2 left, a = inversions(items[:mid]) right, b = inversions(items[mid:]) merged, i, j, cross = [], 0, 0, 0 while i < len(left) and j < len(right): if left[i] <= right[j]: merged.append(left[i]) i += 1 else: merged.append(right[j]) j += 1 cross += len(left) - i return merged + left[i:] + right[j:], a + b + cross
print(inversions([3, 1, 2])[1], inversions([1, 2, 3])[1], inversions([3, 2, 1])[1])2 0 3
What this code does
- A list with one value out of place has few inversions; a reversed list has the most, n(n-1)/2.
- This is also the number of adjacent swaps bubble sort would make.
Example 2 · Median with quickselect
def quickselect(items, k): pivot = items[len(items) // 2] smaller = [x for x in items if x < pivot] equal = [x for x in items if x == pivot] if k < len(smaller): return quickselect(smaller, k) if k < len(smaller) + len(equal): return pivot larger = [x for x in items if x > pivot] return quickselect(larger, k - len(smaller) - len(equal))
loads = [40, 10, 90, 30, 70, 20, 60]print(quickselect(loads, len(loads) // 2))40
What this code does
- Seven loads, so the median is at index 3 of the sorted order: 10, 20, 30, 40, 60, 70, 90.
- No full sort is needed; average time is O(n).
Merge costs O(n) with O(n) space. Partition (shown in the quick sort lesson) costs O(n) with O(1) space.
Count work in plain words
Say the cost aloud: how many levels, and how much work per level. Merge sort has log n levels of n work. Counting sort does n work plus one slot for each possible value. Quickselect does n, n/2, n/4 and so on.
Example 3 · Counting sort for ratings
ratings = [5, 3, 4, 5, 1, 3, 5, 2]counts = [0] * 6for r in ratings: counts[r] += 1print(counts)print([r for r in range(6) for _ in range(counts[r])])[0, 1, 1, 2, 1, 3] [1, 2, 3, 3, 4, 5, 5, 5]
What this code does
- Ratings run from 1 to 5, so six slots (0 to 5) are enough.
- One pass counts and one pass writes: O(n + k) with k = 6.
Module quiz
Questions from the whole module. Your first answer is your score.
Problems
Graded easy to hard, using everything from this module.
Try each one yourself first. Use the hint if you get stuck. Mark it as done when it works.
Exercise 1· Easy
Print the inversions of [1, 20, 6, 4, 5] by checking every pair.
5
Exercise 2· Easy
Merge [1, 5, 9] and [2, 6] with two pointers and print the result.
[1, 2, 5, 6, 9]
Exercise 3· Easy
Sort [4, 1, 3, 2] with insertion sort and print how many shifts it made, then the list.
4 [1, 2, 3, 4]
Exercise 4· Medium
Partition [6, 11, 3, 9, 8] around its last value and print the pivot index and the list.
2 [6, 3, 8, 9, 11]
Exercise 5· Medium
Find the 4th smallest of [12, 3, 5, 7, 19, 26, 4] with quickselect and print it.
7
Exercise 6· Medium
Sort the ages [21, 18, 25, 18, 30, 21] (all between 0 and 120) with counting sort and print the result.
[18, 18, 21, 21, 25, 30]
Exercise 7· Hard
Count inversions of [5, 3, 2, 4, 1] with merge sort and print the count.
8
Exercise 8· Hard
Sort the 0, 1 and 2 values of [1, 2, 0, 1, 0, 2, 1] in a single pass with three pointers. Print the list.
[0, 0, 1, 1, 1, 2, 2]
Interview questions
Questions interviewers ask on this topic.
Finish up
Mark complete & continue
Next: Must-do problems: Sorting Algorithms