comb_sort.cpp

// comb_sort.cpp
// -----------------------------------------------------------------
// Comb Sort（梳排序）
//
// 原理：泡沫排序的改良。比較「間距 gap」的元素而非相鄰元素，
//       gap 每輪除以縮減係數 1.3，最後 gap=1 收尾。
//       大間距能快速消除「小值在尾端」的烏龜元素（turtles）。
//
// 時間複雜度：平均約 O(n^2 / 2^p)，實務接近 O(n log n)；最壞 O(n^2)
// 空間複雜度：O(1)
// 穩定性：不穩定
//
// Compile: g++ -std=c++17 -O2 -Wall -o comb_sort comb_sort.cpp
// -----------------------------------------------------------------
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void combSort(vector<int>& a) {
    int n = (int)a.size();
    int gap = n;
    bool swapped = true;
    while (gap > 1 || swapped) {
        gap = max(1, (int)(gap / 1.3));   // 縮減係數 1.3
        swapped = false;
        for (int i = 0; i + gap < n; ++i) {
            if (a[i] > a[i + gap]) {
                swap(a[i], a[i + gap]);
                swapped = true;
            }
        }
    }
}

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 = {
        {8, 4, 1, 56, 3, -44, 23, -6, 28, 0},
        {5, 2, 9, 1, 5, 6},
        {1, 2, 3, 4, 5},
        {5, 4, 3, 2, 1},
        {42},
        {},
    };
    for (auto& t : tests) {
        printVec("before: ", t);
        combSort(t);
        printVec("after : ", t);
        cout << "sorted : " << boolalpha
             << is_sorted(t.begin(), t.end()) << "\n\n";
    }
    return 0;
}