quick_sort.cpp

// quick_sort.cpp
// -----------------------------------------------------------------
// Quick Sort（快速排序）
//
// 原理：分治法。挑一個基準（pivot），把小於它的放左邊、大於的放右邊
//       （partition），然後遞迴排序左右兩半。
//
// 時間複雜度：最好 / 平均 O(n log n)
//             最壞 O(n^2)（pivot 挑得差，例如已排序 + 取首元素）
// 空間複雜度：O(log n)（遞迴堆疊，平均）
// 穩定性：不穩定
// 本檔示範：
//   1. Lomuto partition（易懂）
//   2. Hoare partition（交換少、較快）
//   3. 隨機 pivot（防最壞情況）
//   4. 三路切分（Dutch National Flag，大量重複元素時 O(n)）
//
// Compile: g++ -std=c++17 -O2 -Wall -o quick_sort quick_sort.cpp
// -----------------------------------------------------------------
#include <iostream>
#include <vector>
#include <algorithm>
#include <random>

using namespace std;

static mt19937 rng(20260703);

// ---------- 1. Lomuto partition ----------
static int lomutoPartition(vector<int>& a, int lo, int hi) {
    int pivot = a[hi];               // 取最後一個為 pivot
    int i = lo - 1;
    for (int j = lo; j < hi; ++j)
        if (a[j] < pivot) swap(a[++i], a[j]);
    swap(a[i + 1], a[hi]);
    return i + 1;
}

void quickSortLomuto(vector<int>& a, int lo, int hi) {
    if (lo >= hi) return;
    int p = lomutoPartition(a, lo, hi);
    quickSortLomuto(a, lo, p - 1);
    quickSortLomuto(a, p + 1, hi);
}

// ---------- 2+3. Hoare partition + 隨機 pivot ----------
static int hoarePartition(vector<int>& a, int lo, int hi) {
    // 隨機挑 pivot 防止最壞情況
    int pivot = a[lo + (int)(rng() % (hi - lo + 1))];
    int i = lo - 1, j = hi + 1;
    while (true) {
        do { ++i; } while (a[i] < pivot);
        do { --j; } while (a[j] > pivot);
        if (i >= j) return j;
        swap(a[i], a[j]);
    }
}

void quickSortHoare(vector<int>& a, int lo, int hi) {
    if (lo >= hi) return;
    int p = hoarePartition(a, lo, hi);
    quickSortHoare(a, lo, p);        // 注意：Hoare 是 [lo, p] 與 [p+1, hi]
    quickSortHoare(a, p + 1, hi);
}

// ---------- 4. 三路切分（重複元素多時特別有效） ----------
void quickSort3Way(vector<int>& a, int lo, int hi) {
    if (lo >= hi) return;
    int pivot = a[lo + (int)(rng() % (hi - lo + 1))];
    int lt = lo, i = lo, gt = hi;
    // 迴圈不變量：[lo,lt) < pivot, [lt,i) == pivot, (gt,hi] > pivot
    while (i <= gt) {
        if (a[i] < pivot)      swap(a[lt++], a[i++]);
        else if (a[i] > pivot) swap(a[i], a[gt--]);
        else                   ++i;
    }
    quickSort3Way(a, lo, lt - 1);
    quickSort3Way(a, gt + 1, hi);
}

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

int main() {
    vector<int> t1 = {10, 7, 8, 9, 1, 5};
    printVec("Lomuto  before: ", t1);
    quickSortLomuto(t1, 0, (int)t1.size() - 1);
    printVec("Lomuto  after : ", t1);
    cout << "sorted : " << boolalpha << is_sorted(t1.begin(), t1.end()) << "\n\n";

    vector<int> t2 = {5, 2, 9, 1, 5, 6, 3, 8, 4, 7};
    printVec("Hoare   before: ", t2);
    quickSortHoare(t2, 0, (int)t2.size() - 1);
    printVec("Hoare   after : ", t2);
    cout << "sorted : " << boolalpha << is_sorted(t2.begin(), t2.end()) << "\n\n";

    vector<int> t3 = {4, 2, 4, 1, 4, 2, 4, 4, 1, 2, 4};   // 大量重複
    printVec("3-way   before: ", t3);
    quickSort3Way(t3, 0, (int)t3.size() - 1);
    printVec("3-way   after : ", t3);
    cout << "sorted : " << boolalpha << is_sorted(t3.begin(), t3.end()) << "\n\n";

    // 邊界情況
    vector<int> t4 = {};
    vector<int> t5 = {42};
    vector<int> t6 = {1, 2, 3, 4, 5};   // 已排序（隨機 pivot 不怕）
    quickSortHoare(t6, 0, (int)t6.size() - 1);
    printVec("edge sorted    : ", t6);
    cout << "empty & single handled OK\n";
    (void)t4; (void)t5;
    return 0;
}