D1.1 Algorithms: sorting, searching and packing
⤓ Presentation⤓ PowerPointPresentation: opens offline in any browser, simulations live. PowerPoint: editable.
Decision Mathematics 1 (AS), specification sections 1.1–1.4. Graph algorithms (Kruskal, Prim, Dijkstra) are on D1.2, route inspection and the travelling salesperson on D1.3, and scheduling workers on the critical path analysis page.
What this page covers
7 points
- What an algorithm is; carrying out an algorithm given as written instructions, with a trace table
- Following a flow chart and counting how many times a box is used
- Bubble sort: passes, comparisons and swaps, and when to stop
- Quick sort with the middle item of each sublist as the pivot, ascending or descending
- Binary search in an ordered list, including an item that is not there
- Bin packing: first fit, first-fit decreasing and full bins, and the lower bound
- The order of an algorithm (linear, quadratic, cubic) and estimating run times
In one minute
5 points
- An algorithm is a finite sequence of precise instructions that solves a problem; in D1 you carry algorithms out accurately and show that you did, tracing them in a table with one column per variable and one row per change.
- Bubble sort: compare neighbours left to right, swap if out of order; after pass k the last k items are fixed. Stop after a pass with no swaps.
- Quick sort: the middle item of each sublist (right of centre if there is an even number) is the pivot; items that belong before it go to its left, the others to its right, in their original order. Repeat on every sublist.
- Binary search: on an ordered list, compare with the item in position ⌈(first + last)/2⌉ and discard the half that cannot contain the target.
- Bin packing: lower bound = total ÷ capacity, rounded up. First fit takes items in the given order; first-fit decreasing sorts them first; full bins looks for exact fills. A packing that meets the lower bound is optimal.
Contents
13 sections
- What is an algorithm, and how do you trace one?
- How do you follow a flow chart?
- How does a bubble sort work?
- How does a quick sort work?
- How does a binary search find an item?
- How do the bin-packing algorithms work?
- What is the order of an algorithm?
- Exam tips for D1.1
- Common misconceptions
- How this topic connects
- Key formulae
- Check your understanding
- Specification checklist
What is an algorithm, and how do you trace one?
D1 algorithm questions never ask you to invent a sort. They ask you to carry one out pass by pass, keep track of comparisons and swaps, find the middle item correctly, pack bins in the right order and say how good the answer is. So the skill is accuracy plus a clear layout of working.
Every instruction must be unambiguous: two people following it get the same result. It must stop after a finite number of steps, and it usually takes an input and produces an output. Algorithms can be written as numbered instructions ("Step 3: if N < k, go to Step 7"), as a flow chart, or in a simple code-like form. You only follow them, never program them.
A trace table records the value of every variable each time it changes. Start a new row each time the algorithm goes round its loop, and write the output at the end. When asked "what does the algorithm do?", look at your input–output pairs and describe the general result (for example "it finds the highest common factor of A and B"), not the particular numbers.
Step 1: Input a positive integer N. Step 2: Let k = 1 and c = 0. Step 3: If N < k, go to Step 7. Step 4: Replace N by N − k. Step 5: Replace c by c + 1 and k by k + 2. Step 6: Go to Step 3. Step 7: Output c.
(a) Carry out the algorithm with N = 40, showing the values in a table. (b) State what the algorithm finds. (c) How many times is Step 4 carried out when N = 150?
(a) One row for the starting values, then one row per time round the loop:
| N | k | c |
|---|---|---|
| 40 | 1 | 0 |
| 39 | 3 | 1 |
| 36 | 5 | 2 |
| 31 | 7 | 3 |
| 24 | 9 | 4 |
| 15 | 11 | 5 |
| 4 | 13 | 6 |
At N = 4, k = 13 the test 4 < 13 is true, so the output is c = 6.
(b) The amounts subtracted are 1, 3, 5, 7, … and \(1 + 3 + \dots + (2c-1) = c^2\). The algorithm counts how many odd numbers can be removed, so it finds the integer part of √N (√40 = 6.32…).
(c) Step 4 runs once for each odd number removed, and the output for 150 is the integer part of √150: 12² = 144 ≤ 150 < 169 = 13², so 12 times.
Updating c but forgetting to update k in the same step, or recording a row for only some of the variables. When an instruction changes two variables, both change in the same row.
How do you follow a flow chart?
| Box shape | Meaning |
|---|---|
| Rounded (oval) box | Start or stop |
| Rectangle | An instruction: input, output or a calculation such as "Let P = P + B" |
| Diamond | A decision: a yes/no question, with one arrow out for each answer |
- Follow the arrows, one box at a time. A "Let" box replaces the old value of a variable with the new one.
- Boxes are usually numbered so a question can ask, for example, how many times box 4 is used.
- INT(x) means the integer part of x: INT(37 ÷ 2) = 18.
- A loop is an arrow that goes back up the chart; the decision box that controls it is the stopping condition. Check that it is eventually met.
Use the flow chart above. (a) Complete a trace table for the input A = 37, B = 23 and state the output. (b) Suggest what the algorithm calculates. (c) For the input A = 100, B = 7, how many times is box 4 used?
(a) One row each time box 4 is reached, showing P after box 5:
| A | B | Is A odd? | P |
|---|---|---|---|
| 37 | 23 | yes | 23 |
| 18 | 46 | no | 23 |
| 9 | 92 | yes | 115 |
| 4 | 184 | no | 115 |
| 2 | 368 | no | 115 |
| 1 | 736 | yes | 851 |
| 0 | 1472 |
At box 7, A = 0, so the output is P = 851. The last row shows the values after box 6 on the final pass; only P matters.
(b) 37 × 23 = 851, so the algorithm finds the product A × B.
(c) A is halved (rounding down) each time round: 100 → 50 → 25 → 12 → 6 → 3 → 1 → 0, so box 4 is used 7 times.
How does a bubble sort work?
In each pass, compare the 1st and 2nd items, then the 2nd and 3rd, and so on, swapping any pair in the wrong order. Equal items are not swapped. For ascending order the largest item "bubbles" to the end in pass 1, so pass 2 can stop one place earlier: pass k makes n − k comparisons for a list of n items.
- Stop after a pass with no swaps, or after n − 1 passes, whichever comes first. The pass with no swaps must be shown: it is how you know the list is sorted.
- The most comparisons possible are \((n-1) + (n-2) + \dots + 1 = \tfrac12 n(n-1)\), when the list starts in reverse order.
- For descending order, swap whenever the left item is smaller; then the smallest item moves to the end.
Use a bubble sort to arrange 27, 41, 19, 52, 34, 60, 45, 38 in ascending order. (a) Show the first pass in full. (b) Show the list after each later pass. (c) State the total number of comparisons and swaps.
(a) Pass 1, one comparison at a time:
| Compare | Swap? | List after the comparison |
|---|---|---|
| 27 and 41 | no | 27, 41, 19, 52, 34, 60, 45, 38 |
| 41 and 19 | yes | 27, 19, 41, 52, 34, 60, 45, 38 |
| 41 and 52 | no | 27, 19, 41, 52, 34, 60, 45, 38 |
| 52 and 34 | yes | 27, 19, 41, 34, 52, 60, 45, 38 |
| 52 and 60 | no | 27, 19, 41, 34, 52, 60, 45, 38 |
| 60 and 45 | yes | 27, 19, 41, 34, 52, 45, 60, 38 |
| 60 and 38 | yes | 27, 19, 41, 34, 52, 45, 38, 60 |
(b) Each pass is one comparison shorter. Pass 2: 19, 27, 34, 41, 45, 38, 52, 60. Pass 3: 19, 27, 34, 41, 38, 45, 52, 60. Pass 4: 19, 27, 34, 38, 41, 45, 52, 60. Pass 5: 19, 27, 34, 38, 41, 45, 52, 60 (no swaps: sort complete).
(c) Comparisons 7 + 6 + 5 + 4 + 3 = 25; swaps 4 + 4 + 1 + 1 + 0 = 10. The list was in order after pass 4, but the algorithm cannot know that until pass 5 finds nothing to swap.
How does a quick sort work?
Quick sort works by splitting rather than by neighbour swaps. Choose a pivot: the middle item of the list. With n items it is in position ⌈(n + 1)/2⌉, so for an even number you take the one just right of centre (the 6th of 10). This page uses that convention throughout; whichever you use, use it consistently.
- Write the items that belong before the pivot to its left, in the order they appear, then the pivot, then the rest in the order they appear. The pivot is now in its final position.
- Each later pass chooses a pivot in every sublist of two or more items. Show the list after each pass and mark the pivots (underline or circle them).
- The sort ends when every item has been a pivot or is alone in its sublist.
- For descending order, items larger than the pivot go to its left. For words, "before" means earlier in the alphabet.
Use a quick sort to arrange 48, 73, 15, 62, 56, 37, 81, 24, 90 in descending order. Show the result of each pass and identify the pivots.
Pass 1 9 items, so the pivot is the 5th, 56. Larger items go left, in their original order: 73, 62, 81, 90, 56, 48, 15, 37, 24.
Pass 2 Two sublists of 4; each pivot is the 3rd item (right of centre): [73, 62, 81, 90] → pivot 81; [48, 15, 37, 24] → pivot 37. List: 90, 81, 73, 62, 56, 48, 37, 15, 24.
Pass 3 Remaining sublists [73, 62] and [15, 24]; the pivot of a two-item sublist is its 2nd item. List: 90, 81, 73, 62, 56, 48, 37, 24, 15 (pivots 62 and 24).
Every item is now a pivot or alone in a sublist, so the sort is complete after 3 passes.
Rearranging items inside a sublist while partitioning, for example writing 90, 81, 73, 62 to the left of 56 in pass 1. Items keep the order in which they appeared; only their side of the pivot changes.
How does a binary search find an item?
Checking every item in turn is slow for a long list. A binary search halves the problem each time, but it only works on a list that is already in order (numerical or alphabetical); sort it first if it is not.
- Number the positions 1 to n and track the first and last positions still in play. The middle position is ⌈(first + last)/2⌉ (round up).
- Compare the target with the middle item. If they match, stop. If the target comes before it, the new last is middle − 1; if after, the new first is middle + 1. Either way the middle item and one half are discarded.
- If the list runs out (first > last) the item is not in the list; say so.
- Each iteration roughly halves what is left, so n items need at most ⌊log₂ n⌋ + 1 iterations: the smallest k with 2k > n.
The names Amir, Bea, Carlos, Dmitri, Elena, Femi, Grace, Hiro, Ines, Jonas, Leila, Mateo, Nadia, Oscar, Priya are in positions 1 to 15. Use a binary search to (a) find Leila, (b) search for Kofi. Show each iteration.
(a) ⌈(1 + 15)/2⌉ = 8, Hiro: Leila is after Hiro, so the list becomes 9–15. ⌈(9 + 15)/2⌉ = 12, Mateo: Leila is before Mateo, so 9–11. ⌈(9 + 11)/2⌉ = 10, Jonas: after, so 11–11. ⌈(11 + 11)/2⌉ = 11, Leila: found in position 11 after 4 iterations.
(b) Kofi is compared with the same names: Hiro (after) → Mateo (before) → Jonas (after) → Leila: Kofi is before Leila, so last = 10 < first = 11. The list is empty, so Kofi is not in the list.
How do the bin-packing algorithms work?
Items of known sizes go into identical bins of fixed capacity, using as few bins as possible. "Bins" can be lorries, CDs, time slots, lengths of timber: anything with a capacity.
The lower bound is not always reachable. Three items of size 11 in bins of 20 have a lower bound of ⌈33/20⌉ = 2, but no two fit together, so 3 bins are needed.
| Method | What you do | Comment |
|---|---|---|
| First fit | Take items in the order given; put each into the first (lowest-numbered) bin with room | Quick, but often wastes space: big items late in the list end up alone |
| First-fit decreasing | Sort into descending order first (state which sort), then apply first fit | Usually good, but not always optimal |
| Full bins | Find combinations that fill a bin exactly (by inspection); pack those, then first fit the rest | Often optimal, but can miss one and is hard for many items |
Parcels of mass (kg) 7, 4, 12, 9, 3, 8, 6, 11, 5, 10 are loaded onto trolleys, each carrying at most 20 kg. (a) Find a lower bound for the number of trolleys. (b) Use first fit. (c) Use first-fit decreasing. (d) Explain whether (c) is optimal.
(a) Total 75; 75 ÷ 20 = 3.75, so 4 trolleys.
(b) Items in the given order, each into the first trolley with room: T1: 7, 4, 9 · T2: 12, 3, 5 · T3: 8, 6 · T4: 11 · T5: 10, so 5 trolleys. The 9 goes into trolley 1 (7 + 4 + 9 = 20), not trolley 3: always check from the first bin.
(c) Sorted: 12, 11, 10, 9, 8, 7, 6, 5, 4, 3. T1: 12, 8 · T2: 11, 9 · T3: 10, 7, 3 · T4: 6, 5, 4, so 4 trolleys.
(d) 4 trolleys = the lower bound, so the solution is optimal.
Writing 75 ÷ 20 = 3.75 and giving a lower bound of 3 (or 4 "to the nearest whole number", which happens to agree). Always round up: 3 trolleys carry at most 60 kg. With a total of 61 kg the bound would still be 4.
What is the order of an algorithm?
The size of a problem is the number of items, n. The order of an algorithm describes how the amount of work (and so the run time) grows with n.
- Linear (order n): doubling n doubles the time, for example adding up a list.
- Quadratic (order n²): doubling n multiplies the time by 4: bubble sort, first fit and first-fit decreasing.
- Cubic (order n³): doubling n multiplies the time by 8.
- A binary search grows only like log₂ n: each extra iteration doubles the list it can handle. 1000 items need at most 10 iterations; a million at most 20.
To estimate a time for an algorithm of order nk: \(t_2 \approx t_1 \times (n_2 \div n_1)^k\). A bubble sort taking 2.4 s for 300 items takes about 2.4 × 4² = 38.4 s for 1200 items. These are estimates for large n; the exact count depends on the particular list (a sorted list needs only one bubble-sort pass).
A radio station has ten segments of lengths (minutes) 5, 15, 13, 14, 5, 10, 6, 17, 19, 16 to put into 30-minute slots; a segment cannot be split. (a) Find a lower bound for the number of slots. (b) Use first-fit decreasing. (c) Use full bins to find an allocation using the fewest slots, and explain why it is optimal. (d) First-fit decreasing has quadratic order; a program applies it to 250 items in 0.9 seconds. Estimate the time for 1000 items.
(a) 120 ÷ 30 = 4, so 4 slots.
(b) Sorted: 19, 17, 16, 15, 14, 13, 10, 6, 5, 5. S1: 19, 10 · S2: 17, 13 · S3: 16, 14 · S4: 15, 6, 5 · S5: 5, so 5 slots.
(c) Combinations totalling exactly 30: 19 + 6 + 5 · 17 + 13 · 16 + 14 · 15 + 10 + 5, so 4 slots, equal to the lower bound, so optimal. The total is exactly 4 × 30, so an optimal allocation must fill every slot, which is why full bins works so well here.
(d) n is multiplied by 4: 0.9 × (1000 ÷ 250)² = 0.9 × 16 = 14.4 seconds.
When a lower bound is reached, say so in words: "4 slots = lower bound, so optimal". If it is not reached, you cannot conclude that the packing is not optimal: the bound may be impossible to achieve.
Exam tips for D1.1
For bubble sort and quick sort, write the whole list after each pass, including items that did not move. For quick sort, mark the pivots used in that pass. The sorted list alone shows nothing about the algorithm.
Unless told to stop when the list is sorted, include the final pass with no swaps and say "no swaps, so the list is sorted". For numbers of comparisons or swaps, list them pass by pass before adding.
In a binary search write ⌈(first + last)/2⌉ = … each time, the item in that position, and which half you keep. Finish an unsuccessful search with "so the item is not in the list".
Present a packing as "Bin 1: 7, 4, 9 · Bin 2: 12, 3, 5 · …", keeping the order in which items went in. For first-fit decreasing, write the sorted list first.
Write the scale factor in full: (new size ÷ old size)power. Bubble sort and the bin-packing algorithms are quadratic, so the power is 2 unless the question gives a different order.
Common misconceptions
| Misconception | Why it is wrong | Correct idea |
|---|---|---|
| A lower bound of 3.75 rounds to 4 because 0.75 is more than a half. | The decimal part is irrelevant: 3 bins cannot hold the total. | Always round up: a total of 61 in bins of 20 still needs at least 4. |
| The lower bound is the number of bins needed. | It ignores how the item sizes fit together. | It is a minimum that may not be reachable (three items of 11 in bins of 20 need 3, not 2). |
| First-fit decreasing always gives the best packing. | It is a heuristic: worked example 7 uses 5 slots where 4 are possible. | Compare with the lower bound; full bins may do better. |
| Binary search works on any list. | Discarding half relies on everything before the middle coming first. | The list must be in order first. |
| A bubble sort can stop as soon as the list looks sorted. | The algorithm only knows it is finished when a pass makes no swaps. | Show the final pass with no swaps. |
| Doubling the number of items doubles the time for any algorithm. | That is only true for linear order. | Quadratic order: × 4; cubic: × 8. |
How this topic connects
D1.2 Graphs, minimum spanning trees and Dijkstra
Kruskal's algorithm starts by sorting the arcs by weight (a sorting job), and Prim's and Dijkstra's algorithms are traced step by step exactly like the flow charts here.
Critical path analysis (D1)
The lower bound for the number of workers, ⌈total activity time ÷ critical time⌉, is the bin-packing lower bound in disguise, and allocating activities to workers is a packing problem.
P2 and P3
The binary search's ⌊log₂ n⌋ + 1 iterations come from solving 2k > n with logarithms (P2); iterative methods for equations in P3 are algorithms with a stopping condition, traced in a table just like worked example 1.
Key formulae
| Formula | Use | In the formulae list? |
|---|---|---|
| lower bound = ⌈total size ÷ bin capacity⌉ | minimum possible number of bins | No — learn it |
| middle position = ⌈(first + last)/2⌉ | item to compare with in a binary search | No — learn it |
| pivot position = ⌈(n + 1)/2⌉ | middle item of a sublist of n items in a quick sort (right of centre when n is even) | No — learn it |
| pass k: n − k comparisons; at most ½n(n − 1) in total | counting comparisons in a bubble sort of n items | No — derive it |
| at most ⌊log₂ n⌋ + 1 iterations (smallest k with 2k > n) | longest possible binary search of n items | No — derive it |
| t₂ ≈ t₁ × (n₂ ÷ n₁)k | estimating the run time of an algorithm of order nk | No — derive it |
Check your understanding
1. What is the largest number of comparisons a bubble sort can make on a list of 12 items, and how many passes can it need?
11 + 10 + … + 1 = ½ × 12 × 11 = 66 comparisons, in at most 11 passes.
2. What is the largest number of iterations a binary search can need for an ordered list of 50 items?
2⁵ = 32 ≤ 50 < 64 = 2⁶, so at most 6 iterations.
3. Items of sizes 8, 7, 6, 5 and 4 are packed into bins of capacity 10. Show that the lower bound is 3 but that 4 bins are needed.
Total 30, 30 ÷ 10 = 3. But 8 and 7 cannot share a bin with any other item (the smallest is 4), so each needs its own bin, and 6, 5 and 4 (total 15) need two more: 4 in all.
4. A sublist in a quick sort has 10 items. Which item is the pivot?
The 6th item, ⌈(10 + 1)/2⌉ = 6: the one just right of centre.
5. An algorithm of cubic order takes 5 seconds for 20 items. Estimate the time for 60 items.
5 × (60 ÷ 20)³ = 5 × 27 = 135 seconds.
6. Use first fit to pack 9, 6, 5, 8, 2, 4 into bins of capacity 12, and state whether the result is optimal.
Bin 1: 9, 2 · Bin 2: 6, 5 · Bin 3: 8, 4. Total 34, lower bound ⌈34/12⌉ = 3, so 3 bins is optimal.
Specification checklist
- (D1 1.1) I can explain what an algorithm is and carry out an algorithm given in words or as a flow chart, recording a trace table.
- (D1 1.1) I can describe what an algorithm does from my trace, and count how many times a step or box is used.
- (D1 1.1) I can describe the order of an algorithm and use it to estimate how the run time changes with the size of the problem.
- (D1 1.2) I can carry out a bubble sort in ascending or descending order, showing each pass and counting comparisons and swaps.
- (D1 1.2) I can carry out a quick sort, choosing the middle item of each sublist as the pivot and showing the pivots in every pass.
- (D1 1.3) I can carry out a binary search on an ordered list, including for an item that is not in the list.
- (D1 1.4) I can find a lower bound for the number of bins and decide whether a packing is optimal.
- (D1 1.4) I can use the first-fit, first-fit decreasing and full-bin methods and comment on how good each solution is.