← All source

Zig — quicksort.zig

zig build-exe quicksort.zig -O ReleaseFast

./quicksort

wsl.exe -d Ubuntu -- bash -c "cd '/mnt/c/Users/granite/Documents/DSU/Algorithms 482/3/HW3/zig' && zig build-exe quicksort.zig -O ReleaseFast && ./quicksort"

// Randomized Quicksort (CLRS Ch. 5, RANDOMIZED-QUICKSORT / RANDOMIZED-PARTITION)
// Timing harness per HW3/DESIGN.md.
//
// No external code used - original implementation based on CLRS
// RANDOMIZED-QUICKSORT / RANDOMIZED-PARTITION pseudocode.
//
// Build: zig build-exe quicksort.zig -O ReleaseFast
// Run:   ./quicksort

const std = @import("std");

/// Lomuto partition scheme (CLRS PARTITION), operating on arr[lo..hi] inclusive,
/// with hi as the (already pivot-swapped) partition element.
fn partition(arr: []i32, lo: usize, hi: usize) usize {
    const pivot = arr[hi];
    var i: usize = lo; // index of the last element <= pivot, offset by 1
    var j: usize = lo;
    while (j < hi) : (j += 1) {
        if (arr[j] <= pivot) {
            std.mem.swap(i32, &arr[i], &arr[j]);
            i += 1;
        }
    }
    std.mem.swap(i32, &arr[i], &arr[hi]);
    return i;
}

/// RANDOMIZED-PARTITION: pick a pivot index uniformly at random in [lo, hi],
/// swap it into the last position, then run the standard partition.
fn randomizedPartition(arr: []i32, lo: usize, hi: usize, rand: std.Random) usize {
    const pivot_idx = rand.intRangeAtMost(usize, lo, hi);
    std.mem.swap(i32, &arr[pivot_idx], &arr[hi]);
    return partition(arr, lo, hi);
}

/// RANDOMIZED-QUICKSORT over arr[lo..hi] inclusive. Recursive, matching CLRS.
fn randomizedQuicksort(arr: []i32, lo: usize, hi: usize, rand: std.Random) void {
    if (lo >= hi) return; // covers empty/single-element ranges (also guards hi underflow at call sites)
    const p = randomizedPartition(arr, lo, hi, rand);
    if (p > 0) randomizedQuicksort(arr, lo, p - 1, rand);
    randomizedQuicksort(arr, p + 1, hi, rand);
}

/// Public entry point mirroring CLRS's top-level call, for an array of length n.
fn sort(arr: []i32, rand: std.Random) void {
    if (arr.len < 2) return;
    randomizedQuicksort(arr, 0, arr.len - 1, rand);
}

pub fn main() !void {
    const allocator = std.heap.page_allocator;

    // Seed the RNG from the OS CSPRNG (std.crypto.random), used for BOTH
    // data generation and randomized pivot selection, per DESIGN.md.
    var prng = std.Random.DefaultPrng.init(blk: {
        var seed: u64 = undefined;
        std.crypto.random.bytes(std.mem.asBytes(&seed));
        break :blk seed;
    });
    const rand = prng.random();

    const results_path = "../results/zig.csv";
    var csv_file = try std.fs.cwd().createFile(results_path, .{ .truncate = true });
    defer csv_file.close();
    var buf_writer = std.io.bufferedWriter(csv_file.writer());
    const writer = buf_writer.writer();

    try writer.writeAll("n,time_seconds\n");
    const stdout = std.io.getStdOut().writer();
    try stdout.writeAll("n,time_seconds\n");

    var n: usize = 1000;
    var iterations: usize = 0;
    const max_iterations: usize = 25;
    const time_limit_s: f64 = 4.0;
    const n_cap: usize = 200_000_000;

    while (true) {
        // Generate fresh random data (NOT timed).
        const arr = try allocator.alloc(i32, n);
        defer allocator.free(arr);
        for (arr) |*x| {
            x.* = rand.intRangeLessThan(i32, 0, 1_000_000);
        }

        var timer = try std.time.Timer.start();
        sort(arr, rand);
        const elapsed_ns = timer.read();
        const elapsed_s: f64 = @as(f64, @floatFromInt(elapsed_ns)) / 1_000_000_000.0;

        iterations += 1;

        const line = try std.fmt.allocPrint(allocator, "{d},{d:.6}\n", .{ n, elapsed_s });
        defer allocator.free(line);
        try writer.writeAll(line);
        try buf_writer.flush();
        try stdout.writeAll(line);

        if (elapsed_s > time_limit_s) break;
        if (iterations >= max_iterations) break;
        if (n > n_cap / 2) break; // next n = n*2 would exceed the cap

        n *= 2;
    }
}

Read Zig report