benchplot is a utility for benchmarking functions over various input
sizes and plotting the results.
use benchplot::{BenchBuilder,BenchFnArg,BenchFnNamed};use rand::Rng;fnmain(){// Functions to benchmark (with names)let functions:Vec<BenchFnNamed<Vec<i32>,Vec<i32>>> = vec![(Box::new(bubble_sort),"Bubble Sort"),(Box::new(insertion_sort),"Insertion Sort"),(Box::new(merge_sort),"Merge Sort"),];// For each size, returns an argument to pass to the functions to benchmarklet argfunc:BenchFnArg<Vec<i32>> = Box::new(|size:usize| {letmut rng = rand::thread_rng();(0..size).map(|_| rng.gen_range(1..=1000)).collect()});// Input sizes to test. NOTE: a wider range was used for the image above.let sizes:Vec<usize> = (0..15).map(|k| 1 << k).collect();// Build a `Bench` instanceletmut bench = BenchBuilder::new(functions, argfunc, sizes).repetitions(1).parallel(true).assert_equal(true).build().unwrap();// Run benchmarks and plot them
bench
.run().plot("output.svg").title("Sorting Algorithms").build().expect("Plotting failed");}// Bubble Sort: O(n²)fnbubble_sort(muta:Vec<i32>) -> Vec<i32>{letmut n = a.len();while n > 1{letmut np = 0;for i in1..n {if a[i - 1] > a[i]{
a.swap(i - 1, i);
np = i;}}
n = np;}
a
}// Insertion Sort: O(n²)fninsertion_sort(muta:Vec<i32>) -> Vec<i32>{let n = a.len();for i in1..n {let x = a[i];letmut j = i;while j > 0 && a[j - 1] > x {
a[j] = a[j - 1];
j -= 1;}
a[j] = x;}
a
}// Merge Sort: O(n log n)// Based on code from https://en.wikipedia.org/wiki/Merge_sortfnmerge_sort(muta:Vec<i32>) -> Vec<i32>{let len = a.len();letmut b = a.clone();top_down_split_merge(&mut a,0, len,&mut b);
a
}fntop_down_split_merge(b:&mut[i32],begin:usize,end:usize,a:&mut[i32],){if end - begin <= 1{return;}let middle = (end + begin) / 2;top_down_split_merge(a, begin, middle, b);top_down_split_merge(a, middle, end, b);top_down_merge(b, begin, middle, end, a);}fntop_down_merge(b:&mut[i32],begin:usize,middle:usize,end:usize,a:&mut[i32],){letmut i = begin;letmut j = middle;for b_k in b.iter_mut().take(end).skip(begin){if i < middle && (j >= end || a[i] <= a[j]){*b_k = a[i];
i += 1;}else{*b_k = a[j];
j += 1;}}}This project is dual-licensed under either the Apache License, Version 2.0 or the MIT License, at your option.
Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in this project by you shall be dual-licensed as above, without any additional terms or conditions.