Maths › Decision Mathematics 1 › Algorithms, sorting and bin packing
Algorithms, sorting and bin packing
A recipe that anyone could 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.
- Perform bubble sort and quick sort, showing every pass.
- Apply bin packing algorithms and compare them with a lower bound.
WHAT YOU PROBABLY THINK
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: 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 seem pointless, rather than for shortcuts that get the same answer.
The order of an algorithm says how the running time grows with the size n of the problem. A sort that compares every pair is order n², so doubling the list quadruples the work. That number, rather than the answer, is the usual measure of a good algorithm, and many perfectly good ones are not guaranteed to find the best answer at all: the opening claim would rule out most of this paper.
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. 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. Neither is guaranteed to be optimal, but the second is usually better and never much worse.
The lower bound is the total of the items divided by the bin size, rounded up. If an algorithm achieves it, the packing is certainly optimal and the question is finished. If it does not, the answer might still be optimal and further justification is needed.
YOUR TURN
Packing by two methods
Pack the items 4, 8, 5, 1, 7, 6, 1, 4, 2, 2 into bins of size 10 by first fit and by first fit decreasing, 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.
The second matches the lower bound, so it is optimal and no further work is needed.
THE EXAM BIT
- 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.
- 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
T
o
t
a
l
2
0
,
s
o
t
h
e
l
o
w
e
r
b
o
u
n
d
i
s
2
0
/
8
=
2
.
5
,
r
o
u
n
d
e
d
u
p
t
o
3
b
i
n
s
.
S
o
r
t
e
d
:
6
,
5
,
4
,
3
,
2
.
F
i
r
s
t
f
i
t
d
e
c
r
e
a
s
i
n
g
g
i
v
e
s
(
6
,
2
)
,
(
5
,
3
)
,
(
4
)
:
3
b
i
n
s
,
w
h
i
c
h
m
a
t
c
h
e
s
t
h
e
b
o
u
n
d
.
An algorithm is a precise finite recipe; its order says how the work grows with the size of the problem.
Bin packing algorithms are quick but not guaranteed optimal, so always compare the answer with the lower bound.
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.
CHECK YOUR PROGRESS
Rate how confident you feel with each objective for this lesson. Ratings are saved in this browser, on this device only.
- Follow an algorithm given as text or a flow chart, and record the trace.
- Perform bubble sort and quick sort, showing every pass.
- Apply bin packing algorithms and compare them with a lower bound.
Open the full revision checklist to see every objective in the course in one place.
No animated video for this topic yet; these notes stand alone.