Salam Academy
Sign inCreate account
Contents · 0% complete
  1. Learning objectives
  2. Core idea
  3. Key formulae
  4. Worked examples
  5. Explore the graph
  6. Common mistakes
  7. Exam tip
  8. Guided practice
  9. Practice questions
  10. Challenge
  11. Summary
  12. Quick quiz
  13. Same topic, different board
  14. Past paper questions
Learn9FM0Option · Decision Mathematics 1Algorithms and graph theorySorting, searching and bin packing
Algorithms and graph theory · Subtopic 1 of 2

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 ⌈totalbin size⌉\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 testAsk Salam Tutor
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,85,1,4,2,8.

Goal
List after pass 1.
Strategy
Compare neighbours left to right; swap if out of order.
  1. 5,1→1,55,1\to1,5
    Swap.
  2. 5,4→4,5;5,2→2,55,4\to4,5;\quad5,2\to2,5
    Swap twice more.
  3. 5,85,8
    In order; no swap.
Answer1,4,2,5,81,4,2,5,8. The largest value has bubbled to the end.
✓ Check44 comparisons for 55 items ✓.
Worst-case comparisons for bubble sort
  1. (n−1)+(n−2)+⋯+1(n-1)+(n-2)+\dots+1
    Each pass fixes one more item at the end, so needs one fewer comparison.
  2. =12n(n−1)=\tfrac12n(n-1)
    Sum of the first n−1n-1 integers.
Quadratic order: doubling nn roughly quadruples the time.

2. Bin packing

lower bound=⌈total sizebin capacity⌉\text{lower bound}=\left\lceil\frac{\text{total size}}{\text{bin capacity}}\right\rceil
where
⌈ ⌉\lceil\ \rceil
round up to the next whole number.
Worked exampleFirst-fit decreasing

Pack 6,5,4,3,26,5,4,3,2 into bins of capacity 1010.

Goal
Number of bins.
Strategy
Sort descending, then first-fit.
  1. 6→B1; 5→B26\to B_1;\ 5\to B_2
    5 doesn't fit with 6.
  2. 4→B1 (10)4\to B_1\ (10)
    First bin with room.
  3. 3→B2 (8); 2→B2 (10)3\to B_2\ (8);\ 2\to B_2\ (10)
    B1B_1 is full.
Answer2 bins, equal to the lower bound ⌈20/10⌉=2\lceil20/10\rceil=2, so optimal.
✓ CheckEvery item placed; no bin exceeds 10 ✓.
Bin-packing methods

Three methods, from quickest to most careful.

Common misconceptionLower bound isn’t always reachable For 8,7,5,4,3,38,7,5,4,3,3 the bound is 33 but nothing fits with the 88, so 44 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 55 s for 200200 items. Estimate for 400400.

Summary

  • Bubble sort: ≤12n(n−1)\le\frac12n(n-1) comparisons.
  • Quick sort: pivots.
  • Bin packing: compare with ⌈total/capacity⌉\lceil\text{total}/\text{capacity}\rceil.
  • Order predicts scaling.
Key words
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 boundbins≥⌈∑item sizesbin capacity⌉\text{bins}\ge\left\lceil\frac{\sum\text{item sizes}}{\text{bin capacity}}\right\rceil
Bubble sortat most 12n(n−1) comparisons\text{at most }\tfrac12n(n-1)\ \text{comparisons}
OrderO(n2): time×k2 when n×kO(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,26,5,4,3,2 into bins of size 1010 using first-fit decreasing.
    Example 2 · Order0 / 2 steps
    A quadratic-order algorithm takes 22 s for 100100 items. Estimate the time for 300300.
      Section 5 of 14

      Explore the graph

      Comparisons: bubble sort vs quick sort
      Loading the interactive graph…
      Try this
      1. xx is the number of items. The steeper curve is bubble sort's worst case, 12n(n−1)\frac12n(n-1).
      2. Quick sort's typical nlog⁡2nn\log_2n grows far more slowly.

      Quadratic vs nlog⁡nn\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 2010\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,38,7,5,4,3,3 are packed into bins of size 1010. Find the lower bound for the number of bins.

      Sign in or create a free account to check answers, get hints and track your progress.

      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,23,6,5,4,2 (in this order) with bins of size 1010. How many bins are used?

      Sign in or create a free account to check answers, get hints and track your progress.

      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 66 items?

      Sign in or create a free account to check answers, get hints and track your progress.

      Salam Academy Original Practice · Proposed mark scheme
      SA-DM-AL-0032 marksL2 StandardNon-calculatorOrder
      An algorithm of quadratic order takes 22 s for 100100 items. Estimate the time in seconds for 300300 items.

      Sign in or create a free account to check answers, get hints and track your progress.

      Salam Academy Original Practice · Proposed mark scheme
      SA-DM-AL-0041 markL2 StandardNon-calculatorSorting
      Binary search is used on an ordered list of 1515 names. Using the middle item each time, what is the maximum number of items examined?

      Sign in or create a free account to check answers, get hints and track your progress.

      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,38,7,5,4,3,3 in bins of size 1010, find the fewest bins actually possible.

      Sign in or create a free account to check answers, get hints and track your progress.

      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
      Choose one option

      Sign in or create a free account to check answers, get hints and track your progress.

      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 · WDM119FM0 · 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 9FM0, First teaching 2017 (official specification).