Easy -1.8 This is a routine recall question testing basic knowledge of bubble sort mechanics and first-fit decreasing algorithm. Part (a) requires describing standard algorithm steps, parts (b-c) involve straightforward application with minimal computation (the list is nearly sorted), and part (d) is a textbook bin-packing exercise requiring only arithmetic checks against capacity 4.
2. (a) (i) Describe how to carry out the first pass of a bubble sort when it is used to sort a list of \(n\) numbers into ascending order.
(ii) Write down the circumstances under which a bubble sort stops.
A bubble sort, starting at the left-hand end of the list, is used to sort a list of ten numbers into ascending order. After a number of passes the list reads
0.9
0.5
0.7
1.2
1.5
1.4
1.1
1.7
2.2
3.2
(b) Determine the maximum number of passes that could have taken place on this list. You must give a reason for your answer.
(c) Complete the bubble sort to produce a list of the numbers in ascending order. You only need to give the state of the list after each complete pass.
(d) Use the first-fit decreasing bin packing algorithm to determine how the ten numbers listed above can be packed into bins of size 4
(a)(i) In the first pass of a bubble sort we compare the first value with the second and swap if the first is larger than the second. We then compare the value that is second with the third value and swap if the second is larger than the third. Continue like this until the end of the list.
M1 A1 B1 B1 (4)
a1M1: Compare first value with second value (allow 'compare first and second') and swap if first is larger (oe) - allow 'wrong order' for M1 only – must be clear that the first value is being compared with the second value. a1A1: Compare second with third (not just 'next two') and so on until the end of the list (oe e.g. 'all', 'last two', 'last') – must be clear that all the list of numbers has been considered. a1B1: CAO – one of 'until only one item left' (oe e.g. 'stops after \(n-1\) passes' but not just a statement along the lines of 'until all the required passes have been done') or 'until no swaps' (oe e.g. 'one pass gives the same result as the next pass') – no marks though if they only say 'when the list is in order' (oo). a2B1: CAO – both reasons stated correctly.
(a)(ii) Bubble sort stops when we either have a list of length 1 to sort or we have a pass in which no swaps were made.
B1 B1 (4)
b1B1: CAO (3). b2B1 dep: Correct reasoning – dependent on previous B mark – must mention that the three largest numbers are in the correct position (and not just that 1.7, 2.2 and 3.2 are in the correct position).
(b) Maximum number of passes is 3 as only the three largest values are in the correct position.
B1 B1dep (2)
(c) [Table showing 7 passes of bubble sort with values being compared and swapped]
M1 A1 A1ft A1cso (4)
c1M1: Bubble sort. Consistent direction throughout sort, and first pass correct – do check these carefully as some candidates show the result of each comparison and swap in their first pass. No marks for quick sort or descending order. c1A1: Second and third passes correct – so end six numbers in place after third pass. c2A1ft: Their fourth and fifth passes correct following through from the candidate's third pass – so end eight numbers in place after fifth pass. c3A1: CSO (correct solution only) – with sixth pass showing no swaps (not just a statement that the list is in order after a fifth pass).
(d) Bin 1: 3.2 0.7; Bin 2: 2.2 [1.7]; Bin 3: [1.5] 1.4 1.1; Bin 4: 1.2 0.9 0.5
M1 A1 A1 (3)
d1M1: First four items placed correctly (the boxed values). Condone cumulative totals for M1 only. d1A1: First eight items placed correctly (the boxed and underlined values) – any additional/repeated values scores M1 only. d2A1: CSO.
13 marks
| Answer | Marks | Guidance |
|--------|-------|----------|
| (a)(i) In the first pass of a bubble sort we compare the first value with the second and swap if the first is larger than the second. We then compare the value that is second with the third value and swap if the second is larger than the third. Continue like this until the end of the list. | M1 A1 B1 B1 (4) | a1M1: Compare first value with second value (allow 'compare first and second') and swap if first is larger (oe) - allow 'wrong order' for M1 only – must be clear that the first value is being compared with the second value. a1A1: Compare second with third (not just 'next two') and so on until the end of the list (oe e.g. 'all', 'last two', 'last') – must be clear that all the list of numbers has been considered. a1B1: CAO – one of 'until only one item left' (oe e.g. 'stops after $n-1$ passes' but not just a statement along the lines of 'until all the required passes have been done') or 'until no swaps' (oe e.g. 'one pass gives the same result as the next pass') – no marks though if they only say 'when the list is in order' (oo). a2B1: CAO – both reasons stated correctly. |
| (a)(ii) Bubble sort stops when we either have a list of length 1 to sort or we have a pass in which no swaps were made. | B1 B1 (4) | b1B1: CAO (3). b2B1 dep: Correct reasoning – dependent on previous B mark – must mention that the three largest numbers are in the correct position (and not just that 1.7, 2.2 and 3.2 are in the correct position). |
| (b) Maximum number of passes is 3 as only the three largest values are in the correct position. | B1 B1dep (2) | |
| (c) [Table showing 7 passes of bubble sort with values being compared and swapped] | M1 A1 A1ft A1cso (4) | c1M1: Bubble sort. Consistent direction throughout sort, and first pass correct – do check these carefully as some candidates show the result of each comparison and swap in their first pass. No marks for quick sort or descending order. c1A1: Second and third passes correct – so end six numbers in place after third pass. c2A1ft: Their fourth and fifth passes correct following through from the candidate's third pass – so end eight numbers in place after fifth pass. c3A1: CSO (correct solution only) – with sixth pass showing no swaps (not just a statement that the list is in order after a fifth pass). |
| (d) Bin 1: 3.2 0.7; Bin 2: 2.2 [1.7]; Bin 3: [1.5] 1.4 1.1; Bin 4: 1.2 0.9 0.5 | M1 A1 A1 (3) | d1M1: First four items placed correctly (the boxed values). Condone cumulative totals for M1 only. d1A1: First eight items placed correctly (the boxed and underlined values) – any additional/repeated values scores M1 only. d2A1: CSO. |
| | 13 marks | |
---
2. (a) (i) Describe how to carry out the first pass of a bubble sort when it is used to sort a list of $n$ numbers into ascending order.\\
(ii) Write down the circumstances under which a bubble sort stops.
A bubble sort, starting at the left-hand end of the list, is used to sort a list of ten numbers into ascending order. After a number of passes the list reads\\
0.9\\
0.5\\
0.7\\
1.2\\
1.5\\
1.4\\
1.1\\
1.7\\
2.2\\
3.2\\
(b) Determine the maximum number of passes that could have taken place on this list. You must give a reason for your answer.\\
(c) Complete the bubble sort to produce a list of the numbers in ascending order. You only need to give the state of the list after each complete pass.\\
(d) Use the first-fit decreasing bin packing algorithm to determine how the ten numbers listed above can be packed into bins of size 4\\
\hfill \mbox{\textit{Edexcel D1 2020 Q2 [13]}}