Modified Probability Quicksort Algorithm

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

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

// Configuration Constants
const int NUM_ELEMENTS = 1000000; // 1 million elements
const int NUM_TRIALS = 1000;     // 1000 trials

// 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) {
    // Corrected condition: size 3 implies high - low == 2 (e.g., indices 0, 1, 2)
    if (high - low == 2) {
        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];
    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 quickSort(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
        quickSort(arr, low, p);
        quickSort(arr, p + 1, high);
    }
}

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::random_device rd;
    std::mt19937 gen(rd());
    std::uniform_int_distribution<> distrib(1, 10000000);

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

    // Variable to hold ONLY the time spent sorting
    std::chrono::duration<double> total_sort_duration(0);

    for (int t = 1; t <= NUM_TRIALS; ++t) {
        // 1. Generate Random Numbers (NOT TIMED)
        for (int i = 0; i < NUM_ELEMENTS; ++i) {
            data[i] = distrib(gen);
        }

        // 2. Start Timer (Start "Stopwatch")
        auto start = std::chrono::high_resolution_clock::now();

        // 3. Run Quicksort
        quickSort(data, 0, NUM_ELEMENTS - 1);

        // 4. Stop Timer (Stop "Stopwatch")
        auto end = std::chrono::high_resolution_clock::now();

        // 5. Add difference to accumulator
        total_sort_duration += (end - start);

        // Optional: Simple check to ensure sorted (checks only first trial)
        if (t == 1) {
            bool sorted = true;
            for (size_t i = 0; i < data.size() - 1; ++i) {
                if (data[i] > data[i+1]) {
                    sorted = false;
                    break;
                }
            }
            if (!sorted) {
                std::cerr << "Error: Array not sorted on trial 1!" << std::endl;
                return 1;
            }
        }

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

    std::cout << "\n\nBenchmark Complete." << std::endl;

    // Output stats based on the accumulated sort duration
    std::cout << "Total Sorting Time (excluding generation): " << total_sort_duration.count() << " seconds" << std::endl;
    std::cout << "Average Time per Sort: " << total_sort_duration.count() / NUM_TRIALS << " seconds" << std::endl;

    return 0;
}