Algorithms: sorting, searching and packing flashcards

Test yourself one card at a time: say the answer, flip, then mark it. Cards you know drop out; the rest come back until you know them. Your progress stays in this browser.

Algorithm
A finite sequence of precise instructions which, followed exactly, solves a problem or carries out a task.
Trace table
A table recording the value of each variable every time it changes as an algorithm runs, with the output at the end.
Pass (in a sort)
One complete run through the list (or through every current sublist) applying the sorting rule once.
Pivot (quick sort)
The middle item of a sublist (right of centre for an even number of items); the other items are split to its two sides and it is then fixed.
Lower bound (bin packing)
The smallest number of bins that could possibly hold the items: total size ÷ bin capacity, rounded up.
Optimal packing
A packing that uses the fewest bins possible; certainly optimal if it uses the lower bound.
Order of an algorithm
How the amount of work grows with the size n of the problem, e.g. linear (n), quadratic (n²), cubic (n³).
Lower bound for the number of bins
⌈total of item sizes ÷ capacity of one bin⌉ (always round up) (No — learn it)
Middle position in a binary search
⌈(first + last)/2⌉ (No — learn it)
Pivot position in a sublist of n items
⌈(n + 1)/2⌉: the middle item, or the one just right of centre when n is even (No — learn it)
Most comparisons in a bubble sort of n items
(n − 1) + (n − 2) + … + 1 = ½n(n − 1), in at most n − 1 passes (No — derive it)
Most iterations of a binary search of n items
⌊log₂ n⌋ + 1: the smallest k with 2ᵏ > n (No — derive it)
Scaling the run time of an algorithm of order nᵏ
new time ≈ old time × (new n ÷ old n)ᵏ (No — derive it)
Flow chart box shapes
Rounded box: start/stop. Rectangle: instruction (input, output, calculation). Diamond: yes/no decision with two exits.
Bubble sort drawn pass by pass (ascending)
Each row is one pass; the largest unsorted item reaches the right-hand end, so the fixed block at the end grows by one each pass.
Quick sort drawn pass by pass
Each row marks the pivots of that pass; earlier pivots stay fixed; sublists between fixed items shrink until every item is fixed.
Bins drawn to scale
Each bin is a column of height = capacity, items stacked with heights proportional to size; the gap at the top is the wasted space.
Graph of worst-case binary search iterations against n
A step function that rises by 1 each time n passes a power of 2 (logarithmic growth), far flatter than the parabola for bubble sort.
When does a bubble sort stop?
After a pass in which no swaps are made (or after n − 1 passes). The pass with no swaps must be shown.
Why must the list be ordered for a binary search?
Discarding half of the list relies on every item before the middle being smaller (or earlier) than every item after it.
How do first fit and first-fit decreasing differ?
First fit takes items in the given order; first-fit decreasing sorts them into descending order first, then applies first fit.
Full-bin method
Find combinations of items that fill bins exactly (by inspection), pack them, then first fit the rest. Often optimal, but it can miss the best packing and is hard for many items.
Why might the lower bound not be reachable?
It ignores how sizes fit together: e.g. two items each larger than half the capacity can never share a bin with each other.
How does a quick sort partition a sublist?
Items that belong before the pivot go to its left, the rest to its right, each group in the order they appeared; the pivot is then in its final place.
Items 7, 4, 12, 9, 3, 8, 6, 11, 5, 10 into bins of 20: lower bound, first fit, first-fit decreasing?
LB ⌈75/20⌉ = 4. First fit: 5 bins. FFD: 12, 8 · 11, 9 · 10, 7, 3 · 6, 5, 4 = 4 bins, optimal.
First pass of a bubble sort (ascending) on 27, 41, 19, 52, 34, 60, 45, 38
27, 19, 41, 34, 52, 45, 38, 60 — 7 comparisons, 4 swaps.
First pass of a quick sort into descending order on 48, 73, 15, 62, 56, 37, 81, 24, 90
Pivot 56 (5th item): 73, 62, 81, 90, 56, 48, 15, 37, 24.
Binary search for 40 in a sorted list of 20 numbers (positions 11, 6, 3, 5 hold 67, 44, 23, 36)
11 → keep 1–10; 6 → keep 1–5; 3 → keep 4–5; 5 → 40 > 36, first = 6 > last = 5: not in the list.
A bubble sort takes 2.4 s for 300 items. Estimate the time for 1200 items.
Quadratic: 2.4 × 4² = 38.4 s.
Most iterations for a binary search of 1000 items?
2⁹ = 512 ≤ 1000 < 1024 = 2¹⁰, so 10.
Crates 42, 63, 19, 37, 56, 67, 59, 51, 55, 30 kg, lift limit 100 kg. Why are 6 trips needed when the lower bound is 5?
Six crates (67, 63, 59, 56, 55, 51) are over 50 kg, so no two share a trip: at least 6 trips.
Rounding a lower bound
Always round up: 3.75 → 4, and 3.05 → 4 too.
Showing a sort
Write the whole list after every pass; for quick sort, mark the pivots used in that pass.
Quick sort: order within a sublist
Keep items in the order they appeared; do not sort them as you partition.
Unsuccessful binary search
Carry on until first > last, then state that the item is not in the list.
Lower bound not reached
Do not conclude the packing is not optimal; the bound may be impossible to achieve.

Practise this topicNotes Questions (28)Test builder