Hello everyone! Today, we will learn a simple yet classic sorting algorithm—Bubble Sort—and implement it in C++. The name “Bubble Sort” is quite interesting; its core idea is similar to how bubbles rise in water: smaller elements gradually “bubble up” to the top of the array, ultimately making the entire array sorted.

1. Basic Idea of Bubble Sort¶

The core of Bubble Sort is to repeatedly compare adjacent elements and swap them if they are in the wrong order. Specifically:
- Start from the first element of the array and compare adjacent elements one by one.
- If the previous element is larger than the next, swap them.
- After one round of comparisons, the largest element will “bubble up” to the end of the array.
- Repeat this process, with each round determining the final position of one largest element, until the entire array is sorted.

2. Understanding the Process with an Example¶

Suppose we have the array: [5, 2, 9, 1, 5, 6]. Let’s sort it using Bubble Sort.

First Round (Determine the position of the largest element, 9):¶

• Compare 5 and 2: 5 > 2, swap → [2, 5, 9, 1, 5, 6]
• Compare 5 and 9: 5 < 9, no swap
• Compare 9 and 1: 9 > 1, swap → [2, 5, 1, 9, 5, 6]
• Compare 9 and 5: 9 > 5, swap → [2, 5, 1, 5, 9, 6]
• Compare 9 and 6: 9 > 6, swap → [2, 5, 1, 5, 6, 9]
  At this point, the largest element (9) has bubbled to the end; no further comparisons are needed for it.

Second Round (Determine the position of the second largest element, 6):¶

• Compare 2 and 5: 2 < 5, no swap
• Compare 5 and 1: 5 > 1, swap → [2, 1, 5, 5, 6, 9]
• Compare 5 and 5: equal, no swap
• Compare 5 and 6: 5 < 6, no swap
  The second largest element (6) is now in its final position.

Subsequent rounds follow similarly until the entire array is sorted.

3. C++ Code Implementation¶

Here’s the C++ implementation of Bubble Sort with detailed comments:

#include <iostream>
using namespace std;

// Bubble Sort function: takes an array and its length
void bubbleSort(int arr[], int n) {
    // Outer loop: controls the number of rounds (n-1 rounds for n elements)
    for (int i = 0; i < n - 1; ++i) {
        bool swapped = false; // Flag to check if any swaps occurred in this round
        // Inner loop: compare adjacent elements, excluding the already sorted part
        for (int j = 0; j < n - i - 1; ++j) {
            // Swap if the current element is larger than the next
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];       // Temporary variable for swapping
                arr[j] = arr[j + 1];     // Move next element to current position
                arr[j + 1] = temp;       // Move current element to next position
                swapped = true;          // Mark that a swap occurred
            }
        }
        // Optimization: If no swaps in this round, the array is already sorted
        if (!swapped) {
            break;
        }
    }
}

// Main function: test Bubble Sort
int main() {
    int arr[] = {5, 2, 9, 1, 5, 6}; // Array to be sorted
    int n = sizeof(arr) / sizeof(arr[0]); // Calculate array length

    cout << "Array before sorting: ";
    for (int i = 0; i < n; ++i) {
        cout << arr[i] << " ";
    }
    cout << endl;

    bubbleSort(arr, n); // Call Bubble Sort

    cout << "Array after sorting: ";
    for (int i = 0; i < n; ++i) {
        cout << arr[i] << " ";
    }
    cout << endl;

    return 0;
}

4. Code Explanation¶

1. Outer Loop: for (int i = 0; i < n - 1; ++i)
   Controls the number of rounds. For an array of length n, at most n-1 rounds are needed (each round fixes the position of one largest element).

2. Inner Loop: for (int j = 0; j < n - i - 1; ++j)
   Controls comparisons per round. After each round, the largest element is already sorted at the end, so we reduce the comparison range by i elements.

3. Swap Logic: int temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp;
   Uses a temporary variable to swap adjacent elements to avoid data loss during swapping.

4. Optimization: bool swapped = false
   If no swaps occur in a round, the array is already sorted, and we exit early to avoid unnecessary comparisons, improving efficiency.

5. Output Result¶

When the code runs, the output is:

Array before sorting: 5 2 9 1 5 6 
Array after sorting: 1 2 5 5 6 9 

6. Complexity Analysis¶

• Time Complexity:
• Worst Case (completely reversed): O(n²) (requires all n-1 rounds, each with n-i comparisons).
• Best Case (already sorted): O(n) (optimized to 1 round with no swaps).

• Average Case: O(n²).

• Space Complexity: O(1) (uses only a few temporary variables, sorts in-place).

• Stability: Stable (equal elements are not swapped).

7. Summary¶

Bubble Sort is an ideal starting point for learning sorting algorithms. Its core idea is simple and intuitive, making it easy to understand. Although less efficient than advanced algorithms like Quick Sort or Merge Sort, it helps master the basic “compare-and-swap” sorting logic. Try modifying the array elements to test different scenarios and observe how Bubble Sort behaves!