Sorting algorithms are a fundamental concept in computer science, widely taught in schools and used in software development. Among the simplest and most intuitive of these is the Bubble Sort algorithm. Understanding Bubble Sort not only helps in learning basic algorithm design but also builds a strong foundation for more advanced sorting methods.
In this article, we will explore the pseudocode for Bubble Sort, explain how it works, and offer examples to help you master it.
What is Bubble Sort?
Bubble Sort is a simple comparison-based algorithm that repeatedly steps through a list, compares adjacent elements, and swaps them if they are in the wrong order. This process is repeated until the list becomes sorted. It is called “Bubble” Sort because smaller elements “bubble” to the top of the list through successive swaps.
Although Bubble Sort is not efficient for large datasets compared to other algorithms like Quick Sort or Merge Sort, it is an excellent starting point for beginners learning about sorting and algorithm analysis.
Bubble Sort Pseudocode
Here is a clear and easy-to-follow pseudocode for Bubble Sort:
1 2 3 4 5 6 7 8 9 10 11 12 13 | 1. Start 2. Input the list of numbers to be sorted 3. Set a variable swapped to True 4. While swapped is True, do: a. Set swapped to False b. For each index i from 0 to length of list - 2, do: i. If list[i] > list[i + 1], then: - Swap list[i] and list[i + 1] - Set swapped to True 5. Output the sorted list 6. End |
Explanation of the Pseudocode
- Initialization: We start by assuming that the list needs sorting (
swapped = True). - Outer Loop: The algorithm keeps checking and swapping elements until no more swaps are needed.
- Inner Loop: It goes through the list, comparing adjacent elements.
- Swapping: If two elements are in the wrong order (first is bigger than the second), they are swapped.
- Early Termination: If no elements were swapped during a pass, the list is sorted, and the algorithm stops early.
Example Walkthrough
Let’s see Bubble Sort in action with a simple list: [5, 3, 8, 4, 2].
- First Pass:
- Compare 5 and 3 → Swap →
[3, 5, 8, 4, 2] - Compare 5 and 8 → No swap
- Compare 8 and 4 → Swap →
[3, 5, 4, 8, 2] - Compare 8 and 2 → Swap →
[3, 5, 4, 2, 8]
- Compare 5 and 3 → Swap →
- Second Pass:
- Compare 3 and 5 → No swap
- Compare 5 and 4 → Swap →
[3, 4, 5, 2, 8] - Compare 5 and 2 → Swap →
[3, 4, 2, 5, 8]
- Third Pass:
- Compare 3 and 4 → No swap
- Compare 4 and 2 → Swap →
[3, 2, 4, 5, 8]
- Fourth Pass:
- Compare 3 and 2 → Swap →
[2, 3, 4, 5, 8]
- Compare 3 and 2 → Swap →
At this point, no further swaps are needed, and the list is sorted.
Time Complexity of Bubble Sort
| Case | Time Complexity |
|---|---|
| Best Case | O(n) |
| Average Case | O(n²) |
| Worst Case | O(n²) |
- Best case happens when the list is already sorted.
- Worst and average cases occur when the list is sorted in reverse order or random order.
Conclusion
Bubble Sort is an excellent algorithm for beginners who want to understand the mechanics of sorting. While not efficient for large datasets, its simplicity makes it a favorite teaching tool. Learning Bubble Sort helps students grasp core programming concepts like loops, conditionals, and swapping values.
If you’re starting with pseudocode or basic algorithms, mastering Bubble Sort is a must!
