Bubble Sort
Computer Science: OCR GCSE, topic 2.1.13
Bubble Sort
Bubble sort is a naive sorting algorithm.
The concept
- Imagine that you have a set of cards face up on the desk.
- If the first two cards are in the wrong order, you swap them.
- Then do the same for the second and third cards, and continue in this pattern until the end of the pack. This is known as a pass.
- The highest value will 'bubble' up to the top of the pack each pass.
- By repeating this enough times, the pack will get sorted.
In English
- Compare the first two items of the dataset:
- Swap these items if they aren't in the right order.
- Continue for the rest of the cards in the deck.
- Repeat the whole process, until a pass with no swaps happens.
In pseudocode
Example
- We will sort this list in ascending order:
- [7, 3, 9, 2, 5]
- A bubble sort pass compares each pair of adjacent items and swaps them if they are in the wrong order.
- Step 1
- Compare 7 and 3
- 7 > 3 → swap
- [3, 7, 9, 2, 5]
- Step 2
- Compare 7 and 9
- 7 < 9 → no swap
- [3, 7, 9, 2, 5]
- Step 3
- Compare 9 and 2
- 9 > 2 → swap
- [3, 7, 2, 9, 5]
- Step 4
- Compare 9 and 5
- 9 > 5 → swap
- [3, 7, 2, 5, 9]
- At the end of the first pass, the largest value (9) has “bubbled up” to the final position. Bubble sort always places the highest unsorted value at the end after each pass.
Pros and cons of bubble sort
- Pros:
- More memory efficient than the merge sort, as it does not need to use an extra space during the algorithm. All swaps happen 'in place'.
- The algorithm is easy to implement
- Cons:
- Often slower than the insertion sort on a dataset of the same size. On average, more comparisons are required.
Test yourself on Bubble Sort
What is the main disadvantage of bubble sort?
Bubble Sort in English