D1.1.2 Bin packing, bubble sort and quick sort.

Section
D1.1 Algorithms and graph theory
Level
AS & A level
Statement
Bin packing, bubble sort and quick sort.
Guidance
When using the quick sort algorithm, the pivot should be chosen as the middle item of the list.
Since 2018
34 parts, 93 marks · topic pages: Algorithms, sorting, bin packing and graph theory

Back to the checklist

June 2025 · AS Paper 2 (Decision 1) · Q1(a) 3 marks
1 16 10 25 30 13 12 28 22 23 20 The list of ten numbers above is to be sorted into ascending order. (a) Carry out a bubble sort, starting at the left-hand end of the list, to produce the sorted list. You should only give the state of the list after each pass. (3)
June 2025 · Paper 3D (Decision 1) · Q1(a) 3 marks
1. 4.7 2.9 5.5 1.4 5.8 2.8 3.8 6.5 5.1 6.3 4.1 (a) Use the first-fit bin packing algorithm to determine how the numbers listed above can be packed into bins of size 13 (3)
June 2025 · Paper 3D (Decision 1) · Q1(b) 2 marks
(b) Use the first-fit decreasing bin packing algorithm to determine how the numbers listed above can be packed into bins of size 13 (2)
June 2025 · Paper 3D (Decision 1) · Q2(a) 4 marks
2. 271 828 182 845 904 523 536 028 747 135 The list of ten numbers above is to be sorted into descending order. (a) Perform a quick sort on the list to obtain the sorted list. You should show the result of each pass and identify the pivots clearly. (4)
June 2025 · Paper 3D (Decision 1) · Q2(b) 2 marks
A list of n numbers is to be sorted into descending order using bubble sort. (b) Determine, in the worst case, the total number of comparisons required to sort the list. Give your answer as a simplified expression in terms of n. (2)
June 2024 · AS Paper 2 (Decision 1) · Q1(a) 3 marks
1. 4 6.5 7 1.3 2 5 1.5 6 4.5 6 1 The list of eleven numbers shown above is to be sorted into descending order. (a) Carry out a quick sort to produce the sorted list. You should show the result of each pass and identify the pivots clearly. (3)
June 2024 · AS Paper 2 (Decision 1) · Q1(b) 3 marks
(b) Use the first‑fit decreasing bin packing algorithm to pack the numbers into bins of size 10 (3)
June 2024 · AS Paper 2 (Decision 1) · Q1(c) 2 marks
(c) Determine whether your answer to part (b) uses the minimum number of bins. You must justify your answer. (2)
June 2024 · AS Paper 2 (Decision 1) · Q1(d) 1 mark
A different list of eleven numbers is to be sorted into descending order using a bubble sort. The list after the second pass is 4.5 5.6 3.8 6.7 5.4 1.6 4.8 9.1 3.3 1.7 1.5 (d) Explain how you know that at least one of the first two passes of the bubble sort was not carried out correctly. (1)
June 2024 · Paper 3D (Decision 1) · Q1(a) 1 mark
1. The eleven numbers listed above are to be packed into bins of size n where n is a positive integer. When the first-fit bin packing algorithm is applied to the eleven numbers, the bins are packed as shown below. Bin 1: Bin 2: Bin 3: Bin 4: Bin 5: (a) Explain why this packing means that the value of n must be 40 (1)
June 2024 · Paper 3D (Decision 1) · Q1(b) 4 marks
The original list of eleven numbers is to be sorted into descending order. (b) Use a quick sort to obtain the fully sorted list. You must make your pivots clear. (4)
June 2024 · Paper 3D (Decision 1) · Q1(c) 2 marks
(c) Apply the first-fit decreasing bin packing algorithm to the fully sorted list to pack the numbers into bins of size 40 (2)
June 2023 · AS Paper 2 (Decision 1) · Q1 4 marks
1. 67 59 46 71 40 48 53 63 45 54 56 The list of eleven numbers shown above is to be sorted into descending order. Carry out a quick sort to produce the sorted list. You should show the result of each pass and identify the pivots clearly.
June 2023 · Paper 3D (Decision 1) · Q4(a) 1 mark
4. The eleven distinct numbers listed below are to be packed into bins of size 40 15 22 3 9 23 x 5 4 18 20 13 It is known that x • is an integer less than 40 • is the largest number in the list (a) Explain why it is not possible to pack the numbers into 3 bins of size 40 (1)
June 2023 · Paper 3D (Decision 1) · Q4(b) 2 marks
Given that it is possible to pack the numbers into 4 bins of size 40 (b) determine the range of values for x (2)
June 2023 · Paper 3D (Decision 1) · Q4(c) 3 marks
(c) Use the first-fit bin packing algorithm to determine how the numbers can be packed into bins of size 40 (3)
June 2023 · Paper 3D (Decision 1) · Q4(d) 4 marks
(d) Carry out a quick sort to produce a list of the numbers in descending order. You should show the result of each pass and identify your pivots clearly. (4)
June 2023 · Paper 3D (Decision 1) · Q4(e) 2 marks
When the first-fit decreasing bin packing algorithm is applied to the list, neither the 15 nor the 13 is placed in the first bin. (e) Determine the value of x. You must give reasons for your answer. (2)
June 2022 · AS Paper 2 (Decision 1) · Q1(a) 4 marks
1. 55 44 34 59 28 37 41 52 33 42 47 The list of eleven numbers shown above is to be sorted into ascending order. (a) Carry out a quick sort to produce the sorted list. You should show the result of each pass and identify your pivots clearly. (4)
June 2022 · Paper 3D (Decision 1) · Q1(a) 2 marks
1. A gardener needs the following lengths of string. All lengths are in metres. 4.3 6.1 5.1 4.7 2.5 5.9 3.4 1.7 2.1 0.4 1.3 She cuts the lengths from balls of string. Each ball contains 10 m of string. (a) Calculate a lower bound for the number of balls of string the gardener needs. You must make your method clear. (2)
June 2022 · Paper 3D (Decision 1) · Q1(b) 3 marks
(b) Use the first‑fit bin packing algorithm to determine how the lengths could be cut from the balls of string. (3)
June 2022 · Paper 3D (Decision 1) · Q6(b) 5 marks
B C A 24 14 E Figure 4 The weights of the ten arcs in Figure 4 are 17 21 24 14 23 13 15 19 28 20 (b) (i) Starting at the left‑hand end of the above list, sort the list into ascending order using bubble sort. You need only write down the state of the list at the end of each pass. (ii) Find the total number of comparisons performed during the sort. (5)
June 2022 · Paper 3D (Decision 1) · Q6(c) 1 mark
(c) Find the maximum total number of comparisons required to sort the weights of the 10 arcs of K5 into ascending order using bubble sort. (1)
June 2022 · Paper 3D (Decision 1) · Q6(d) 3 marks
It is given that the maximum total number of comparisons required to sort the weights of the arcs of Kn into ascending order using bubble sort is λn(n – 1)(n + 1)(n – 2) where λ is a constant. (d) Determine the maximum total number of comparisons required to sort the weights of the arcs of K50 into ascending order using bubble sort. You must make your method and working clear. (3)
Nov 2021 · Paper 3D (Decision 1) · Q5(a) 4 marks
5. 30 12 5 2 23 18 36 10 15 24 (a) The list of ten numbers above is to be sorted into descending order. Use a quick sort to obtain the sorted list. You should show the result of each pass and identify your pivots clearly. (4)
Nov 2021 · Paper 3D (Decision 1) · Q5(b) 3 marks
The ten numbers are to be packed into bins of size n, where n is a positive integer. When the first-fit bin packing algorithm is applied to the original list of ten numbers, the following allocation is obtained. Bin 1: 30 12 2 Bin 2: 5 23 10 Bin 3: 18 15 Bin 4: 36 Bin 5: 24 (b) Explain why the value of the integer n must be either 44 or 45 (3)
Nov 2021 · Paper 3D (Decision 1) · Q5(c) 3 marks
(c) Use the first-fit decreasing bin packing algorithm to determine how the numbers can be packed into bins of size 45 (3)
Oct 2020 · AS Paper 2 (Decision 1) · Q1(a) 3 marks
1. 3.7 2.5 5.4 1.9 2.7 3.2 3.1 2.7 4.2 2.0 (a) Use the first‑fit bin packing algorithm to determine how the numbers listed above can be packed into bins of size 8.5 (3)
Oct 2020 · AS Paper 2 (Decision 1) · Q1(b) 3 marks
The first‑fit bin packing algorithm is to be used to pack n numbers into bins. The number of comparisons is used to measure the order of the first‑fit bin packing algorithm. (b) By considering the worst case, determine the order of the first‑fit bin packing algorithm in terms of n. You must make your method and working clear. (3)
Oct 2020 · Paper 3D (Decision 1) · Q5(a) 3 marks
5. The nine distinct numbers in the following list are to be packed into bins of size 50 23 17 19 x 24 8 18 10 21 When the first-fit bin packing algorithm is applied to the numbers in the list it results in the following allocation. Bin 1: 23 17 8 Bin 2: 19 x 10 Bin 3: 24 18 Bin 4: 21 (a) Explain why 13 < x < 21 (3)
Oct 2020 · Paper 3D (Decision 1) · Q5(b) 2 marks
The same list of numbers is to be sorted into descending order. A bubble sort, starting at the left-hand end of the list, is to be used to obtain the sorted list. After the first complete pass the list is 23 19 17 24 x 18 10 21 8 (b) Using this information, write down the smallest interval that must contain x, giving your answer as an inequality. (2)
Oct 2020 · Paper 3D (Decision 1) · Q5(c) 2 marks
When the first-fit decreasing bin packing algorithm is applied to the nine distinct numbers it results in the following allocation. Bin 1: 24 23 Bin 2: 21 19 10 Bin 3: 18 17 x Bin 4: 8 Given that only one of the bins is full and that x is an integer, (c) calculate the value of x. You must give reasons for your answer. (2)
June 2019 · Paper 3D (Decision 1) · Q1(a) 2 marks
1. 2.1 1.7 3.0 1.9 3.2 1.2 3.3 1.4 1.5 0.2 (a) Use the first-fit bin packing algorithm to determine how the numbers listed above can be packed into bins of size 5 (2)
June 2019 · Paper 3D (Decision 1) · Q1(b) 4 marks
The list of numbers is now to be sorted into descending order. (b) Perform a quick sort on the original list to obtain the sorted list. You should show the result of each pass and identify your pivots clearly. (4)

Find an Edexcel Further Maths tutor

Stuck on this? Book a trial lesson with our Further Maths tutor.

Prefer email? Send an enquiry

If you are under 18, please include a parent's contact details. Enquiries go to enquiries@alevelfurthermathstutor.com and are deleted once handled.