Standard Quicksort Algorithm

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

// Standard Quicksort
// 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;
}

// Standard Hoare partition scheme
int partition(std::vector<int>& arr, int low, int high) {
    // Hoare's partition uses the first element as the pivot
    int pivot = arr[low];
    int i = low - 1;
    int j = high + 1;

    while (true) {
        // Find element on the left that is >= pivot
        do {
            i++;
        } while (arr[i] < pivot);

        // Find element on the right that is <= pivot
        do {
            j--;
        } while (arr[j] > pivot);

        // If pointers cross, partition is complete
        if (i >= j)
            return j;

        // Swap elements at i and j
        std::swap(arr[i], arr[j]);
    }
}

/**
 * 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);
    }
}

int main() {
    std::cout << "Starting Benchmark (Standard Quicksort)..." << 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 (Time NOT recorded here)
        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 (THIS TIME IS RECORDED)
        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 to save time)
        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;
}