Contents · 0% complete

Learning objectives
Core idea
Key formulae
Worked examples
Explore the graph
Common mistakes
Exam tip
Guided practice
Practice questions
Challenge
Summary
Quick quiz
Same topic, different board
Past paper questions

LearnYMA01WDM11 · Decision Mathematics 1AlgorithmsSorting, searching and bin packing

Algorithms · Subtopic 1 of 1

Algorithms: Sorting and Bin Packing

An algorithm is a finite list of precise instructions. Bubble sort compares neighbours and swaps; quick sort splits around a pivot. Bin packing puts items into the fewest bins: first-fit, first-fit decreasing (FFD) and full-bin methods, compared with the lower bound $\left\lceil\frac{\text{total}}{\text{bin size}}\right\rceil$ .

Edexcel YMA01 WDM11Edexcel 9FM0 Option≈ 45 minRevision 1 · updated 2026-10-27

Practise this topicTimed test Ask Salam TutorSwitch board

Section 1 of 14

Learning objectives

Trace an algorithm given in words or as a flow chart.
Carry out bubble sort, quick sort and binary search.
Apply first-fit, first-fit decreasing and full-bin packing; find lower bounds.
Use the order of an algorithm to estimate run times.

Pause and think

You must load boxes of 6, 5, 4, 3 and 2 kg into crates holding 10 kg each. What's the fewest crates possible?

Section 2 of 14

Core idea

Start hereLoading the van

A removal firm has boxes of different weights and vans with a weight limit. Trying every arrangement would take forever. Instead they follow a short, precise recipe that gives a good answer fast. That recipe is an algorithm.

The big idea

An algorithm is a finite sequence of precise steps. Sorting algorithms put lists in order; bin-packing algorithms fill containers. We judge them by correctness, by how close to optimal they get, and by how their run time grows with the input size (order).

1. Sorting

Worked exampleOne pass of bubble sort

Carry out the first pass of a bubble sort (ascending) on $5,1,4,2,8$ .

Goal: List after pass 1.
Strategy: Compare neighbours left to right; swap if out of order.

$5,1\to1,5$
Swap.
$5,4\to4,5;\quad5,2\to2,5$
Swap twice more.
$5,8$
In order; no swap.

Answer

1,4,2,5,8

. The largest value has bubbled to the end.

✓ Check

4

comparisons for

5

items ✓.

Worst-case comparisons for bubble sort

$(n-1)+(n-2)+\dots+1$
Each pass fixes one more item at the end, so needs one fewer comparison.
$=\tfrac12n(n-1)$
Sum of the first $n-1$ integers.

Quadratic order: doubling

n

roughly quadruples the time.

2. Bin packing

\text{lower bound}=\left\lceil\frac{\text{total size}}{\text{bin capacity}}\right\rceil

$\lceil\ \rceil$: round up to the next whole number.

Worked exampleFirst-fit decreasing

Pack $6,5,4,3,2$ into bins of capacity $10$ .

Goal: Number of bins.
Strategy: Sort descending, then first-fit.

$6\to B_1;\ 5\to B_2$
5 doesn't fit with 6.
$4\to B_1\ (10)$
First bin with room.
$3\to B_2\ (8);\ 2\to B_2\ (10)$
$B_1$ is full.

Answer2 bins, equal to the lower bound

\lceil20/10\rceil=2

, so optimal.

✓ CheckEvery item placed; no bin exceeds 10 ✓.

Bin-packing methods

Drawing diagram…

Three methods, from quickest to most careful.

Common misconceptionLower bound isn’t always reachable For

8,7,5,4,3,3

the bound is

3

but nothing fits with the

8

, so

4

bins are needed.

Key takeawayQuick sort Choose the middle item as pivot; write smaller items before it and larger after, keeping their order; repeat on each sub-list.

Pause and think

A cubic-order algorithm takes $5$ s for $200$ items. Estimate for $400$ .

Summary

Bubble sort: $\le\frac12n(n-1)$ comparisons.
Quick sort: pivots.
Bin packing: compare with $\lceil\text{total}/\text{capacity}\rceil$ .
Order predicts scaling.

Algorithm: Finite list of precise instructions.
Heuristic: Method that gives a good, not necessarily optimal, answer.
Order: How run time grows with input size.

HistoryAl-Khwarizmi. The word "algorithm" comes from the 9th-century Baghdad scholar Muhammad al-Khwarizmi, whose book on calculation spread Hindu–Arabic numerals to Europe.

Fun factSorting at scale. Google sorted a petabyte (a million gigabytes) of data in 33 minutes in 2011, using a distributed sort.

Section 3 of 14

