cycle_sort.cpp

// cycle_sort.cpp
// -----------------------------------------------------------------
// Cycle Sort（循環排序）
//
// 原理：把每個元素「一次到位」——計算元素最終位置，直接放過去，
//       被擠出的元素再找它的家，形成一個循環（cycle）。
//
// 時間複雜度：最好 / 平均 / 最壞 都是 O(n^2)（比較多）
// 空間複雜度：O(1)
// 穩定性：不穩定
// 特點：「寫入次數」理論最少（每個元素最多寫一次），
//       適合快閃記憶體等寫入昂貴的場景。
//
// Compile: g++ -std=c++17 -O2 -Wall -o cycle_sort cycle_sort.cpp
// -----------------------------------------------------------------
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int cycleSort(vector<int>& a) {          // 回傳寫入次數
    int n = (int)a.size();
    int writes = 0;
    for (int start = 0; start < n - 1; ++start) {
        int item = a[start];

        // 計算 item 的最終位置：數有幾個元素比它小
        int pos = start;
        for (int i = start + 1; i < n; ++i)
            if (a[i] < item) ++pos;
        if (pos == start) continue;       // 已在正確位置

        while (item == a[pos]) ++pos;     // 跳過相等元素
        swap(item, a[pos]); ++writes;

        // 繼續安置被擠出的元素，直到回到 start
        while (pos != start) {
            pos = start;
            for (int i = start + 1; i < n; ++i)
                if (a[i] < item) ++pos;
            while (item == a[pos]) ++pos;
            swap(item, a[pos]); ++writes;
        }
    }
    return writes;
}

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 = {
        {1, 8, 3, 9, 10, 10, 2, 4},
        {5, 2, 9, 1, 5, 6},
        {1, 2, 3, 4, 5},     // 已排序 -> 0 次寫入
        {5, 4, 3, 2, 1},
        {42},
        {},
    };
    for (auto& t : tests) {
        printVec("before: ", t);
        int w = cycleSort(t);
        printVec("after : ", t);
        cout << "writes : " << w
             << " | sorted : " << boolalpha
             << is_sorted(t.begin(), t.end()) << "\n\n";
    }
    return 0;
}