Understanding the Basics

Bubble Sort is one of the simplest sorting algorithms. It repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. This process continues until the list is sorted.

Swapping Condition

The fundamental operation of Bubble Sort is swapping elements if they are out of order.

if (arr[j] > arr[j+1])

This ensures that larger elements "bubble up" towards the right, just like bubbles rising to the surface of water.

Swapping Function

To facilitate swapping, we use a helper function:

void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

Basic Bubble Sort Implementation

Here's how a basic Bubble Sort works:

void bubbleSort(vector<int>& arr) {
    int n = arr.size();
    for (int i = 0; i < n; i++) {  // Loop for passes
        for (int j = 0; j < n - 1; j++) {  // Compare adjacent elements
            if (arr[j] > arr[j + 1]) {  // Swap if needed
                swap(&arr[j], &arr[j + 1]);
            }
        }
    }
}

Time Complexity:

Worst-case: O(n²) (when the array is in reverse order)
Best-case: O(n²)

Optimized Bubble Sort (With Early Stopping Condition)

An optimized version of Bubble Sort introduces a swapped flag to stop the algorithm if no swaps occur in a pass. If a pass completes without any swaps, the array is already sorted, preventing unnecessary iterations.

void bubbleSort(vector<int>& arr) {
    int n = arr.size();
    bool swapped;

    for (int i = 0; i < n - 1; i++) {  // Run n-1 passes
        swapped = false;
        for (int j = 0; j < n - i - 1; j++) {  // Compare adjacent elements
            if (arr[j] > arr[j + 1]) {  // Swap if needed
                swap(&arr[j], &arr[j + 1]);
                swapped = true;
            }
        }
        if (!swapped)  // If no swap happens, the array is sorted
            break;
    }
}

Optimized Complexity:

Worst-case: O(n²)
Best-case: O(n) (when the array is already sorted)

Why Use Bubble Sort?

✅ Easy to implement
✅ Good for small datasets
✅ Teaches fundamental sorting concepts

When Not to Use Bubble Sort?

❌ Inefficient for large datasets
❌ Better alternatives exist (Merge Sort, Quick Sort, etc.)

Final Thoughts

While Bubble Sort is not the most efficient sorting algorithm, it is great for learning the basics of sorting logic. Understanding its swapping mechanism and optimization techniques can help in mastering more advanced sorting algorithms.

Bubble Sort Algorithm