What is Bubble Sort?

What is Bubble Sort?

Bubble Sort is a sorting algorithm that repeatedly compares adjacent elements in a list and swaps them if they are in the wrong order. The name comes from the way larger elements "bubble" to the top (end of the list) with each pass.

---

How Does Bubble Sort Work?

1. Start with the first two elements of the list.
2. Compare the two elements:
   • If the first element is greater than the second, swap them.
   • Otherwise, move to the next pair.
3. Repeat this process for every pair in the list. By the end of one pass, the largest element is at the correct position (end of the list).
4. Repeat the process for the remaining unsorted portion of the list (ignoring the last element, which is already sorted).
5. Continue until the list is fully sorted.

---

Example Walkthrough

Let’s sort the list [5, 3, 8, 4, 2] using Bubble Sort.

Step 1: First Pass

• Compare 5 and 3 → Swap → [3, 5, 8, 4, 2]
• Compare 5 and 8 → No Swap → [3, 5, 8, 4, 2]
• Compare 8 and 4 → Swap → [3, 5, 4, 8, 2]
• Compare 8 and 2 → Swap → [3, 5, 4, 2, 8]

After the first pass, the largest element (8) is in its correct position.

Step 2: Second Pass

• Compare 3 and 5 → No Swap → [3, 5, 4, 2, 8]
• Compare 5 and 4 → Swap → [3, 4, 5, 2, 8]
• Compare 5 and 2 → Swap → [3, 4, 2, 5, 8]

After the second pass, the second largest element (5) is in its correct position.

Step 3: Third Pass

• Compare 3 and 4 → No Swap → [3, 4, 2, 5, 8]
• Compare 4 and 2 → Swap → [3, 2, 4, 5, 8]

After the third pass, the third largest element (4) is in its correct position.

Step 4: Fourth Pass

• Compare 3 and 2 → Swap → [2, 3, 4, 5, 8]

Now the list is fully sorted.

---

Key Properties of Bubble Sort

1. Number of Passes: Each pass moves the largest unsorted element to its correct position. It can take up to ( n-1 ) passes for a list of size ( n ).
2. Stability: Bubble Sort is a stable algorithm, meaning it preserves the relative order of elements with equal values.
3. In-Place Sorting: It doesn’t require extra memory to sort; the swaps happen within the same array.

---

Advantages

• Simple to understand and implement.
• Works well for small datasets or nearly sorted data.

---

Disadvantages

• Inefficient for large datasets due to its ( O(n^2) ) time complexity in the average and worst cases.
• Requires multiple passes even if the list becomes sorted early (unless optimized).

---

Optimizing Bubble Sort

You can optimize Bubble Sort by adding a flag to check if any swaps were made during a pass. If no swaps occur, the list is already sorted, and you can stop early.

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        swapped = False
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
                swapped = True
        if not swapped:
            break  # Exit early if no swaps occurred

---

Visualizing Bubble Sort

1. Imagine sorting like bubbling air in water.
2. Larger elements move up (to the end) as smaller elements sink down (toward the start) after each pass.

The time complexity of Bubble Sort is measured by analyzing the number of comparisons and swaps performed in the worst, best, and average cases. Let's break it down:

---

List: [5, 3, 8, 4, 2]

• Size of the List (n): 5

Step-by-Step Time Complexity Measurement

Bubble Sort involves two nested loops:

1. Outer Loop: Runs ( n-1 ) times (for each pass).
2. Inner Loop: Compares adjacent elements in the unsorted part of the list.

1. Total Comparisons (Worst Case)

In the worst case (reverse-sorted list), Bubble Sort makes the maximum number of comparisons.

• Pass 1: ( n-1 = 4 ) comparisons.
• Pass 2: ( n-2 = 3 ) comparisons.
• Pass 3: ( n-3 = 2 ) comparisons.
• Pass 4: ( n-4 = 1 ) comparison.

---

2. Best Case

In the best case (already sorted list), Bubble Sort can terminate early if no swaps occur during a pass.

• The algorithm performs ( n-1 ) comparisons in the first pass and terminates early.
• Total comparisons: ( n-1 = 4 ) for ( n = 5 ).
• Time Complexity in Big O: ( O(n) ).

---

3. Average Case

For a random input list, the number of comparisons is similar to the worst case because the algorithm doesn't know if the list is sorted early.

• Total comparisons: ( \frac{n(n-1)}{2} ), same as the worst case.
• Time Complexity in Big O: ( O(n^2) ).

---

Time Complexity Summary

---

How to Measure Time Complexity

1. Count Comparisons: Focus on the number of element comparisons (inner loop iterations).
2. Count Swaps: Swaps occur only when elements are out of order.
3. Consider Input Size: Analyze how the algorithm behaves as ( n ) (input size) grows.

For Bubble Sort, the time complexity is dominated by the number of comparisons, leading to a quadratic growth in the worst and average cases.

Let me know if you want further clarification or a real-world analogy!