Lib.rs

› Algorithms
#sorting #library

bin+lib sorting_rs

Collection of sorting algorithms implemented in Rust

by Konstantin Fedotov

12 stable releases

1.2.10 Aug 16, 2020
1.2.9 Aug 13, 2020
1.2.2 Jul 25, 2020

#789 in Algorithms

MIT license

83KB
1.5K SLoC

sorting_rs

Sorting algorithms implemented in Rust.

Usage

  1. Add this dependency and please consider it's version into your Cargo.toml:
[dependencies]
sorting_rs = "1.2.0"
  1. Use available sorting algorithms in your Rust code:
use sorting_rs::*;
  1. API for every sorting function is pretty the same: you just have to pass mutable reference: &mut [T], or vec![T, T, T, ...]. T should have PartialOrd trait, sometimes you may need Copy or Clone traits, though all implementations try to avoid this kind of additional requirements.
  2. For more information about origin of algorithms and implementation details, please read modules documentation. Wikipedia is nice starting point too.

This library contains following sorting algorithms:

Sorting algorithm Features and downsides Worst-case performance O(): comparisons; swaps Best-case performance O(): comparisons; swaps Space complexity O()
Bingo aims to be faster than selection sort if there are duplicates n + m2 nm
Bitonic method based on building a sorting network nlog2n nlog2n nlog2n
Bubble bad for sorted or reversed input n2; n2 n; 1 1
Cocktail little performance improvement over bubble sort n2 n 1
Comb speeds up when data is nearly sorted n2 nlogn 1
Cycle uses minimum amount of writes, good for memory with limited TBW n2 n2 1
Gnome simple and slow, works with one item at a time n2 n 1
Heap independent of data distribution nlogn nlogn 1
Weak Heap independent of data distribution, decreased number of comparisons nlogn nlogn 1
N-Heap should be faster than default heap. N = 3 nlogn nlogn 1
Bottom-up Heap upgraded version of heapsort with decreased number of comparisons nlogn nlogn 1
Insertion simple, but less effective than quicksort, heapsort or merge sort n2; n2 n; 1 1
Merge independent of data distribution nlogn nlogn n
Merge Bottom-up independent of data distribution, modified version of mergesort nlogn nlogn n
Odd-even presented to be effective on processors with local interconnections n2 n 1
Odd-even Batcher more efficient version of odd-even sort log2n log2n logn2
Pancake swaps data a lot and not so effective in practice n3; 2n - 3 n2 n
Quick bad for sorted or reversed input n2 nlogn logn
Quick dual enchanced version of quicksort n2 2nlnn logn
Ksort quicksort variant, faster than heap at less than 7 million elements n2 nlog2n logn
Selection the least number of swaps among all the algorithms n2; n n2; 1 1
Double selection modified selection sort with more workload, but better efficiency n2; n n2; 1 higher than Selection
Shellsort it is optimization of insertion sort n3/2 or nlogn2 nlogn 1
Slow it's slow, who would ever need it?
Smooth variant of heapsort, good for nearly sorted data nlogn n 1
Stooge it's a bit faster than slow sort n2.7095 n

New algorithms implementations are planned in future

No runtime deps