Finding a slot is different from making room.
Binary search can find an insertion position in O(log n), but inserting into an array may still shift O(n) items. Across all insertions, the worst-case shifting work is Θ(n²).
Lecture 08 · Heaps and Heapsort
Keep the biggest at the top.
A heap is a tree-shaped way to organize an array. It does not fully sort values; it keeps enough order to make the largest easy to grab.
First, picture the heap
In a max heap, every parent is at least as large as its children. So the root is the maximum. The other values can be in many orders.
Heapsort moves the root to the far right, shrinks the heap, then lets the new root sink until the parent-child rule is restored.
Think: “Take the current biggest and park it at the end.” Repeat to fill the array from right to left.
Heap property · parent ≥ child
9
78
2534
Stored level by level using the slides’ convention: root index 1; children of index k are 2*k and 2*k+1.
C++ · build and repair a max heap
void heapsort(Item heap[], size_t n) { heapify(heap, n); for (size_t i = n; i >= 2; --i) { swap(heap[i], heap[1]); fixDown(heap, i - 1, 1); } // for i} // heapsort() void fixDown(Item heap[], size_t heapsize, size_t k) { while (2 * k <= heapsize) { size_t j = 2 * k; // start with left child if (j < heapsize && heap[j] < heap[j + 1]) ++j; if (heap[k] >= heap[j]) break; // heap restored swap(heap[k], heap[j]); k = j; // move down } // while} // fixDown()Worst-case time Θ(n log n) · extra space O(1) · not stable. This example uses zero-based indexing; the slides also show a one-based version.
Lecture 09 · Ordered, Sorted, and Sets
Sorted order becomes a tool.
This lecture is about what you can do after sorting. Sorted ranges let you search and combine without checking every pair.
Binary search throws half away
To find 9 in [1, 3, 5, 7, 9, 11, 13], check the middle. The first middle is 7 at index 3. Since 9 is larger than 7, ignore that value and the left half. Check the middle of what remains, then narrow again.
Each check halves the range. That’s why binary search takes O(log n), instead of looking at all n values.
Three similar tools
binary_search: does the value exist?lower_bound: first value ≥ target.upper_bound: first value > target.
Try it · search a sorted row
A duplicate-key example
In [1, 3, 3, 3, 7], searching for 3 gives lower_bound = index 1 and upper_bound = index 4. The range between them contains all three copies.
Search one value
Binary search needs sorted data and takes O(log n) checks.
Combine sorted ranges
Set operations walk both left to right, taking the smaller next value. Usually O(m+n).
C++ · binary search, bounds, and a sorted union
vector<int> a = {1, 3, 3, 3, 7};int target = 3; // These all require sorted input.bool exists = binary_search(a.begin(), a.end(), target);auto low = lower_bound(a.begin(), a.end(), target); // index 1auto high = upper_bound(a.begin(), a.end(), target); // index 4 // Two sorted inputs can be merged into a sorted union.vector<int> b = {2, 3, 8};vector<int> result;set_union(a.begin(), a.end(), b.begin(), b.end(), back_inserter(result)); // result uses extra storage. For an O(1)-memory display problem,// scan the sorted inputs and print results as they are found.Lecture 10 · Elementary Sorts
Three simple rules for moving values.
Bubble, selection, and insertion sort all use comparisons. They differ in what each pass accomplishes. Choose one and step through the same list below.
Bubble: compare neighbors
Look at adjacent values. If backward, swap them. In this course version, a small value bubbles left. An early-stop check lets already sorted input finish in one pass.
Selection: find the next smallest
Scan the unsorted part, remember its smallest value, then swap it into the next open position. It still scans sorted input, but makes only O(n) swaps.
Insertion: tuck the next value in
Treat the left side as sorted. Pick the next value and slide bigger values right until there’s a gap. Like arranging cards in your hand. Nearly sorted input needs little shifting.
Same input · after the first pass
start
52413
bubble
15243
select
12453
insert
25413
Bubble + insertion
Stable, in-place, useful on nearly sorted data. Worst case Θ(n²).
Selection
Θ(n²) comparisons even on sorted input, but only O(n) swaps.
C++ · bubble sort: compare neighbors
void bubble(Item a[], size_t left, size_t right) { for (auto i = left; i < right - 1; ++i) { bool swapped = false; for (auto j = right - 1; j > i; --j) { if (a[j] < a[j - 1]) { swapped = true; swap(a[j - 1], a[j]); } // if } // for j if (!swapped) break; } // for i} // bubble()Adaptive version: Θ(n) on already sorted input; Θ(n²) worst case.
C++ · selection sort: remember the minimum
void selection(Item a[], size_t left, size_t right) { for (auto i = left; i < right - 1; ++i) { auto minIndex = i; for (auto j = i + 1; j < right; ++j) if (a[j] < a[minIndex]) minIndex = j; swap(a[i], a[minIndex]); } // for} // selection()Θ(n²) comparisons in every case; at most n−1 swaps.
C++ · insertion sort: hold, shift, insert
void insertion(Item a[], size_t left, size_t right) { for (auto i = left + 1; i < right; ++i) { Item v = a[i]; auto j = i; while ((j > left) && (v < a[j - 1])) { a[j] = a[j - 1]; --j; } // while a[j] = v; } // for i} // insertion()Adaptive: Θ(n) best case; Θ(n²) worst case. Stable.
Counting sort: use keys as bucket labels
The slide version sorts full Student records by their category key. First count each category. Next turn frequencies into starting offsets. Finally scan the original records in order and copy each into its next free result position. There are no pairwise key comparisons.
For input [2, 1, 2, 0, 3, 2], the buckets below mean one zero, one one, three twos, and one three. Output becomes [0, 1, 2, 2, 2, 3].
The key range must be manageable. This version needs both counts and a separate output vector, so it is not the single-pass, constant-memory handwritten solution.
Count by key
key 01
key 11
key 23
key 31
These are pass 1 frequencies. Pass 2 changes them to starting offsets [0, 1, 2, 5]. Pass 3 copies original records into those category blocks.
C++ · stable counting sort of Student records
void counting_sort(vector<Student> &students) { vector<Student> result(students.size()); vector<size_t> counts(CLASSES); size_t temp, sum = 0; for (auto &s : students) // Pass 1: count each category ++counts[s.classStanding()]; for (size_t i = 0; i < CLASSES; ++i) { // Pass 2: calculate start points temp = counts[i]; counts[i] = sum; sum += temp; } // for i for (auto &s : students) { // Pass 3: sort result[counts[s.classStanding()]] = s; ++counts[s.classStanding()]; } // for swap(students, result);} // counting_sort()O(n+k) time and space, where k is the number of possible keys. For stable sorting of records, use offsets and preserve the records when placing them into output.
Other exact slide versions
Slide 14 · basic bubble
Exact slide 14 code. This version does not stop early.
void bubble(Item a[], size_t left, size_t right) { for (auto i = left; i < right - 1; ++i) for (auto j = right - 1; j > i; --j) if (a[j] < a[j - 1]) swap(a[j - 1], a[j]);} // bubble()Slide 24 · avoid self-swaps
Exact slide 24 code. The added if skips a swap when minIndex already equals i.
void selection(Item a[], size_t left, size_t right) { for (auto i = left; i < right - 1; ++i) { auto minIndex = i; for (auto j = i + 1; j < right; ++j) if (a[j] < a[minIndex]) minIndex = j; if (minIndex != i) swap(a[i], a[minIndex]); } // for} // selection()Slide 31 · basic adjacent swaps
Exact slide 31 code. The inner loop still visits every earlier neighbor.
void insertion(Item a[], size_t left, size_t right) { for (auto i = left + 1; i < right; ++i) for (auto j = i; j > left; --j) if (a[j] < a[j - 1]) swap(a[j - 1], a[j]);} // insertion()Slide 39 · sentinel version
Exact slide 39 code. The minimum at a[left] stops the while loop, so it omits j > left.
void insertion(Item a[], size_t left, size_t right) { for (auto i = right - 1; i > left; --i) // find min item, if (a[i] < a[i - 1]) // put in a[left] swap(a[i - 1], a[i]); // as sentinel for (auto i = left + 2; i < right; ++i) { Item v = a[i]; auto j = i; // v is new item while (v < a[j - 1]) { // v in wrong spot a[j] = a[j - 1]; // copy/overwrite --j; } // while a[j] = v; } // for i} // insertion()Lecture 11 · Quicksort
Split around a pivot.
Quicksort partitions the range: smaller values go left, larger values go right. Then it repeats on each side.
A pivot makes a boundary
In the slide 9 partition, values left of pivot 4 are strictly less than 4; values right of it are at least 4. Those sides aren’t sorted yet, but sorting each finishes the job.
Balanced sides give Θ(n log n). If each pivot leaves one huge side and one tiny side, it can degrade to Θ(n²).
Think: Quicksort arranges during the split. No separate merge at the end.
Partition around pivot 4
625143
One valid partition:
213456
Groups are on the correct side; each group still needs sorting.
C++ · the exact partition policy quoted in your quiz
size_t partition(Item a[], size_t left, size_t right) { auto pivot = --right; // beware right == 0 while (true) { while (a[left] < a[pivot]) ++left; while (left < right && a[right - 1] >= a[pivot]) --right; if (left >= right) break; swap(a[left], a[right - 1]); } // while swap(a[left], a[pivot]); return left;} // partition()One partition call is O(n). It separates groups; it does not sort each group.
C++ · recurse after partitioning
void quicksort(Item a[], size_t left, size_t right) { if (left + 1 >= right) return; auto pivot = partition(a, left, right); quicksort(a, left, pivot); quicksort(a, pivot + 1, right);} // quicksort()Average Θ(n log n), worst Θ(n²). Additional recursion stack: typically O(log n), potentially O(n) for this basic implementation.
Lecture 12 · Merge Sort
Sort halves, then weave them together.
Merge sort divides the array until each piece has one item. Then it merges small sorted pieces into larger sorted pieces.
The merge does the sorting
Suppose sorted halves are [2, 5, 8] and [1, 4, 7]. Compare their front values, take the smaller one, and advance only that half.
Each merge pass touches every item once. There are about log₂(n) levels, so time is Θ(n log n), even if input is already sorted or reversed.
Think: Quicksort splits values into sides. Merge sort splits by position, then sorts while merging.
Merge two sorted halves
258+147
Take the smaller front each time:
124578
Result: [1, 2, 4, 5, 7, 8]
C++ · exact merge_sort() and merge() from slides 10–11
void merge_sort(Item a[], size_t left, size_t right) { if (left + 1 >= right) // base case: 0 or 1 item(s) return; auto mid = left + (right - left) / 2; merge_sort(a, left, mid); // [left, mid) merge_sort(a, mid, right); // [mid, right) merge(a, left, mid, right);} // merge_sort() void merge(Item a[], size_t left, size_t mid, size_t right) { auto n = right - left; vector<Item> c(n); for (auto i = left, j = mid, k = 0; k < n; ++k) { if (i == mid) c[k] = a[j++]; else if (j == right) c[k] = a[i++]; else c[k] = (a[i] <= a[j]) ? a[i++] : a[j++]; } // for copy(begin(c), end(c), &a[left]);} // merge()Standard array version: Θ(n log n) time, O(n) auxiliary array. Equal keys keep their order because the left side wins ties.
Connect the lectures · quiz reasoning
The questions combine these ideas.
Use the data structure, the memory limit, and the kind of work being counted to decide which algorithm fits.
A linked list rewards sequential access.
A merge can advance through list nodes without jumping to an arbitrary index. That makes merge sort a natural Θ(n log n) choice for linked lists. An array heap depends on fast parent/child indexing, which ordinary lists do not provide.
Sorted data lets two pointers do the next job.
For a closest-sum pair, sort first, then keep one pointer at each end. A sum that is too small means moving the left pointer right; a sum that is too large means moving the right pointer left. The scan is linear. Count the sorting cost too.
If total extra space must be O(1), heapsort meets that array-sorting restriction. A basic recursive quicksort also needs stack space.
“In either range, but not both” is symmetric difference.
Sort both ranges, then compare their current items. Output the smaller unmatched item. Skip a match and advance both. Treat duplicate counts according to the question’s definition; set membership and multiset counts are different.
A snapshot reveals the algorithm’s promise.
Merge sort forms sorted runs of sizes 1, 2, 4, … in its bottom-up version. Selection settles a minimum on each pass. Insertion grows a sorted prefix. Bubble moves an extreme value across neighbors. Heapsort first forms a heap, then grows a sorted suffix.
[a] [b] [c] [d] → [a b] [c d] → [a b c d]
Stable means equal keys keep their order.
Sorting [2A, 1, 2B] stably gives [1, 2A, 2B]. It preserves which equal-key record came first. Stability does not mean a runtime guarantee. Standard bubble, insertion, and merge sort are stable; standard selection, heap, and in-place quicksort are not.
Pivot choice affects the split.
Balanced partitions give about log n levels of linear partitioning work. Repeated 0-versus-(n−1) splits give quadratic work. Sorted input alone does not determine quicksort’s time; the pivot rule and partition behavior matter.
For general partition questions, equal keys may appear on either side if no stricter rule is specified. When tracing supplied code, obey its exact < and >= conditions.
Fast comparisons do not erase expensive moves.
For comparison sorting, the best possible general worst-case growth is Ω(n log n) comparisons. Elementary selection sort makes Θ(n²) comparisons but only O(n) swaps. If copying large records dominates, that difference matters.
Handwritten 0/1/2 task: understand the regions first
Maintain four regions: zeros, ones, unknown values, twos. The scan pointer looks at the first unknown item. A 0 goes to the left region; a 2 goes to the right region; a 1 is already in its region. After swapping a 2 rightward, inspect the incoming value before advancing the scan.
0s1sunknown2s
This is the three-way partition idea. The quicksort trace earlier uses the separate two-way lecture implementation because that is the one quoted in the quiz.
Memory hooks
Heap: remove the biggest. Bubble: swap neighbors. Selection: find next smallest. Insertion: slide into sorted part. Quick: partition around a pivot. Merge: weave sorted halves. Binary search: halve a sorted range.