Modified Pivot Median vs Standard Pivot Median Quicksort

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

// Modified Pivot Median vs Standard Pivot Median Quicksort
// Contact Email [email protected]
// Created by I.A

const int NUM_ELEMENTS = 1000000; // 1000000-100000000
const int NUM_TRIALS = 1000;        // Number of test runs to average

thread_local std::random_device rd_pivot;
thread_local std::mt19937 gen_pivot(rd_pivot());

// Standard Hoare Partition using a pre-selected pivot value
int partition(std::vector<int>& arr, int low, int high, int pivot) {
    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]);
    }
}

int getStandardMedian(const std::vector<int>& arr, int low, int high) {
    int mid = low + (high - low) / 2;
    int a = arr[low], b = arr[mid], c = arr[high];

    int max_v = std::max({a, b, c});
    int min_v = std::min({a, b, c});
    return a + b + c - max_v - min_v;
}

void standardQuicksort(std::vector<int>& arr, int low, int high) {
    if (low < high) {
        int pivot = getStandardMedian(arr, low, high);
        int p = partition(arr, low, high, pivot);

        standardQuicksort(arr, low, p);
        standardQuicksort(arr, p + 1, high);
    }
}


// Modified Median

int getCustomMedian(const std::vector<int>& arr, int low, int high) {
    int mid = low + (high - low) / 2;
    int a = arr[low], b = arr[mid], c = arr[high];

    int max_val = std::max({a, b, c});
    int min_val = std::min({a, b, c});
    int med_val = a + b + c - max_val - min_val;

    double total_range = (double)max_val - min_val;

    // Prevent division by zero if all three numbers are identical
    if (total_range <= 0.0) return med_val;

    // 1. Calculate gaps and their percentage of the total range
    double gap_min = med_val - min_val;
    double gap_max = max_val - med_val;

    double pct_min = gap_min / total_range;
    double pct_max = gap_max / total_range;

    // 2. If the median is relatively centered, do nothing.
    // Below are notes for different percentages and tests
    // We use a 75% threshold. If one gap takes up more than 75% of the total range,
    // the other number is a massive outlier.
    // [1, 5000, 10000] -> pct_max is ~50% (Passed, returns 5000)
    // [1, 5000, 40000] -> pct_max is ~87.5% (Triggers the fallback below)
    if (pct_max <= 0.75 && pct_min <= 0.75) {
        return med_val;
    }

    // 3. Random Search Fallback
    int max_attempts = 5;

    for (int i = 0; i < max_attempts; ++i) {
        // Pick a random number from the current sub-array
        int rand_idx = low + std::rand() % (high - low + 1);
        int candidate = arr[rand_idx];

        if (pct_max > 0.80) {
            // Max is the outlier. Target the gap between med and max.
            double margin = gap_max * 0.80;
            if (candidate >= med_val + margin && candidate <= max_val - margin) {
                return candidate;
            }
        }
        else if (pct_min > 0.80) {
            // Min is the outlier. Target the gap between min and med.
            double margin = gap_min * 0.80;
            if (candidate >= min_val + margin && candidate <= med_val - margin) {
                return candidate;
            }
        }
    }
    // just return the original median so QuickSort doesn't crash.
    return med_val;
}

void customQuicksort(std::vector<int>& arr, int low, int high) {
    if (low < high) {
        int pivot = getCustomMedian(arr, low, high);
        int p = partition(arr, low, high, pivot);

        customQuicksort(arr, low, p);
        customQuicksort(arr, p + 1, high);
    }
}

int main() {
    std::cout << "Starting Quicksort Benchmark..." << std::endl;
    std::cout << "Elements: " << NUM_ELEMENTS << " | Trials: " << NUM_TRIALS << "\n" << std::endl;

    std::random_device rd;
    std::mt19937 gen(rd());
    std::uniform_int_distribution<> distrib(1, 100);

    std::vector<int> source_data(NUM_ELEMENTS);
    std::chrono::duration<double> total_std_time(0);
    std::chrono::duration<double> total_cust_time(0);

    for (int t = 1; t <= NUM_TRIALS; ++t) {
        // 1. Generate fresh random data for this trial
        for (int i = 0; i < NUM_ELEMENTS; ++i) {
            source_data[i] = distrib(gen);
        }

        // --- Benchmark Standard ---
        std::vector<int> data_std = source_data;
        auto start_std = std::chrono::steady_clock::now();
        standardQuicksort(data_std, 0, NUM_ELEMENTS - 1);
        auto end_std = std::chrono::steady_clock::now();
        total_std_time += (end_std - start_std);

        // --- Benchmark Custom ---
        std::vector<int> data_cust = source_data;
        auto start_cust = std::chrono::steady_clock::now();
        customQuicksort(data_cust, 0, NUM_ELEMENTS - 1);
        auto end_cust = std::chrono::steady_clock::now();
        total_cust_time += (end_cust - start_cust);

        // Sanity check on first trial
        if (t == 1) {
            if (!std::is_sorted(data_std.begin(), data_std.end()) ||
                !std::is_sorted(data_cust.begin(), data_cust.end())) {
                std::cerr << "Sorting Error Detected!" << std::endl;
                return 1;
            }
        }

        if (t % 100 == 0) {
            std::cout << "Completed Trial " << t << "/" << NUM_TRIALS << "\r" << std::flush;
        }
    }

    std::cout << "\n\n--- BENCHMARK RESULTS ---" << std::endl;
    std::cout << "Standard Median-of-Three Avg: " << total_std_time.count() / NUM_TRIALS << " seconds" << std::endl;
    std::cout << "Modified Custom Pivot Avg:   " << total_cust_time.count() / NUM_TRIALS << " seconds" << std::endl;

    if (total_cust_time < total_std_time) {
        double diff = (total_std_time.count() - total_cust_time.count()) / total_std_time.count() * 100.0;
        std::cout << "\nCustom logic was " << diff << "% faster." << std::endl;
    } else {
        double diff = (total_cust_time.count() - total_std_time.count()) / total_std_time.count() * 100.0;
        std::cout << "\nStandard logic was " << diff << "% faster." << std::endl;
    }

    return 0;
}