Bubble Sort

Test yourself on Bubble Sort with exam style questions, marked instantly.

Flashcards that come back just before you would forget them.

A revision plan that remembers what you know and shows what to do next.

See which topics you have nailed and which need another look.

Quiz yourself on Bubble SortGet your flashcardsBuild my revision planTrack my progress

Bubbles Rising to the Top

Bubble sort is named after bubbles rising in water. It compares two neighbouring items, swaps them if they are in the wrong order, and moves along the list. After one full run (a pass), the largest value has "bubbled up" to the end. It keeps making passes until the list is sorted.

Bubble sort flowchart with two loops. Start, input the array, set i to 0. While i is less than n minus 1, set j to 0. While j is less than n minus i minus 1, test whether array[j] is greater than array[j+1]. If yes, swap the two items. Then, whether yes or no, add 1 to j and test again. When the j test fails, add 1 to i and test i again. When the i test fails, output the sorted array and end.

This is the bubble sort flowchart. It uses two loops: i counts the passes and j moves along the list comparing neighbouring items.

Bubble Sort at a Glance

Feature Bubble Sort
Method Compare neighbouring items, swap if in the wrong order, repeat passes
After each pass The largest unsorted value is in its final place at the end
Stops when A full pass makes no swaps
Maximum passes n - 1 passes that make swaps, for a list of n items
Extra memory None: it sorts in place, without a second list
Advantage Simple to understand and to program
Disadvantage Slow on large lists because of the many comparisons and swaps

Deep Dive: Bubble Sort Trace

Sort [4, 2, 3, 1] into ascending order:

Pass 1:

  • Compare 4 and 2: swap, giving [2, 4, 3, 1]
  • Compare 4 and 3: swap, giving [2, 3, 4, 1]
  • Compare 4 and 1: swap, giving [2, 3, 1, 4]. The 4 is now in its final place.

Pass 2:

  • Compare 2 and 3: no swap
  • Compare 3 and 1: swap, giving [2, 1, 3, 4]

Pass 3:

  • Compare 2 and 1: swap, giving [1, 2, 3, 4]

The list is now in order. A further pass would make no swaps, which is how the algorithm knows it can stop.

Deep Dive: Stopping Early

A basic bubble sort always makes n - 1 passes. An improved version uses a swap flag.

  1. Set the flag to False at the start of each pass.
  2. Set the flag to True whenever two items are swapped.
  3. 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.

Memory Trick

Big values bubble up. One pass sends the biggest remaining value to the end, like the biggest bubble reaching the surface first.
No swaps, no more passes. A clean pass means the list is sorted.

Exam Tips

  • Show your working: write the list after every pass, and show each swap if the question asks for it.
  • Do not stop too early: keep going until a full pass makes no swaps.
  • Advantage and disadvantage: simple and needs no extra memory, but slow for large lists.
  • Common mistake: writing only the final sorted list. Method marks are for the passes.

Make this stick

Signing in gives access to all PrepWise features.

PrepWise is a trading name of A3M Quality Solutions Limited, registered in England and Wales, company number 14959172. Registered office: 202 Stroud Road, Gloucester, GL1 5LA. ICO registration ZC267069.