← All source

C++ — quicksort.cpp

g++ -O2 -std=c++17 -o quicksort quicksort.cpp

./quicksort

wsl.exe -d Ubuntu -- bash -c "cd '/mnt/c/Users/granite/Documents/DSU/Algorithms 482/3/HW3/cpp' && g++ -O2 -std=c++17 -o quicksort quicksort.cpp && ./quicksort"

// Randomized Quicksort - C++ implementation
//
// CSC 482 HW3 - Language Comparison
//
// Algorithm: CLRS (Cormen, Leiserson, Rivest & Stein), Introduction to
// Algorithms, Ch. 5, RANDOMIZED-QUICKSORT / RANDOMIZED-PARTITION pseudocode.
// No external code used - original implementation based on that pseudocode.
//
// In-place quicksort on a std::vector<int>: at every partition step, a pivot
// index is chosen uniformly at random from the current subarray range and
// swapped into the last position before running a standard Lomuto partition.
//
// Timing harness per HW3/DESIGN.md: n starts at 1000, doubles each
// iteration, array of n random ints in [0, 1000000) generated fresh each
// iteration (generation not timed), only the sort call is timed with
// std::chrono::steady_clock. Loop stops when an iteration's elapsed time
// exceeds 4.0s, or 25 iterations have run, or the next n would exceed
// 200,000,000 - whichever comes first.

#include <chrono>
#include <cstdio>
#include <fstream>
#include <iostream>
#include <random>
#include <vector>

// Single RNG used for both pivot selection and data generation, seeded from
// a random_device (per DESIGN.md: use <random>'s mt19937 + uniform_int_distribution).
static std::mt19937 rng(std::random_device{}());

// RANDOMIZED-PARTITION(A, p, r): pick a uniformly random index in [p, r],
// swap it into position r, then run Lomuto partition around A[r].
static int randomizedPartition(std::vector<int>& a, int p, int r) {
    std::uniform_int_distribution<int> dist(p, r);
    int i = dist(rng);
    std::swap(a[i], a[r]);

    int pivot = a[r];
    int lo = p - 1;
    for (int j = p; j < r; ++j) {
        if (a[j] <= pivot) {
            ++lo;
            std::swap(a[lo], a[j]);
        }
    }
    std::swap(a[lo + 1], a[r]);
    return lo + 1;
}

// RANDOMIZED-QUICKSORT(A, p, r)
static void randomizedQuicksort(std::vector<int>& a, int p, int r) {
    while (p < r) {
        int q = randomizedPartition(a, p, r);
        // Recurse into the smaller side, loop over the larger side, to keep
        // worst-case recursion depth O(log n) on average.
        if (q - p < r - q) {
            randomizedQuicksort(a, p, q - 1);
            p = q + 1;
        } else {
            randomizedQuicksort(a, q + 1, r);
            r = q - 1;
        }
    }
}

static void randomizedQuicksort(std::vector<int>& a) {
    if (!a.empty()) {
        randomizedQuicksort(a, 0, static_cast<int>(a.size()) - 1);
    }
}

static std::vector<int> generateRandomArray(long long n, int lo, int hi) {
    std::vector<int> a(static_cast<size_t>(n));
    std::uniform_int_distribution<int> dist(lo, hi - 1);
    for (long long i = 0; i < n; ++i) {
        a[static_cast<size_t>(i)] = dist(rng);
    }
    return a;
}

int main() {
    const double TIME_LIMIT_SECONDS = 4.0;
    const int MAX_ITERATIONS = 25;
    const long long N_CAP = 200000000LL;

    long long n = 1000;

    std::ofstream csv("../results/cpp.csv");
    if (!csv.is_open()) {
        std::cerr << "Failed to open ../results/cpp.csv for writing\n";
        return 1;
    }
    csv << "n,time_seconds\n";
    std::cout << "n,time_seconds\n";

    for (int iter = 0; iter < MAX_ITERATIONS; ++iter) {
        std::vector<int> a = generateRandomArray(n, 0, 1000000);

        auto start = std::chrono::steady_clock::now();
        randomizedQuicksort(a);
        auto end = std::chrono::steady_clock::now();

        std::chrono::duration<double> elapsed = end - start;
        double elapsedSeconds = elapsed.count();

        csv << n << "," << elapsedSeconds << "\n";
        csv.flush();
        std::printf("%lld,%.9f\n", n, elapsedSeconds);

        if (elapsedSeconds > TIME_LIMIT_SECONDS) {
            break;
        }
        if (n * 2 > N_CAP) {
            break;
        }
        n *= 2;
    }

    csv.close();
    return 0;
}

Read C++ report