// Quick Sort 快速排序
//   时间：O(n log n) 平均
//         O(n^2) 最坏
//   空间：O(log n) 平均递归栈
//    最坏 O(n)
//   稳定：否
#include "common/sort_test.hpp"

void quick_sort(std::vector<int> &a, int l, int r)
{

    if (r - l <= 0)
        return;
    std::swap(a[l], a[r]);
    int p = a[l];
    int i = l - 1, j = r + 1; // 两个指针分别指向最左边和最右边
    while (true)
    {
        do
        {
            ++i;
        } while (a[i] < p);
        do
        {
            --j;
        } while (a[j] > p);
        if (i >= j) // 判断是否已经分好
            break;
        std::swap(a[i], a[j]);
    }
    quick_sort(a, l, j);
    quick_sort(a, j + 1, r);
}

int main(int argc, char **argv)
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    return sort_test::run("Quick Sort", [](std::vector<int> &a)
                          { quick_sort(a, 0, static_cast<int>(a.size()) - 1); }, argc, argv);
}