Fig. 1 shows test data from a drone survey. The computer must arrange image file sizes in ascending order before uploading them over a network. The diagram ...
Question 1 Report
Fig. 1 shows test data from a drone survey. The computer must arrange image file sizes in ascending order before uploading them over a network. The diagram compares the number of adjacent comparisons made by bubble sort in successive passes. The final pass has no red swap arrows.
(a) State the sorted array shown at the end of Fig. 1. [1]
(b) Give the total number of swaps shown. [2]
(c) State the pass on which an optimised bubble sort can stop. [1]
(d) Explain why no further pass is needed at this point. [2]
(e) Give the maximum number of comparisons an unoptimised bubble sort makes when sorting five values. [3]
Answer Details
Bubble sort repeatedly compares adjacent values. For ascending order, a pair is swapped when the left value is larger than the right value.
- (a) The sorted array shown is 6, 9, 14, 18, 22. [1]
- (b) The diagram shows four swaps on pass 1, two on pass 2, one on pass 3, and none on pass 4: \[4+2+1+0=7\] So there are 7 swaps. [2]
- (c) An optimised bubble sort can stop on pass 4. [1]
- (d) No swaps mean that every adjacent pair is in the correct order. Therefore the entire array is sorted, so another pass cannot improve it. [2]
- (e) For five values, an unoptimised sort makes \[4+3+2+1=10\] comparisons. [3]
Download The App On Google Playstore
Everything you need to excel in your exams
