Algorithms, bin packing and sorting
Studying this course? Keep your progress in one place.
Key facts
- An algorithm is a finite, unambiguous sequence of steps; use a trace table to implement it.
- The order of an algorithm is how running time grows with : multiplying by multiplies an time by about .
- Bin packing: first-fit, first-fit decreasing, full-bin. The lower bound is total capacity, rounded up.
- Bubble sort swaps adjacent pairs; at most comparisons.
- Quick sort uses a middle pivot: position ( odd) or ( even).
Algorithms and flow charts
A finite, unambiguous sequence of steps; follow it exactly and keep a trace table.
An algorithm is a finite, unambiguous sequence of steps that solves a problem, given as numbered text or a flow chart. A flow chart uses boxes for input/output and instructions, diamonds for decisions and arrows for flow, with start and stop terminals.
To implement an algorithm, follow each step exactly, keeping a trace table of each variable after every step. Do not skip steps or work in your head.
- 1
Input
and with
- 2
Divide
= remainder of
- 3
Decide
if , output and stop
- 4
Replace
becomes , becomes , then go back to Divide
Worked example: trace table
Apply Euclid's algorithm with and .
- 1
has remainder , so , .
- 2
has remainder , so , .
- 3
has remainder , so output .
In a flow chart, which shape is used for a decision?
Order of an algorithm
The order keeps only the highest power of ; an algorithm takes about times as long when is multiplied by .
The size of a problem is the amount of data, such as the number of items . The order of an algorithm describes how the running time grows with for large : it keeps only the highest power. Bubble sort and first-fit bin packing are of order .
From slowest growth to fastest: , , , , . The order is a guide to efficiency, not an exact time: lower-order terms and constants are ignored.
- n
- n²
- 2ⁿ
An algorithm has order . About how much longer does it take if is multiplied by ?
Bin packing
Find the lower bound, then pack with first-fit or first-fit decreasing; none of these is guaranteed optimal unless the lower bound is met.
Bin packing fits items into the fewest bins of a fixed capacity. The lower bound on the number of bins is the total size divided by the capacity, rounded up. These algorithms are heuristics: none guarantees the optimum, except when the lower bound is met.
First-fit
- Take items in the given order
- Place each in the first bin with room
First-fit decreasing
- Sort into descending order first
- Then apply first-fit
Full-bin
- Look for combinations
- That exactly fill a bin
Worked example
Capacity . Items: . Find the lower bound and pack using first-fit and first-fit decreasing.
- 1
Total: . , so at least bins.
- 2
First-fit: , , , , . That is bins.
- 3
Sort descending: .
- 4
First-fit decreasing: , , , . That is bins.
Items total and the bin capacity is . What is the lower bound on the number of bins?
Bubble sort
Compare adjacent items from the left and swap any pair in the wrong order; the largest item reaches the end each pass.
Bubble sort compares adjacent items from the left, swapping any pair in the wrong order. After the first pass the largest item is in its final place; each later pass can ignore the items already placed. The list is sorted when a pass makes no swaps (or after passes).
Write out the whole list after each pass.
- 1
Compare
the first two items
- 2
Swap
if they are in the wrong order
- 3
Move on
compare the next adjacent pair
- 4
End of pass
the largest remaining item is in place
- Maximum comparisons, so order
Worked example
Sort into ascending order using bubble sort.
- 1
Pass 1: . The is in place.
- 2
Pass 2: .
- 3
Pass 3: .
- 4
Pass 4: no swaps, so the list is sorted.
What is the maximum number of comparisons to bubble sort items?
Quick sort
Choose the middle item as pivot, put smaller items to its left and larger to its right in their original order, then repeat on each sublist.
Quick sort chooses a pivot, the middle item: position if is odd and if is even. Items smaller than the pivot go to its left and larger ones to its right, each keeping the original order. The pivot is now in its final place.
Repeat on each sublist with more than one item until every item is a pivot or alone. Quick sort is usually much faster than bubble sort on long lists.
- 1
Choose the pivot
middle item: or
- 2
Split
smaller items left, larger items right, original order kept
- 3
Fix the pivot
it is now in its final place
- 4
Repeat
on each sublist with more than one item
Worked example
Sort using quick sort.
- 1
, pivot is item , which is : .
- 2
Left, , pivot is item , which is : .
- 3
Right, , pivot is item , which is : .
- 4
Then , pivot : . Then pivot : .
Which item is the pivot for the list ()?
Try an exam question
Items of sizes are to be packed into bins of capacity . Find the lower bound for the number of bins, and use the first-fit algorithm to pack the items.
[4 marks]
- [1]Total , and , so the lower bound is .
- [1]First-fit: in bin 1, in bin 2, in bin 1.
- [1] in bin 3, in bin 3, in bin 2.
- [1]Bins: , , : bins, equal to the lower bound, so optimal.
That's the notes covered.
Carry on to the next subtopic.
Try a question
Find the output when the algorithm is applied to and .
1 mark, marked against the mark scheme
Find the output when the algorithm is applied to and .
1 mark, marked against the mark scheme