bubble_sort.cpp

// bubble_sort.cpp
// -----------------------------------------------------------------
// Bubble Sort（泡沫排序）
//
// 原理：反覆走訪陣列，比較相鄰兩元素，順序錯誤就交換。
//       每一輪會把「目前最大」的元素像泡泡一樣浮到最右端。
//       若某一輪完全沒有交換，代表已排好，可提早結束。
//
// 時間複雜度：最好 O(n)（已排序 + 提早結束優化）
//             平均 / 最壞 O(n^2)
// 空間複雜度：O(1)（原地排序）
// 穩定性：穩定（相等元素不交換，相對次序不變）
//
// Compile: g++ -std=c++17 -O2 -Wall -o bubble_sort bubble_sort.cpp
// -----------------------------------------------------------------
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void bubbleSort(vector<int>& a) {
    int n = (int)a.size();
    for (int i = 0; i < n - 1; ++i) {
        bool swapped = false;
        // 每輪結尾的 i 個元素已就定位，不必再比
        for (int j = 0; j + 1 < n - i; ++j) {
            if (a[j] > a[j + 1]) {
                swap(a[j], a[j + 1]);
                swapped = true;
            }
        }
        if (!swapped) break;   // 提早結束：本輪無交換代表已排序
    }
}

static void printVec(const string& tag, const vector<int>& a) {
    cout << tag;
    for (int x : a) cout << x << " ";
    cout << "\n";
}

int main() {
    vector<vector<int>> tests = {
        {5, 2, 9, 1, 5, 6},
        {3, 1, 2},
        {1, 2, 3, 4, 5},          // 已排序（提早結束）
        {5, 4, 3, 2, 1},          // 反向
        {42},                     // 單一元素
        {},                       // 空陣列
        {7, 7, 7, 7},             // 全部相等
    };
    for (auto& t : tests) {
        printVec("before: ", t);
        bubbleSort(t);
        printVec("after : ", t);
        cout << "sorted : " << boolalpha
             << is_sorted(t.begin(), t.end()) << "\n\n";
    }
    return 0;
}