#include <iostream>
#include <vector>
#include <algorithm>
#include <random>
#include <chrono>
#include <iomanip>

// Modified Quicksort with three element rule
// Contact Email [email protected]
// Created by I.A

// Configuration Constants
const int NUM_ELEMENTS = 1000000;
const int NUM_TRIALS = 10;
const int NUM_REPEATS = 20;

// Helper function to print vector (for debugging small sizes)
void printVector(const std::vector<int>& arr) {
    for (int num : arr) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
}

/**
 * Applies the specific rule requested for subarrays of size 3.
 */
void apply_three_element_rule(std::vector<int>& arr, int low, int high) {
    int pivot = arr[low];      // First number as pivot
    int third_num = arr[high]; // Third number to compare

    if (third_num <= pivot) {
        // Swap all 3 to make pivot middle, third_num first
        int temp_mid = arr[low + 1];

        arr[high] = temp_mid;
        arr[low + 1] = pivot;
        arr[low] = third_num;
    } else {
        // Swap all 3 to make pivot middle, third_num last
        int temp_mid = arr[low + 1];

        arr[low] = temp_mid;
        arr[low + 1] = pivot;
        arr[high] = third_num;
    }
}

// Standard Hoare partition scheme
int partition(std::vector<int>& arr, int low, int high) {
    int pivot = arr[(low + high) / 2];
    int i = low - 1;
    int j = high + 1;

    while (true) {
        do {
            i++;
        } while (arr[i] < pivot);

        do {
            j--;
        } while (arr[j] > pivot);

        if (i >= j)
            return j;

        std::swap(arr[i], arr[j]);
    }
}

/**
 * Quicksort implementation.
 * Integrates the apply_three_element_rule when the subarray size is 3.
 */
void quickSortProb(std::vector<int>& arr, int low, int high) {
    if (low < high) {
        // Check for specific 3-element case
        if (high - low == 2) {
            apply_three_element_rule(arr, low, high);
        }

        // Partition the array
        int p = partition(arr, low, high);

        // Recursively sort elements before and after partition
        quickSortProb(arr, low, p);
        quickSortProb(arr, p + 1, high);
    }
}

/**
 * Standard Quicksort implementation (Recursive).
 */
void quickSort(std::vector<int>& arr, int low, int high) {
    if (low < high) {
        // p is the partitioning index, arr[p] is now at the right place
        int p = partition(arr, low, high);

        // Recursively sort elements before and after partition
        quickSort(arr, low, p);
        quickSort(arr, p + 1, high);
    }
}

void QuickSortStd(std::vector<int>& arr, int low, int high) {
    std::sort(&arr[low], &arr[high] + 1);
}

template<typename Function> int runBenchmark(Function testedFunction, const std::vector<int>& data, bool checkIfCorrectOutput) {
    std::vector<int> executionTimes;
    for (int i = 1; i <= NUM_REPEATS; ++i) {
        auto copiedData = data;
        auto start = std::chrono::steady_clock::now();
        testedFunction(copiedData, 0, NUM_ELEMENTS - 1);
        auto end = std::chrono::steady_clock::now();
        executionTimes.push_back(std::chrono::duration_cast<std::chrono::microseconds>(end - start).count());

        if (checkIfCorrectOutput) {
            bool sorted = true;
            for (size_t i = 0; i < copiedData.size() - 1; ++i) {
                if (copiedData[i] > copiedData[i + 1]) {
                    sorted = false;
                    break;
                }
            }
            if (!sorted) {
                std::cerr << "Error: Array not sorted on trial 1!" << std::endl;
            }
        }
    }
    return *std::min_element(executionTimes.begin(), executionTimes.end());
}

int main() {
    std::cout << "Starting Benchmark..." << std::endl;
    std::cout << "Elements per array: " << NUM_ELEMENTS << std::endl;
    std::cout << "Total Trials: " << NUM_TRIALS << std::endl;

    // Setup random number generation
    std::mt19937 gen(0x12345678);
    std::uniform_int_distribution<> distrib(1, 10000000);

    // Pre-allocate vector
    std::vector<int> data(NUM_ELEMENTS);

    std::cout << std::left;
    std::cout << std::setw(10) << "Trial nr" << " | "
        << std::setw(20) << "Quicksort [us]" << " | "
        << std::setw(20) << "QuicksortProb [us]" << " | "
        << std::setw(20) << "QuicksortStd [us]" << "\n";

    int sumOfMinTimesQuicksort = 0;
    int sumOfMinTimesQuicksortProb = 0;
    int sumOfMinTimesQuicksortStd = 0;

    for (int t = 1; t <= NUM_TRIALS; ++t) {
        for (int i = 0; i < NUM_ELEMENTS; ++i) {
            data[i] = distrib(gen);
        }
        int minTimeQuicksort = runBenchmark(quickSort, data, true);
        int minTimeQuicksortProb = runBenchmark(quickSortProb, data, true);
        int minTimeQuicksortStd = runBenchmark(QuickSortStd, data, true);
        std::cout << std::setw(10) << t << " | "
            << std::setw(20) << minTimeQuicksort << " | "
            << std::setw(20) << minTimeQuicksortProb << " | "
            << std::setw(20) << minTimeQuicksortStd << "\n";
        sumOfMinTimesQuicksort += minTimeQuicksort;
        sumOfMinTimesQuicksortProb += minTimeQuicksortProb;
        sumOfMinTimesQuicksortStd += minTimeQuicksortStd;
    }

    std::cout << std::setw(10) << "Total" << " | "
        << std::setw(20) << sumOfMinTimesQuicksort << " | "
        << std::setw(20) << sumOfMinTimesQuicksortProb << " | "
        << std::setw(20) << sumOfMinTimesQuicksortStd << '\n';

    std::cout << std::setw(30) << "quicksortProb / quicksort " << " = " << double(sumOfMinTimesQuicksortProb) / sumOfMinTimesQuicksort << '\n';
    std::cout << std::setw(30) << "quicksortProb / quicksortStd " << " = " << double(sumOfMinTimesQuicksortProb) / sumOfMinTimesQuicksortStd << '\n';

    return 0;
}