Skip to content

Instantly share code, notes, and snippets.

@bgeron
Created December 24, 2019 17:50
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save bgeron/9e0688de632517efdccdd59ab3598026 to your computer and use it in GitHub Desktop.
Save bgeron/9e0688de632517efdccdd59ab3598026 to your computer and use it in GitHub Desktop.
Quicksort in Rust
[package]
name = "quicksort-rust"
version = "0.1.0"
authors = ["Bram Geron <bram@bram.xyz>"]
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"
#[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 <bram@bram.xyz>")
(about: "Quicksort microbenchmark")
(@arg size: +required "input size")
)
.get_matches();
let size = matches.value_of("size").unwrap().parse::<u32>().unwrap();
run_benchmark(size);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment