Bubble Sort

TL;DR Bubble Sort repeatedly scans the list, compares adjacent elements, and swaps them when out of order. After each pass, the largest (or smallest) element “bubbles” to its final place.

1. Algorithm Steps

1. Start at the beginning of the array.
2. Compare each pair of adjacent elements.
3. If they’re in the wrong order, swap them.
4. After each full pass, the “heaviest” element sits at the end.
5. Repeat steps 1–4 until no swaps occur.

Early-exit optimization: Keep a swapped flag. If no swaps occur in a pass, the array is sorted, improving best-case time to O(n).

2. Complexity

3. Optimizations & Variants

• Early exit: stops sorting if no swaps occur (best-case O(n)).
• Shrinking bounds: each pass ignores the already sorted elements at the end (n ← n - 1).
• Cocktail Shaker Sort: traverses both directions each round.
• Odd–Even Sort: parallel-friendly, alternating odd-even indexed comparisons.

4. Reference Python Implementation

def bubble_sort(arr):
    def bubbleSort(array): # Write your code here.
    for i in reversed(range(0, len(array))):
        isSorted = True
        for j in range(0, i):
            if array[j] > array[j+1]:
                swap(array, j, j+1)
                isSorted = False
        if isSorted:
            return array
    return array



def swap(array, indexOne, indexTwo):
    temp = array[indexOne]
    array[indexOne] = array[indexTwo]
    array[indexTwo] = temp

5. Practice

Prompt: Write a function that sorts an array of integers using Bubble Sort.

Sample Input: [8, 5, 2, 9, 5, 6, 3]

Expected Output: [2, 3, 5, 5, 6, 8, 9]

Optimal Time & Space Complexity:

• Best: O(n) time, O(1) space
• Average: O(n²) time, O(1) space
• Worst: O(n²) time, O(1) space

6. When (Not) to Use Bubble Sort

• ✅ Good for teaching, debugging, and nearly sorted data (early exit optimization).
• ❌ Not efficient for large datasets; prefer Merge, Quick, or Heap Sort.
• ❌ Cache-unfriendly due to frequent adjacent swaps.

7. Quick Self-Check

1. Why is Bubble Sort considered stable?
2. What is the advantage of the shrinking-bound optimization?
3. Describe the best-case scenario and its complexity.
4. Identify a situation where Bubble Sort outperforms Quick Sort.

8. Further Reading

• Introduction to Algorithms (CLRS), Section 2.1
• Visualgo.net
• CP-Algorithms: Bubble Sort

Happy sorting! May your elements bubble swiftly! 🍵