Quicksort in Rust

README.md

Inspired by http://macias.info/entry/201912201300_graal_aot.md and https://www.reddit.com/r/java/comments/eez8g9/java_jit_vs_java_aot_vs_go_for_small_shortlived/ .

CC-BY-SA 2.0 Bram Geron

Cargo.toml

[package]
name = "quicksort-rust"
version = "0.1.0"
authors = ["Bram Geron <[email protected]>"]
edition = "2018"

# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html

[dependencies]
rand = "0.7.2"
clap = "2.33.0"

src-main.rs

#[macro_use]
extern crate clap;

fn run_benchmark(size: u32) {
    let mut vec = make_rand_vec(size);

    quick_sort(&mut vec);

    assert_sorted(&vec);
}

fn quick_sort(slice: &mut [i32]) {
    if !slice.is_empty() {
        let partition_index = partition(slice);
        let len = slice.len();

        quick_sort(&mut slice[0..partition_index]);
        quick_sort(&mut slice[partition_index + 1..len]);
        assert_sorted(slice);
    }
}

fn partition(slice: &mut [i32]) -> usize {
    let len = slice.len();
    let pivot = slice[len - 1];
    let mut i = 0;
    let mut j = 0;

    while j < len - 1 {
        if slice[j] <= pivot {
            slice.swap(i, j);
            i += 1;
        }
        j += 1;
    }

    slice.swap(i, len - 1);

    i
}

fn assert_sorted(slice: &[i32]) {
    for i in 1..slice.len() {
        assert!(slice[i - 1] <= slice[i])
    }
}

fn make_rand_vec(size: u32) -> Vec<i32> {
    let mut slice: Vec<i32> = Vec::new();
    for _ in 0..size {
        slice.push(rand::random::<i32>());
    }
    slice
}

fn main() {
    let matches = clap_app!(myapp =>
        (version: "0.1")
        (author: "Bram Geron <[email protected]>")
        (about: "Quicksort microbenchmark")
        (@arg size: +required "input size")
    )
    .get_matches();

    let size = matches.value_of("size").unwrap().parse::<u32>().unwrap();

    run_benchmark(size);
}