Bubble Sort
Learn how the Bubble Sort algorithm organizes data by swapping adjacent elements.
Warm Up
Imagine that you want to sort these 7 cards into ascending order (Lowest to Highest). Click a card then click another to swap them.
Click two cards to swap their positions.
What is Bubble Sort?
The bubble sort algorithm works by repeatedly going through a list of items, comparing consecutive pairs of items and swapping the items if they are in the wrong order.
The algorithm is called bubble sort because when sorting a list from lowest to highest value, the highest values are moved up the list, which some people imagine as bubbles in a fizzy drink rising to the top.
- Pass: Each time the algorithm goes through the list completely.
- Comparison: Each time a pair of items are checked to see if they are in the correct order.
Visualising the Process
First Pass
The algorithm compares start to end. The highest value (10) bubbles to the top.
At the end of this pass, the highest value (10) will be green.
Using this method, if there are N items in the list, then a maximum of N-1 passes will be performed. Optimised versions of the algorithm stop early if no swaps are made in a pass.
Numerical Example: Olympic Medals
Let's sort the medal counts: [15, 25, 13, 29, 18].
1. Sorting Numbers
Try it yourself!
How many comparisons will bubble sort perform with the following list during the first pass?
List Length = 7
Sorting Words
Bubble sort can also sort words strictly alphabetically (A-Z).
2. Sorting Schools
Try it yourself!
Consider this list of Swindon schools: ["Dorcan", "Highworth", "St Joseph's", "Kingsdown"].
How many swaps and how many comparisons will be made during the first pass?
Algorithm Implementation
Below is the standard version of Bubble Sort. Use the trace table to step through the algorithm.
def bubble_sort(items):
num_items = len(items)
# Outer loop for number of passes
for pass_num in range(num_items - 1):
# Inner loop for comparisons
for index in range(num_items - 1):
if items[index] > items[index + 1]:
# Swap elements
temp = items[index]
items[index] = items[index + 1]
items[index + 1] = temp
return items# This basic version is easy to code but not very efficient because it keeps checking even if the list is already sorted.
Efficiency Scenarios
Bubble sort performance varies greatly depending on the initial order.
Best Case
Already sorted. 1 Pass. 0 Swaps.
Worst Case
Reverse order. Max Passes & Swaps.
Fill the Gaps
Order the Steps
Arrange the steps of the Bubble Sort algorithm.
Available Steps:
Your sequence:
Click items above to build your sequence
Keywords Memory Game
A-Level Only: Efficiency of Bubble Sort
Let's analyse the Time and Space complexity of Bubble Sort using Big O notation. The graph below compares the operations needed for Best Case (Linear O(n)) and Worst/Average Case (Polynomial O(n²)), alongside the Space Complexity (Constant O(1)).