algorithms4 0.0.5

A rust implementation of the 4th edition of Algorithms by R. Sedgewick and K. Wayne.
Documentation
use std::hint::black_box;

use algorithms4::{
    HeapSort, MergeSort, QuickSort, binary_insertion_sort, insertion_sort,
    insertion_sort_x, selection_sort, shell_sort,
};
use criterion::{
    BenchmarkId, Criterion, Throughput, criterion_group, criterion_main,
};
use rand::RngExt;

fn exp_range() -> Vec<usize> {
    (5..11).map(|x| 2usize.pow(x)).collect::<Vec<_>>()
}

fn bench_elementary(c: &mut Criterion) {
    let mut rand = rand::rng();
    let mut group = c.benchmark_group("sorting_elementary");
    for &i in exp_range().iter() {
        let mut vec = vec![0; i];
        let m = i as i64;
        for item in vec.iter_mut() {
            *item = rand.random_range(-m / 2..m)
        }
        group.throughput(Throughput::Elements(i as u64));
        group.bench_with_input(
            BenchmarkId::new("insertion_sort", i),
            &i,
            |b, _| {
                b.iter(|| {
                    black_box(insertion_sort(black_box(&mut vec.clone())))
                })
            },
        );
        group.bench_with_input(
            BenchmarkId::new("insertion_sort_x", i),
            &i,
            |b, _| {
                b.iter(|| {
                    black_box(insertion_sort_x(black_box(&mut vec.clone())))
                })
            },
        );
        group.bench_with_input(
            BenchmarkId::new("binary_insertion_sort", i),
            &i,
            |b, _| {
                b.iter(|| {
                    black_box(binary_insertion_sort(black_box(
                        &mut vec.clone(),
                    )))
                })
            },
        );
        group.bench_with_input(
            BenchmarkId::new("selection_sort", i),
            &i,
            |b, _| {
                b.iter(|| {
                    black_box(selection_sort(black_box(&mut vec.clone())))
                })
            },
        );
        group.bench_with_input(
            BenchmarkId::new("shell_sort", i),
            &i,
            |b, _| {
                b.iter(|| black_box(shell_sort(black_box(&mut vec.clone()))))
            },
        );
    }
    group.finish();
}

fn bench_merge(c: &mut Criterion) {
    let mut rand = rand::rng();
    let mut group = c.benchmark_group("sorting_merge");
    for &i in exp_range().iter() {
        let mut vec = vec![0; i];
        let m = i as i64;
        for item in vec.iter_mut() {
            *item = rand.random_range(-m / 2..m)
        }
        group.throughput(Throughput::Elements(i as u64));
        group.bench_with_input(
            BenchmarkId::new("merge_top_down_sort", i),
            &i,
            |b, _| {
                b.iter(|| {
                    black_box(MergeSort::top_down_sort(black_box(
                        &mut vec.clone(),
                    )))
                })
            },
        );
        group.bench_with_input(
            BenchmarkId::new("merge_bottom_up_sort", i),
            &i,
            |b, _| {
                b.iter(|| {
                    black_box(MergeSort::bottom_up_sort(black_box(
                        &mut vec.clone(),
                    )))
                })
            },
        );
        group.bench_with_input(
            BenchmarkId::new("merge_index_sort", i),
            &i,
            |b, _| {
                b.iter(|| {
                    black_box(MergeSort::index_sort(black_box(
                        &mut vec.clone(),
                    )))
                })
            },
        );
    }
    group.finish();
}

fn bench_quick(c: &mut Criterion) {
    let mut rand = rand::rng();
    let mut group = c.benchmark_group("sorting_quick");
    for &i in exp_range().iter() {
        let mut vec = vec![0; i];
        let m = i as i64;
        for item in vec.iter_mut() {
            *item = rand.random_range(-m / 2..m)
        }
        group.throughput(Throughput::Elements(i as u64));
        group.bench_with_input(
            BenchmarkId::new("quick_sort", i),
            &i,
            |b, _| {
                b.iter(|| {
                    black_box(QuickSort::sort(black_box(&mut vec.clone())))
                })
            },
        );
        group.bench_with_input(
            BenchmarkId::new("quick_three_way_sort", i),
            &i,
            |b, _| {
                b.iter(|| {
                    black_box(QuickSort::three_way_sort(black_box(
                        &mut vec.clone(),
                    )))
                })
            },
        );
        group.bench_with_input(
            BenchmarkId::new("quick_optimized", i),
            &i,
            |b, _| {
                b.iter(|| {
                    black_box(QuickSort::optimized(black_box(&mut vec.clone())))
                })
            },
        );
    }
    group.finish();
}

fn bench_pq(c: &mut Criterion) {
    let mut rand = rand::rng();
    let mut group = c.benchmark_group("sorting_pq");
    for &i in exp_range().iter() {
        let mut vec = vec![0; i];
        let m = i as i64;
        for item in vec.iter_mut() {
            *item = rand.random_range(-m / 2..m)
        }
        group.throughput(Throughput::Elements(i as u64));
        group.bench_with_input(BenchmarkId::new("heap_sort", i), &i, |b, _| {
            b.iter(|| black_box(HeapSort::sort(black_box(&mut vec.clone()))))
        });
    }
    group.finish();
}

criterion_group!(
    benches,
    bench_elementary,
    bench_merge,
    bench_quick,
    bench_pq
);
criterion_main!(benches);