Maths › Decision Mathematics 1 › Algorithms, sorting and bin packing
Algorithms, sorting and bin packing
An algorithm is a sequence of instructions precise enough to follow without judgement. Once a method is written that precisely you can count how long it takes and ask whether it always gives the best answer.
Builds on The structure of proof and Sequences and sigma notation.
IN THIS TOPIC
- Follow an algorithm given as text or a flow chart, and record the trace.
- State the order of an algorithm and use it to predict running time.
- Perform bubble sort and quick sort, showing every pass.
- Apply the three bin packing algorithms and compare the result with a lower bound.
COMMON MISCONCEPTION
A good algorithm is one that always finds the best possible answer.
Following instructions exactly
An algorithm is a finite sequence of precise instructions that solves a problem. Exam questions supply one and ask for a trace, which is a table with a column per variable and a row per pass, filled in mechanically. Marks go for following it exactly, including the steps that look pointless. A shortcut that reaches the same answer earns nothing.
The order of an algorithm says how the running time grows with the size n of the problem. A method that compares every pair of items is quadratic, so doubling the list quadruples the work and trebling it multiplies the work by nine. That number is the usual measure of a good algorithm, and plenty of perfectly good algorithms carry no guarantee of finding the best answer at all.
Two sorts
Bubble sort compares each neighbouring pair along the list and swaps them when they are out of order. One pass delivers the largest item to the end, so each pass is one shorter than the last, and the algorithm stops after a pass that makes no swaps. Say that final pass happened; it is where the mark is.
Quick sort picks a pivot, in this specification the middle item, and splits the list into those below it and those above it, keeping the original order within each part. The pivot is now fixed in place, and the method repeats on each sublist until every item has been a pivot.
WORKED EXAMPLE
Two sorts on the same list
Sort 5, 12, 3, 9, 1 into increasing order.
Bubble sort, first pass: compare and swap along the list to get 5, 3, 9, 1, 12. The largest is now in place.
Second pass: 3, 5, 1, 9. Third: 3, 1, 5. Fourth: 1, 3. A fifth pass makes no swaps, which is how the algorithm knows to stop.
Quick sort instead picks the middle item, 3, as pivot, giving 1 to its left and 5, 12, 9 to its right, and repeats on each sublist. Both end at 1, 3, 5, 9, 12.
Packing bins, and how well
Bin packing puts items into bins of fixed size, and the specification names three methods. First fit takes the items in the order given and puts each into the first bin with room. First fit decreasing sorts them largest first, then does the same. Full bin packing uses observation to spot groups of items that fill a bin exactly, packs those first, and finishes off whatever is left by first fit.
None of the three is guaranteed optimal. First fit decreasing is usually better than first fit and never much worse. Full bin often is often better than both, but it needs a human eye and is hard to program.
The lower bound is the total of the items divided by the bin size, rounded up. Achieve it and the packing is certainly optimal and the question is finished. Miss it and the answer might still be optimal, but you would have to argue the point.
GUIDED PRACTICE
Packing by three methods
Pack the items 4, 8, 5, 1, 7, 6, 1, 4, 2, 2 into bins of size 10 by first fit, by first fit decreasing and by full bin packing, and compare with the lower bound.
Show the working
Lower bound: the total is 40, so at least 40/10 = 4 bins.
First fit gives (4, 5, 1), (8, 1), (7, 2), (6, 4), (2): 5 bins.
First fit decreasing gives (8, 2), (7, 2, 1), (6, 4), (5, 4, 1): 4 bins.
Full bins are easy to spot here: 8 + 2, 5 + 4 + 1, 7 + 2 + 1 and 6 + 4, again 4 bins and every one of them exactly full.
Two methods match the lower bound, so 4 bins is optimal and no further argument is needed.
ASSESSMENT FOCUS
- Follow the algorithm exactly as written, including steps that look redundant.
- Show every pass of a sort as well as the final order. The working is what is marked.
- For quick sort, take the middle item as pivot and say so.
- Name which bin packing algorithm you are using; the mark scheme checks the method, not only the number of bins.
- Always compute the lower bound for a bin packing question and compare it with your answer.
CHECK YOURSELF
Items of size 6, 3, 5, 4, 2 are packed into bins of size 8. Find the lower bound and pack them by first fit decreasing.
Show a hint
Total over bin size, rounded up, then sort and pack.
Show the answer
Total 20, so the lower bound is 20/8 = 2.5, rounded up to 3 bins. Sorted: 6, 5, 4, 3, 2. First fit decreasing gives (6, 2), (5, 3), (4): 3 bins, which matches the bound.
An algorithm is a precise finite recipe, and its order says how the work grows with the size of the problem.
First fit, first fit decreasing and full bin packing are all quick and none is guaranteed optimal.
Always compare a packing with the lower bound of total size over bin size, rounded up.
WORKBOOK
Printable practice for this topic: original exam-style questions with room to work, and a fully worked answer book. Free to use; please do not redistribute or sell.
Or read them with their worked answers on the algorithms, sorting and bin packing questions page.
CHECK YOUR PROGRESS
Rate how confident you feel with each objective for this lesson. Ratings are saved in this browser, on this device, unless you sign in.
- Follow an algorithm given as text or a flow chart, and record the trace.
- State the order of an algorithm and use it to predict running time.
- Perform bubble sort and quick sort, showing every pass.
- Apply the three bin packing algorithms and compare the result with a lower bound.
Open the full revision checklist to see every objective in the course in one place.