Computer ScienceExam code: 0984

Sorting and Searching Algorithms

Algorithm Design and Problem Solving

A walks through a list over and over, comparing each pair of neighbouring values and swapping any pair that is out of order. The list is sorted as soon as a complete pass finishes without making any swaps.

The name comes from the way larger values "bubble" to the end of the list (or smaller values bubble to the beginning, depending on the sort direction).

Step-by-step algorithm

StepWhat it does
1Look at the pair of values sitting at positions 1 and 2
2If that pair is out of order, swap the two values
3Slide one position to the right (positions 2 and 3, then 3 and 4, and so on)
4Keep applying steps 2 and 3 until the last pair has been processed. That whole sweep counts as one pass
5If any swaps were made during the pass, start a new pass from the beginning
6If no swaps were made during a pass, the list is sorted; stop

After each pass, the largest unsorted value is in its correct position at the end of the list. This means you only need to compare up to one fewer position on each subsequent pass, although exam answers usually keep it simple and pass over the whole list each time.

Common exam question

Describing what a bubble sort algorithm does

Question: Given a flowchart or pseudocode that compares neighbouring elements of an array and swaps them, state its purpose, describe what it does, or outline its processes (1–4 marks).

Asked in 3 of the 17 papers. Recognise the sort from its parts: each element compared with the next, a swap through a temporary variable, and repeated passes, ended by a flag showing no swap or fixed in number. For the purpose or description give both ideas: the data in the array is sorted, and the order it is put into (ascending, or alphabetical for names); the two-mark version credits them separately. Swapping when the left value is the greater gives ascending order.

When the processes are asked for, each stage is a point: inputting the values, storing them in an array, sorting them with a bubble sort into ascending order, and outputting them (or finding the middle value, if the algorithm does). Initialisation and iteration are also credited as processes.

Pseudocode

DECLARE Data : ARRAY[1:10] OF INTEGER
DECLARE Swapped : BOOLEAN
DECLARE Count : INTEGER
Count ← 10
Swapped ← TRUE

WHILE Swapped = TRUE DO
   Swapped ← FALSE
   FOR i ← 1 TO Count - 1
      IF Data[i] > Data[i + 1]
        THEN
           // Swap the two values
           Temp ← Data[i]
           Data[i] ← Data[i + 1]
           Data[i + 1] ← Temp
           Swapped ← TRUE
      ENDIF
   NEXT i
ENDWHILE

Common exam question

Completing a trace table for a bubble sort

Question: Complete the trace table for a bubble sort given as a flowchart or pseudocode, using the values stored in the array (5–7 marks).

Set in 2 of the 17 papers. The marks are per column: one each for the flag, the counter and the temporary variable, and two for the array columns (one with a single error); the longer version also marks the input stage and the output separately. Write every value the algorithm assigns, even a repeat: the schemes write the flag and the temporary variable again on each swap. When a pass ends with the flag set, reset it and start the counter from the first pair again. Carry on until a complete pass makes no swap; that final pass must appear in your table even though the list already looks sorted.

In both papers the flowchart adds 1 to the counter before testing it, so write the value that stops each loop as well.

Worked example

Tracing a bubble sort to the pass with no swaps

The array Data[1:4] holds 3, 9, 6, 4. Complete a trace table for this algorithm.

REPEAT
   Swapped ← FALSE
   FOR Count ← 1 TO 3
      IF Data[Count] > Data[Count + 1]
        THEN
          Temp ← Data[Count]
          Data[Count] ← Data[Count + 1]
          Data[Count + 1] ← Temp
          Swapped ← TRUE
      ENDIF
   NEXT Count
UNTIL Swapped = FALSE

Solution:

  • Give the array its starting values in the first row, then add a row for each value of Count, filling in only what that trip round the loop assigns.
  • Each pass begins by setting Swapped to FALSE; a swap writes Temp and the two array elements and sets Swapped to TRUE.
SwappedCountData[1]Data[2]Data[3]Data[4]Temp
3964
FALSE1
TRUE2699
TRUE3499
FALSE1
TRUE2466
3
FALSE1
2
3
  • The third pass makes no swap, so Swapped is still FALSE when UNTIL is reached and the loop ends.
  • Sorted array: 3, 4, 6, 9, after three passes and three swaps.

How the algorithm terminates

The bubble sort stops when a complete pass is made with no swaps. This is detected using a (called Swapped, Swap or Flag in exam algorithms):

  • Set Swapped to FALSE at the start of each pass.
  • Every time a swap is made, set Swapped to TRUE.
  • At the end of each pass, check Swapped. If it is FALSE, the list is sorted; if it is TRUE, do another pass.

Without this flag, a naive bubble sort would always run the same number of passes, even on an already-sorted list. The flag lets the algorithm stop as soon as the list is in order.

Exam tip

Explaining why a bubble sort is efficient

Asked why a bubble sort with these features is efficient (three marks), give the mechanisms: one mark per point, feature and effect counted separately. The flag is set to FALSE at the start of a pass and to TRUE when a swap is made, so a pass ending with it still FALSE shows the list is sorted and the loop stops. The inner loop's upper limit is reduced by one after each pass, because the largest value is already in place, so later passes make fewer comparisons. Saying only that it stops when sorted is one point of the three.

Advantages and disadvantages

AdvantagesDisadvantages
Very simple to understand and codeSlow on large lists: up to n × n comparisons
Easy to spot when the list is sorted (no swaps in the pass)Many swaps mean a lot of data movement
Sorts the list in place: needs no extra memory beyond a temporary variableBetter-performing algorithms exist (quicksort, mergesort), but they are beyond this level

Performance

For a list of n items:

  • Best case (list already sorted): one pass, n − 1 comparisons, zero swaps.
  • Worst case (list sorted in reverse): n passes of n − 1 comparisons (roughly n × n), with a swap on about half of them.

Bubble sort is fine for short lists or educational examples, but not for serious sorting work.

Bubble sort tracing the list 9, 2, 4, 7, 10, 3, 1: pass 1 compares each neighbouring pair left to right and swaps any out of order so 10 bubbles to the end, then pass 2 begins from the start comparing pairs again
Source: Bubble Sort in Computer Science by Save My Exams

Quick check

5 short questions on this note. See what has stuck, and where to look if something hasn't.

About 2 minutes

Build on this topic