Key formulae

Lower bound

\text{bins}\ge\left\lceil\frac{\sum\text{item sizes}}{\text{bin capacity}}\right\rceil

Bubble sort

\text{at most }\tfrac12n(n-1)\ \text{comparisons}

Order

O(n^2):\ \text{time}\times k^2\ \text{when }n\times k

TrickQuick sort pivot. Use the middle item (round up for an even list) as the pivot, as Edexcel does. Write items smaller than the pivot to its left in their original order.

Section 4 of 14

Worked examples

Example 1 · FFD0 / 3 steps

Pack

6,5,4,3,2

into bins of size

10

using first-fit decreasing.

Example 2 · Order0 / 2 steps

A quadratic-order algorithm takes

2

s for

100

items. Estimate the time for

300

Section 5 of 14

Explore the graph

Comparisons: bubble sort vs quick sort

Loading the interactive graph…

Try this

$x$ is the number of items. The steeper curve is bubble sort's worst case, $\frac12n(n-1)$ .
Quick sort's typical $n\log_2n$ grows far more slowly.

Quadratic vs $n\log n$ .

In the real worldLorry loading. Delivery firms solve bin packing every day to load lorries and pallets; exact answers are too slow, so they use FFD-style heuristics.

Section 6 of 14

Common mistakes

IncorrectLower bound

\frac{20}{10}

rounded down

CorrectRound up

You can't use part of a bin.

IncorrectFirst-fit puts items in the emptiest bin

CorrectThe first bin it fits

Always scan from bin 1.

IncorrectStopping bubble sort early without checking

CorrectStop after a pass with no swaps

That's the stopping condition.

Optimal bin packing

FFD: close enough, and done before lunch.

Section 7 of 14

Exam tip

Exam tipShow every pass. For sorts, write the list after each pass and mark pivots or the end of each pass; method marks depend on it.

Section 8 of 14

Guided practice

SA-DM-AL-G012 marksL1 FoundationNon-calculatorBin packing

Items of size

8,7,5,4,3,3

are packed into bins of size

10

. Find the lower bound for the number of bins.

Salam Academy Original Practice · Proposed mark scheme

Section 9 of 14

Practice questions

SA-DM-AL-0012 marksL2 StandardNon-calculatorBin packing

Use first-fit on the items

3,6,5,4,2

(in this order) with bins of size

10

. How many bins are used?

Salam Academy Original Practice · Proposed mark scheme

SA-DM-AL-0021 markL1 FoundationNon-calculatorSorting

What is the maximum number of comparisons a bubble sort can need for

6

items?

Salam Academy Original Practice · Proposed mark scheme

SA-DM-AL-0032 marksL2 StandardNon-calculatorOrder

An algorithm of quadratic order takes

2

s for

100

items. Estimate the time in seconds for

300

items.

Salam Academy Original Practice · Proposed mark scheme

SA-DM-AL-0041 markL2 StandardNon-calculatorSorting

Binary search is used on an ordered list of

15

names. Using the middle item each time, what is the maximum number of items examined?

Salam Academy Original Practice · Proposed mark scheme

More questions on every skill in this subtopic are in the question bank under Practise.

Section 10 of 14

Challenge

SA-DM-AL-0052 marksL3 ExamNon-calculatorBin packing

For

8,7,5,4,3,3

in bins of size

10

, find the fewest bins actually possible.

Salam Academy Original Practice · Proposed mark scheme

Section 11 of 14

Summary

Bubble sort: neighbour swaps.
Quick sort: pivots.
Lower bound: total ÷ capacity, round up.
FFD usually beats first-fit.

Section 12 of 14

Quick quiz

Q1 · SA-DM-AL-Q011 markL1 FoundationNon-calculatorBin packing

First-fit decreasing differs from first-fit because it

Salam Academy Original Practice · Proposed mark scheme

Section 13 of 14

Same topic, different board

Specification: A level Further Mathematics 9FM0
Where: Decision 1 · Algorithms and graph theory
Expected: Follow and trace algorithms (flow charts, text); bubble sort, quick sort, binary search; first-fit, first-fit decreasing and full-bin packing; lower bounds; order of an algorithm.
Calculator: Permitted; show enough working to earn the method marks.
Typical style: Edexcel often opens with a routine part and builds to a "show that" or "prove" part.
Open in: YMA01 · WDM11 9FM0 · Option

Section 14 of 14

Past paper questions

No past paper questions are tagged to this subtopic yet. We add papers every week.

Browse past papers

Salam Academy original content · Content status: reviewed and published. Syllabus mapping: Pearson Edexcel YMA01, 2018 specification (official specification).