Bubble Sort (AQA GCSE Computer Science): Revision Notes
Bubble Sort Algorithm
What is bubble sort?
Bubble sort is a simple sorting algorithm that works by examining pairs of adjacent elements in a list. When it finds two elements that are in the wrong order compared to each other, it swaps them around. This process gets repeated for every adjacent pair of values throughout the entire list.
The algorithm gets its name because the largest numbers gradually "bubble" their way to the top of the list, just like air bubbles rising to the surface of water.
How bubble sort works
The bubble sort algorithm is straightforward to understand once you break it down into its core steps. Here's the systematic approach it follows:
The bubble sort process involves repeated passes through the data, with each pass comparing adjacent elements and swapping them when necessary.
- Compare adjacent elements: Start at the beginning of the list and compare the first two elements
- Swap if necessary: If they're in the wrong order, swap them around
- Move to the next pair: Compare the next two adjacent elements
- Repeat through the list: Continue this process until you've checked every adjacent pair
- Multiple passes: After completing one full pass through the list, start again from the beginning
- Stop when no swaps occur: The algorithm only stops when it completes a full pass without making any swaps
Worked example
Let's see how bubble sort works with a practical example using the numbers: 7, 2, 9, 4, 3
Worked Example: Sorting [7, 2, 9, 4, 3] with Bubble Sort
First Pass:
Starting with our original list, we compare the first two elements (7 and 2). Since , they're in the wrong order, so we swap them:
Next, we compare 7 and 9. These are already in the correct order (), so no swap is needed.
Then we compare 9 and 4. Since , they need to be swapped.
Finally, we compare 9 and 3. Since , we swap them too.
Result after first pass: [2, 7, 4, 3, 9]
Continuing the process:
The algorithm continues making passes through the list, comparing and swapping adjacent elements when needed:
- After the second pass: [2, 4, 3, 7, 9]
- After the third pass: [2, 3, 4, 7, 9]
Critical termination rule: Even though the list appears to be sorted after the third pass, the algorithm doesn't know this yet. It must complete one more full pass without making any swaps to confirm the list is properly sorted.
Pseudocode structure
Here's how we can write bubble sort in pseudocode:
REPEAT
REPEAT for each pair in list
IF list[x] > list[x + 1] THEN
swap list[x], list[x + 1]
ENDIF
UNTIL all pairs of values checked
UNTIL no swaps made
The outer loop ensures the algorithm keeps running until no more swaps are needed, while the inner loop handles the comparison of each adjacent pair.
Key characteristics
Understanding these fundamental characteristics will help you grasp why bubble sort works the way it does:
Multiple passes required: Bubble sort typically needs several passes through the data before everything is sorted. Each pass moves at least one element closer to its correct position.
Adjacent comparisons only: The algorithm only ever compares elements that are next to each other in the list - it never compares elements that are far apart.
Guaranteed to terminate: Because each pass either makes progress (by swapping elements) or completes without swaps (meaning we're finished), the algorithm will always eventually stop.
Efficiency consideration: While bubble sort is easy to understand and implement, it's not the most efficient sorting algorithm for large lists of data. It has a time complexity of O(n²) in the worst case.
Exam tips
Essential exam preparation points:
- Remember that bubble sort compares adjacent elements only
- The algorithm stops when it completes a full pass with no swaps
- You don't need to memorise the exact pseudocode, but you should understand how the algorithm works
- Practice tracing through small examples step by step
- The largest elements "bubble up" to their correct positions first
Summary
Key Points to Remember:
- Bubble sort works by comparing adjacent pairs of elements and swapping them if they're in the wrong order
- The algorithm requires multiple passes through the list until no more swaps are needed
- It gets its name because larger values "bubble" to the top of the list
- The termination condition is completing a full pass without making any swaps
- While simple to understand, bubble sort is not the most efficient algorithm for large datasets