kth.cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <ctime>
#include <random>

double findMedian(std::vector<double> &arr, int l, int r) {
    std::sort(arr.begin() + l, arr.begin() + r + 1);
    int n = r - l + 1;
    return arr[l + n / 2];
}

double SELECT(std::vector<double> &arr, int l, int r, int k, int groupSize) {
    if (l == r) {
        return arr[l];
    }

    int n = r - l + 1;
    int numMedians = (n + groupSize - 1) / groupSize;
    std::vector<double> medians(numMedians);

    for (int i = 0; i < numMedians; i++) {
        int groupEnd = std::min(l + (i + 1) * groupSize - 1, r);
        medians[i] = findMedian(arr, l + i * groupSize, groupEnd);
    }

    double pivot = SELECT(medians, 0, numMedians - 1, numMedians / 2, groupSize);

    int partitionIndex =
            std::partition(arr.begin() + l, arr.begin() + r + 1, [pivot](double num) { return num < pivot; }) -
            arr.begin();

    if (k == partitionIndex) {
        return arr[k];
    } else if (k < partitionIndex) {
        return SELECT(arr, l, partitionIndex - 1, k, groupSize);
    } else {
        return SELECT(arr, partitionIndex + 1, r, k, groupSize);
    }
}

double randomizedSelect(std::vector<double> &arr, int l, int r, int k) {
    std::random_device rd;
    std::mt19937 gen(rd());
    std::uniform_int_distribution<> dis(l, r);

    int pivotIndex = dis(gen);
    std::swap(arr[pivotIndex], arr[r]);
    int i = l;
    for (int j = l; j <= r - 1; j++) {
        if (arr[j] <= arr[r]) {
            std::swap(arr[i], arr[j]);
            i++;
        }
    }
    std::swap(arr[i], arr[r]);

    if (k == i)
        return arr[i];
    if (k < i)
        return randomizedSelect(arr, l, i - 1, k);

    return randomizedSelect(arr, i + 1, r, k);
}

int main() {
    std::ios::sync_with_stdio(true);
    std::random_device rd;
    std::mt19937 g(rd());

    int N = 10000000;  // 1e8
    std::vector<double> arr(N);
    for (int i = 0; i < N; ++i) arr[i] = i;
    std::shuffle(arr.begin(), arr.end(), g);

    int k = N / 2;

    std::cout << "|---------|----------|--------------------|" << '\n'
              << "|  Group  |   Time   |       result       |" << '\n'
              << "|---------|----------|--------------------|" << '\n';

    int test[4] = {3, 5, 7, 9};
    for (int _n = 0; _n < 4; _n++) {
        double time = 0;
        std::vector<double> copied = arr;
        double result;
        for (int i = 0; i < 50; i++) {
            printf("|    %d    |   %.2f   |       %02d/50        |\r", test[_n], (time / (double) i) / CLOCKS_PER_SEC, i);
            fflush(stdout);
            clock_t start = clock();
            result = SELECT(copied, 0, N - 1, k, test[_n]);
            clock_t end = clock();
            time += (end - start);
        }
        printf("|    %d    |   %.2f   |       %d      |\n", test[_n], (time / 50.0) / CLOCKS_PER_SEC, (int) result);
    }
    for (int _n = 0; _n < 1; _n++) {
        double time = 0;
        std::vector<double> copied = arr;
        double result;
        for (int i = 0; i < 50; i++) {
            printf("| random |   %.2f   |       %02d/50        |\r", (time / (double) i) / CLOCKS_PER_SEC, i);
            fflush(stdout);
            clock_t start = clock();
            result = randomizedSelect(copied, 0, N - 1, k);
            clock_t end = clock();
            time += (end - start);
        }
        printf("|  random |   %.2f   |       %d      |\n",  (time / 50.0) / CLOCKS_PER_SEC, (int) result);
    }
    return 0;
}