Bubble Sort Algorithm

What is Bubble Sort?

Bubble Sort is one of the simplest and most well-known comparison-based sorting algorithms. It repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. This process is repeated until the array is fully sorted.

Although it is not efficient for large datasets due to its quadratic time complexity, Bubble Sort is excellent for teaching the core principles of sorting algorithms — such as iteration, comparison, and swapping.

How Bubble Sort Works

1. Start at the beginning of the array.
2. Compare the current element with the next element.
3. If the current element is greater, swap them.
4. Repeat this for each pair in the array.
5. With each pass, the largest unsorted value “bubbles” to its correct position at the end.
6. Continue passes until no swaps are needed (i.e., the array is sorted).

Time and Space Complexity

• Space Complexity: O(1) – Bubble Sort is an in-place sorting algorithm.
• Stable: ✅ Yes (maintains relative order of equal elements)

When to Use Bubble Sort

• When learning basic sorting concepts.
• For small datasets.
• When stability is required and performance is not critical.

Bubble Sort – C++ Code Example

#include <iostream>
using namespace std;

void bubbleSort(int arr[], int n) {
    bool swapped;

    for (int i = 0; i < n - 1; i++) {
        swapped = false;

        // Compare adjacent elements
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                // Swap them
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;

                swapped = true;
            }
        }

        // Print array after each pass
        cout << "After pass " << i + 1 << ": ";
        for (int k = 0; k < n; k++) {
            cout << arr[k] << " ";
        }
        cout << endl;

        // If no swaps were made, the array is already sorted
        if (!swapped) break;
    }
}

void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);

    cout << "Original array:\n";
    printArray(arr, n);

    bubbleSort(arr, n);

    cout << "\nSorted array:\n";
    printArray(arr, n);

    return 0;
}

Output

Original array:
64 34 25 12 22 11 90 
After pass 1: 34 25 12 22 11 64 90 
After pass 2: 25 12 22 11 34 64 90 
After pass 3: 12 22 11 25 34 64 90 
After pass 4: 12 11 22 25 34 64 90 
After pass 5: 11 12 22 25 34 64 90 
After pass 6: 11 12 22 25 34 64 90 

Sorted array:
11 12 22 25 34 64 90 

Bubble Sort – Visual Explanation (Step-by-Step)

Let’s sort:

[64, 34, 25, 12, 22, 11, 90]

Pass 1:

• Compare 64 and 34 → swap → [34, 64, 25, 12, 22, 11, 90]
• Compare 64 and 25 → swap → [34, 25, 64, 12, 22, 11, 90]
• Compare 64 and 12 → swap
• Compare 64 and 22 → swap
• Compare 64 and 11 → swap
• Compare 64 and 90 → OK

➡ Largest element (90) has bubbled to the end.

Pass 2:

Now ignore the last element (already sorted):

[34, 25, 12, 22, 11, 64, 90]
→ Result after swaps: [25, 12, 22, 11, 34, 64, 90]

Pass 3:

[25, 12, 22, 11, 34, 64, 90]
→ Result: [12, 22, 11, 25, 34, 64, 90]

Pass 4:

[12, 22, 11, 25, 34, 64, 90]
→ Result: [12, 11, 22, 25, 34, 64, 90]

Pass 5:

[12, 11, 22, 25, 34, 64, 90]
→ Result: [11, 12, 22, 25, 34, 64, 90]

Pass 6:

Already sorted → no swaps → exit early.

Final Sorted Array:

[11, 12, 22, 25, 34, 64, 90]

Summary

• Bubble Sort is great for educational purposes and small datasets.
• It is simple, easy to implement, and stable.
• The algorithm performs best when the input is already nearly sorted.