No topics match this filter.
Practise 30 exam-style questions on Bubble sort for Cambridge IGCSE Computer Science (Paper 2). Write your answer as you would in the exam and get it marked in seconds against the mark scheme, point by point, with an AI tutor on hand if you get stuck.
Here are 4 of the questions in this topic, each with a model answer, an explanation of why it earns the marks and the mark scheme an examiner would use.
The array List[1:5] holds the values 6, 2, 9, 4, 1.
State the number of swaps made during the first pass of a bubble sort that sorts List into ascending order.
3
6 and 2 swap; 6 and 9 are in order; then 9 swaps with 4 and with 1, giving 2, 6, 4, 1, 9. Each comparison uses the array as it is after the previous swap.
3
The array Ratings[1:5] holds the values 3, 8, 6, 9, 1. One pass of a bubble sort into descending order is made, comparing each pair of adjacent elements from the start of the array.
Give the contents of Ratings after this pass.
8, 6, 9, 3, 1
For descending order a pair is swapped when the first value is smaller. The 3 is smaller than 8, 6 and 9, so it moves along three places; 3 and 1 are already in order. The smallest value ends up at the end - here 1 was already there.
8, 6, 9 in the first three positions, in that order
3, 1 in the last two positions, in that order
The array Points[1:4] holds the values 5, 9, 2, 7.
Pass ← 0
REPEAT
Pass ← Pass + 1
Swap ← FALSE
FOR Index ← 1 TO 3
IF Points[Index] < Points[Index + 1]
THEN
Temp ← Points[Index]
Points[Index] ← Points[Index + 1]
Points[Index + 1] ← Temp
Swap ← TRUE
ENDIF
NEXT Index
UNTIL Swap = FALSEGive the contents of Points when the algorithm ends, the final value of Pass and the total number of swaps made.
Points: 9, 7, 5, 2
Pass = 3
3 swaps
This is a descending sort because it swaps when the first value is smaller. Pass 1 swaps 5 and 9, then 2 and 7 (two swaps, giving 9, 5, 7, 2); pass 2 swaps 5 and 7 (one swap); pass 3 makes no swaps, so the loop ends with Pass equal to 3.
Points: 9, 7, 5, 2
Pass = 3
3 swaps
The one-dimensional array Heights[1:50] holds the heights, in cm, of 50 plants.
Write pseudocode for a bubble sort that sorts Heights into ascending order. Your algorithm must use a flag so that it stops when a pass is made with no swaps.
REPEAT
Swapped ← FALSE
FOR Index ← 1 TO 49
IF Heights[Index] > Heights[Index + 1]
THEN
Temp ← Heights[Index]
Heights[Index] ← Heights[Index + 1]
Heights[Index + 1] ← Temp
Swapped ← TRUE
ENDIF
NEXT Index
UNTIL Swapped = FALSEThe inner loop makes one pass, comparing each element with the next; it stops at 49 because element 49 is compared with element 50. The flag must be reset to FALSE at the start of every pass, inside the REPEAT loop, or the algorithm can never detect a pass with no swaps.
MP1 outer condition-controlled loop (REPEAT ... UNTIL or WHILE) for the passes
max 6
MP2 flag set to FALSE at the start of each pass (inside the outer loop)
MP3 inner loop through the elements from 1 to 49 (or to a decreasing upper limit)
MP4 compares Heights[Index] with Heights[Index + 1] using > (ascending)
MP5 swaps the two elements using a temporary variable (all three assignments correct)
MP6 sets the flag to TRUE when a swap is made
MP7 outer loop ends when a pass has been made with no swaps (flag is FALSE)
MP8 never accesses an element outside 1 to 50 (e.g. no Heights[51])
Ready to try the rest? Every answer you write is marked against the mark scheme, so you can see exactly where the marks are.
Hi! Stuck? Ask me for a hint and I’ll help you work it out. Once you’ve checked your answer I can explain exactly where the marks are.