Bubble Sort: A Step-by-Step Guide
- Iterate through the array multiple times.
- Compare each pair of adjacent elements.
- Swap them if they are in the wrong order.
- Repeat until the array is sorted.
Note
Bubble sort is called "bubble" sort because smaller elements "bubble" to the top of the array with each pass.
Time and Space Complexity of Bubble Sort
- Time Complexity:
- Worst Case: $O(n^2)$ (when the array is in reverse order)
- Best Case: $O(n)$ (when the array is already sorted, with an optimized version that checks for swaps)
- Average Case: $O(n^2)$
- Space Complexity: $O(1)$ (in-place sorting)
Tip
- When analyzing an algorithm's time complexity, always consider the worst-case scenario first.
- Then evaluate average-case performance, which often provides a more realistic assessment of practical efficiency.
Advantages and Disadvantages of Bubble Sort
- Advantages:
- Simple to implement
- No additional memory required
- Disadvantages:
- Inefficient for large datasets
- High number of swaps
Common Mistake
- Assuming bubble sort is efficient for all datasets.
- It is only suitable for small or nearly sorted arrays.
Selection Sort: A Step-by-Step Guide
- Iterate through the array.
- Find the smallest element in the unsorted portion.
- Swap it with the first unsorted element.
- Repeat until the array is sorted.
Note
Selection sort minimizes the number of swaps compared to bubble sort, but it still has a high time complexity.
Time and Space Complexity of Selection Sort
- Time Complexity:
- Worst Case: $O(n^2)$
- Best Case: $O(n^2)$
- Average Case: $O(n^2)$
- Space Complexity: $O(1)$ (in-place sorting)
Note
Selection sort's time complexity is $O(n^2)$ in all cases because it always scans the entire unsorted portion of the array.
Advantages and Disadvantages of Selection Sort
- Advantages:
- Simple to implement
- Fewer swaps compared to bubble sort
- Disadvantages:
- Inefficient for large datasets
- Still has a high time complexity
Note
While both bubble sort and selection sort have the same time complexity, selection sort often performs better in practice due to fewer swaps.
Comparing Bubble Sort and Selection Sort
| Criterion | Bubble sort | Selection sort |
|---|---|---|
| Time complexity | O(n^2) worst/average, O(n) best (already sorted with early stopping) | O(n^2) in all cases (always compares all pairs) |
| Space complexity | O(1) (in-place sorting) | O(1) (in-place sorting) |
| Swaps | High (swaps occur frequently during passes) | Low (only one swap per pass) |
| Best use case | Small or nearly sorted datasets (early exit helps) | Small datasets where swap cost is expensive |
| Stability | Stable (preserves order of equal elements) | Not stable (may change order of equal elements) |
| Practical use | Rare in real-world (educational use, tracing in exams) | Rare in real-world (educational use, algorithm analysis) |
Self review
- Can you trace the execution of bubble sort and selection sort on a small array?
- How do the time and space complexities of these algorithms compare?
- What are the advantages and disadvantages of each algorithm?
