A basic bubble sort always makes n - 1 passes. An improved version uses a swap flag.
- Set the flag to False at the start of each pass.
- Set the flag to True whenever two items are swapped.
- At the end of the pass, if the flag is still False, nothing moved, so the list is sorted and the sort stops.
This saves time on lists that are already sorted or nearly sorted. For [1, 2, 3, 5, 4], one pass swaps 5 and 4, and the next pass makes no swaps, so the sort stops after two passes.
A first pass on a list of 5 items makes 4 comparisons, because each pair of neighbours is compared once.
This study notes covers Deep Dive: Stopping Early within Bubble Sort for GCSE Computer Science. Revise Bubble Sort in 3.1 Fundamentals of Algorithms for GCSE Computer Science with 16 exam-style questions and 10 flashcards. This topic appears regularly enough that it should still be part of a steady revision cycle. It is section 4 of 7 in this topic. Use this study notes to connect the idea to the wider topic before moving on to questions and flashcards.
Practice questions for Bubble Sort
Which of the following best describes bubble sort?
Describe how bubble sort works. You should refer to what happens during each pass through the list. [3 marks]