#include <iostream>
#include <vector>
#include <random>
#include <algorithm>
#include <chrono>
using namespace std;

// =============================================
// KONFIGURASI — ubah nilai di sini
// =============================================
const int DATA_SIZE = 1000000;  // jumlah elemen

// Pilih kondisi: "avg", "best", atau "worst"
const string CASE = "worst";
// =============================================

int qpartition(vector<int>& a, int lo, int hi) {
    int mid = lo + (hi-lo)/2;
    if (a[lo] > a[mid])  swap(a[lo], a[mid]);
    if (a[lo] > a[hi])   swap(a[lo], a[hi]);
    if (a[mid] > a[hi])  swap(a[mid], a[hi]);
    swap(a[mid], a[hi-1]);
    int pivot = a[hi-1], i = lo-1;
    for (int j = lo; j < hi-1; j++) if (a[j] <= pivot) swap(a[++i], a[j]);
    swap(a[i+1], a[hi-1]);
    return i+1;
}

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

void quickSort(vector<int>& a) { if (a.size() > 1) quickRec(a, 0, (int)a.size()-1); }

vector<int> generateData(int n, const string& caseType) {
    vector<int> data(n);

    if (caseType == "best") {
        // Best case: sudah terurut ascending
        for (int i = 0; i < n; i++) data[i] = i + 1;

    } else if (caseType == "worst") {
        // Worst case: urutan terbalik (descending)
        for (int i = 0; i < n; i++) data[i] = n - i;

    } else {
        // Average case: acak (random shuffle)
        for (int i = 0; i < n; i++) data[i] = i + 1;
        mt19937 rng(42);
        shuffle(data.begin(), data.end(), rng);
    }

    return data;
}

int main() {
    vector<int> data = generateData(DATA_SIZE, CASE);

    auto start = chrono::high_resolution_clock::now();
    quickSort(data);
    auto end = chrono::high_resolution_clock::now();

    double ms = chrono::duration<double, milli>(end - start).count();

    cout << "Case     : " << CASE << endl;
    cout << "Size     : " << DATA_SIZE << endl;
    cout << "Waktu    : " << ms << " ms" << endl;

    return 0;
}