CSC 482 — HW3: Language Comparison

← All source

Rust — main.rs

Rust — Randomized Quicksort (CSC 482 HW3)

Toolchain

Build (release mode — required; debug builds are much slower)

Run from Windows via WSL, from the HW3/rust directory:

wsl.exe -d Ubuntu -- bash -c "cd '/mnt/c/Users/granite/Documents/DSU/Algorithms 482/3/HW3/rust' && cargo build --release"

Or, from inside a WSL shell already cd'd into HW3/rust:

cargo build --release

Run

wsl.exe -d Ubuntu -- bash -c "cd '/mnt/c/Users/granite/Documents/DSU/Algorithms 482/3/HW3/rust' && ./target/release/quicksort"

Or from inside WSL:

./target/release/quicksort

The binary prints each n,time_seconds row to stdout as it runs and also writes the same rows to HW3/results/rust.csv (path is ../results/rust.csv relative to HW3/rust, so it must be run with HW3/rust as the current directory, as above).

Files

Notes

// CSC 482 HW3 - Language Comparison: Rust implementation
//
// Randomized Quicksort per CLRS Ch. 5 (RANDOMIZED-QUICKSORT / RANDOMIZED-PARTITION).
// Original implementation, not copied from any online source. The only external
// dependency is the `rand` crate from crates.io (https://crates.io/crates/rand),
// which DESIGN.md explicitly permits since Rust's standard library has no RNG.
//
// Build/run (release mode, required for meaningful timings):
//   cargo build --release
//   ./target/release/quicksort

use rand::Rng;
use std::fs::File;
use std::io::Write;
use std::time::Instant;

/// RANDOMIZED-PARTITION(A, p, r): choose a pivot index uniformly at random in
/// [p, r], swap it into position r, then run the standard Lomuto partition
/// using A[r] as the pivot. Returns the final pivot index q, such that
/// everything in A[p..q] <= A[q] <= A[q+1..r].
fn randomized_partition(a: &mut [i32], p: usize, r: usize, rng: &mut impl Rng) -> usize {
    let pivot_index = rng.gen_range(p..=r);
    a.swap(pivot_index, r);
    lomuto_partition(a, p, r)
}

/// LOMUTO-PARTITION(A, p, r), pivot = A[r].
fn lomuto_partition(a: &mut [i32], p: usize, r: usize) -> usize {
    let pivot = a[r];
    let mut i = p; // boundary of elements <= pivot
    for j in p..r {
        if a[j] <= pivot {
            a.swap(i, j);
            i += 1;
        }
    }
    a.swap(i, r);
    i
}

/// RANDOMIZED-QUICKSORT(A, p, r) over inclusive bounds [p, r].
/// Uses an explicit stack instead of recursion so large n (recursion depth
/// ~O(n) worst case, ~O(log n) expected) never risks blowing the call stack.
fn randomized_quicksort(a: &mut [i32], rng: &mut impl Rng) {
    if a.len() < 2 {
        return;
    }
    let mut stack: Vec<(usize, usize)> = Vec::new();
    stack.push((0, a.len() - 1));

    while let Some((p, r)) = stack.pop() {
        if p >= r {
            continue;
        }
        let q = randomized_partition(a, p, r, rng);
        // Recurse on the left part [p, q-1] if non-empty.
        if q > p {
            stack.push((p, q - 1));
        }
        // Recurse on the right part [q+1, r] if non-empty.
        if q < r {
            stack.push((q + 1, r));
        }
    }
}

/// Generate a fresh Vec<i32> of length n with values uniformly random in
/// [0, 1_000_000). Not timed as part of the sort.
fn generate_random_vec(n: usize, rng: &mut impl Rng) -> Vec<i32> {
    (0..n).map(|_| rng.gen_range(0..1_000_000)).collect()
}

fn is_sorted(a: &[i32]) -> bool {
    a.windows(2).all(|w| w[0] <= w[1])
}

fn main() {
    let mut rng = rand::thread_rng();

    let results_path = "../results/rust.csv";
    let mut csv_file = File::create(results_path)
        .unwrap_or_else(|e| panic!("failed to create {}: {}", results_path, e));
    writeln!(csv_file, "n,time_seconds").unwrap();

    println!("n,time_seconds");

    let mut n: usize = 1000;
    let max_n: usize = 200_000_000;
    let max_iterations = 25;
    let time_limit_secs = 4.0;

    for iteration in 1..=max_iterations {
        // Data generation is NOT timed.
        let mut data = generate_random_vec(n, &mut rng);

        let start = Instant::now();
        randomized_quicksort(&mut data, &mut rng);
        let elapsed = start.elapsed();
        let elapsed_secs = elapsed.as_secs_f64();

        debug_assert!(is_sorted(&data));

        println!("{},{:.9}", n, elapsed_secs);
        writeln!(csv_file, "{},{:.9}", n, elapsed_secs).unwrap();
        csv_file.flush().unwrap();

        if elapsed_secs > time_limit_secs {
            println!(
                "# stopping: iteration {} took {:.3}s (> {:.1}s limit)",
                iteration, elapsed_secs, time_limit_secs
            );
            break;
        }
        if iteration == max_iterations {
            println!("# stopping: reached {} iterations", max_iterations);
            break;
        }
        let next_n = n.checked_mul(2).unwrap_or(usize::MAX);
        if next_n > max_n {
            println!(
                "# stopping: next n ({}) would exceed cap ({})",
                next_n, max_n
            );
            break;
        }
        n = next_n;
    }
}

Read Rust report