Algorithms, bin packing and sorting

Algorithms, bin packing and sorting

Spec 1.1–2 · Edexcel A-Level Further Maths: Revision notes

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 nn: multiplying nn by kk multiplies an n2n^2 time by about k2k^2.
  • Bin packing: first-fit, first-fit decreasing, full-bin. The lower bound is total ÷\div capacity, rounded up.
  • Bubble sort swaps adjacent pairs; at most n(n−1)2\frac{n(n-1)}{2} comparisons.
  • Quick sort uses a middle pivot: position N+12\frac{N+1}{2} (NN odd) or N+22\frac{N+2}{2} (NN 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. 1

    Input

    aa and bb with a>ba>b

  2. 2

    Divide

    rr = remainder of a÷ba\div b

  3. 3

    Decide

    if r=0r=0, output bb and stop

  4. 4

    Replace

    aa becomes bb, bb becomes rr, then go back to Divide

Euclid's algorithm for the highest common factor

Worked example: trace table

Apply Euclid's algorithm with a=252a=252 and b=105b=105.

In a flow chart, which shape is used for a decision?

Order of an algorithm

The order keeps only the highest power of nn; an n2n^2 algorithm takes about k2k^2 times as long when nn is multiplied by kk.

The size of a problem is the amount of data, such as the number of items nn. The order of an algorithm describes how the running time grows with nn for large nn: it keeps only the highest power. Bubble sort and first-fit bin packing are of order n2n^2.

From slowest growth to fastest: log⁡n\log n, nn, n2n^2, n3n^3, 2n2^n. The order is a guide to efficiency, not an exact time: lower-order terms and constants are ignored.

0102030405060123456nNumber of operations
  • n
  • n²
  • 2ⁿ
How n, n² and 2ⁿ grow as the size of the problem increases.

An algorithm has order n2n^2. About how much longer does it take if nn is multiplied by 55?

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 2020. Items: 7,13,8,3,5,9,4,14,127,13,8,3,5,9,4,14,12. Find the lower bound and pack using first-fit and first-fit decreasing.

Items total 6161 and the bin capacity is 2020. 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 n−1n-1 passes).

Write out the whole list after each pass.

  1. 1

    Compare

    the first two items

  2. 2

    Swap

    if they are in the wrong order

  3. 3

    Move on

    compare the next adjacent pair

  4. 4

    End of pass

    the largest remaining item is in place

One pass of bubble sort
  • Maximum comparisonsn(n−1)2\dfrac{n(n-1)}{2}, so order n2n^2

Worked example

Sort 8,3,6,2,58,3,6,2,5 into ascending order using bubble sort.

What is the maximum number of comparisons to bubble sort 66 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 N+12\frac{N+1}{2} if NN is odd and N+22\frac{N+2}{2} if NN 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. 1

    Choose the pivot

    middle item: N+12\frac{N+1}{2} or N+22\frac{N+2}{2}

  2. 2

    Split

    smaller items left, larger items right, original order kept

  3. 3

    Fix the pivot

    it is now in its final place

  4. 4

    Repeat

    on each sublist with more than one item

Quick sort

Worked example

Sort 23,8,31,15,4,19,2723,8,31,15,4,19,27 using quick sort.

Which item is the pivot for the list 5,9,2,75, 9, 2, 7 (N=4N=4)?

Try an exam question

Items of sizes 6,9,4,7,5,36,9,4,7,5,3 are to be packed into bins of capacity 1212. Find the lower bound for the number of bins, and use the first-fit algorithm to pack the items.

[4 marks]

That's the notes covered.

Carry on to the next subtopic.

Try a question

Find the output when the algorithm is applied to a=84a=84 and b=36b=36.

1 mark, marked against the mark scheme

Revision notes