Studyledge

Algorithm Design and Standard Methods: Question 4

Syllabus 7.3, 7.4

Structured 11 marks

A go-kart track records the finishing times, in seconds, of the 5 karts in one heat, stored in a one-dimensional (1D) array called RaceTimes, in the order the karts crossed the start line:

RaceTimes: 52.3, 48.7, 55.1, 50.4, 47.6

The track marshal wants RaceTimes sorted into ascending order (fastest time first) so that trophies can be awarded correctly.

(a) Write an algorithm, in pseudocode, that uses a bubble sort to sort RaceTimes into ascending order. Your algorithm must use a Boolean variable, Swapped, so that it stops repeating passes as soon as a complete pass makes no swaps. [5]

(b) Trace your algorithm for the data given, showing the contents of RaceTimes after each pass, until the array is fully sorted into ascending order. [4]

(c) Explain how including the variable Swapped in your algorithm in (a) makes it more efficient than a bubble sort that always repeats a fixed number of passes. [2]

Show worked solution Hide worked solution

Worked solution

Part (a): Writing the bubble sort with a swap flag

Adjacent elements are compared and swapped if they are in the wrong order, repeating full passes until one pass makes no swaps at all:

DECLARE RaceTimes : ARRAY[1:5] OF REAL
DECLARE Index : INTEGER
DECLARE Temp : REAL
DECLARE Swapped : BOOLEAN

Swapped ← TRUE
WHILE Swapped = TRUE
    Swapped ← FALSE
    FOR Index ← 1 TO 4
        IF RaceTimes[Index] > RaceTimes[Index + 1] THEN
            Temp ← RaceTimes[Index]
            RaceTimes[Index] ← RaceTimes[Index + 1]
            RaceTimes[Index + 1] ← Temp
            Swapped ← TRUE
        ENDIF
    NEXT Index
ENDWHILE

Mark-earning features: [1] Swapped initialised to TRUE so the outer loop runs at least once; [1] Swapped reset to FALSE at the start of every pass; [1] the inner FOR loop correctly bounded 1 TO 4 (one less than the 5 elements, comparing each element with its neighbour); [1] a correct three-line swap using Temp when RaceTimes[Index] > RaceTimes[Index + 1]; [1] Swapped ← TRUE set inside the IF, so the outer loop only ends once a whole pass completes with no swaps.

Part (b): Tracing the algorithm

Starting array: 52.3, 48.7, 55.1, 50.4, 47.6

Pass 1 (Swapped ← FALSE at start):

  • Index 1: 52.3 > 48.7, swap → 48.7, 52.3, 55.1, 50.4, 47.6
  • Index 2: 52.3 > 55.1 is false, no swap
  • Index 3: 55.1 > 50.4, swap → 48.7, 52.3, 50.4, 55.1, 47.6
  • Index 4: 55.1 > 47.6, swap → 48.7, 52.3, 50.4, 47.6, 55.1

After pass 1: 48.7, 52.3, 50.4, 47.6, 55.1 (Swapped = TRUE)

Pass 2:

  • Index 1: 48.7 > 52.3 false
  • Index 2: 52.3 > 50.4, swap → 48.7, 50.4, 52.3, 47.6, 55.1
  • Index 3: 52.3 > 47.6, swap → 48.7, 50.4, 47.6, 52.3, 55.1
  • Index 4: 52.3 > 55.1 false

After pass 2: 48.7, 50.4, 47.6, 52.3, 55.1 (Swapped = TRUE)

Pass 3:

  • Index 1: 48.7 > 50.4 false
  • Index 2: 50.4 > 47.6, swap → 48.7, 47.6, 50.4, 52.3, 55.1
  • Index 3: 50.4 > 52.3 false
  • Index 4: 52.3 > 55.1 false

After pass 3: 48.7, 47.6, 50.4, 52.3, 55.1 (Swapped = TRUE)

Pass 4:

  • Index 1: 48.7 > 47.6, swap → 47.6, 48.7, 50.4, 52.3, 55.1
  • Index 2, 3, 4: all comparisons false

After pass 4: 47.6, 48.7, 50.4, 52.3, 55.1 (Swapped = TRUE, one swap occurred)

Pass 5: every comparison is now false (47.6 < 48.7 < 50.4 < 52.3 < 55.1), so no swaps occur and Swapped stays FALSE. The WHILE Swapped = TRUE condition fails and the algorithm stops.

The array is fully sorted into ascending order: 47.6, 48.7, 50.4, 52.3, 55.1.

Part (c): Why the swap flag improves efficiency

Without Swapped, a bubble sort must be written to always repeat the maximum number of passes needed to guarantee any possible arrangement of 5 elements is sorted (4 passes), even on data that becomes sorted earlier, comparing elements that are already in the correct order for no reason. [1]

With Swapped, the algorithm can detect the moment a complete pass makes no swaps at all, which, as traced above, happens on pass 5, and stop immediately rather than continuing to run passes on data that is already sorted. This saves unnecessary comparisons whenever the data is partially ordered to begin with, or becomes ordered before the maximum number of passes has been reached. [1]

Final answers

  • (a) See the pseudocode algorithm above.
  • (b) Sorted array after pass 4: 47.6, 48.7, 50.4, 52.3, 55.1; pass 5 confirms no more swaps are needed.
  • (c) Swapped allows the algorithm to stop as soon as one pass makes no swaps, avoiding unnecessary passes over already-sorted data.