sorting_rs
Sorting algorithms implemented in Rust
Usage
- Add this dependency and please consider it's version into your Cargo.toml:
[]
= "1.2.0"
- Use available sorting algorithms in your Rust code:
use *;
- For more information about origin of algorithms and implementation details, please read modules documentation. wikipedia is nice starting point too
- For API
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() |
---|---|---|---|---|
Bubble | bad for sorted or reversed input | n 2 ; n 2 |
n ; 1 |
n or 1 |
Cocktail | little performance improvement over bubble sort | n 2 |
n |
1 |
Comb | speeds up when data is nearly sorted | n 2 |
nlogn |
1 |
Gnome | simple and slow, works with one item at a time | n 2 |
n |
1 |
Heap | independent of data distribution | nlogn |
nlogn or n |
n or 1 |
Weak Heap | independent of data distribution, decreased amount of comparisons | nlogn |
nlogn or n |
n or 1 |
N-Heap | independent of data distribution, should be faster than default heap. n = 3 | nlogn |
nlogn or n |
n or 1 |
Bottom-up Heap | upgraded version of heapsort with decreased number of comparisons | nlogn |
nlogn or n |
n or 1 |
Insertion | simple, but less effective than quicksort, heapsort or merge sort | n 2 ; n 2 |
n ; 1 |
n or 1 |
Merge | independent of data distribution | nlogn |
nlogn |
n |
Odd-even | presented to be effective on processors with local interconnections | n 2 |
n |
1 |
Odd-even (Batcher) | more efficient version of odd-even sort | nlogn 2 |
logn 2 |
logn 2 |
Quick | bad for sorted or reversed input | n 2 |
nlog 2n |
n or logn |
Quick dual | enchanced version of quicksort | n 2 |
2nlnn |
n or logn |
Ksort | modified version of quicksort, faster than heap at less than 7 million elements | n 2 |
nlog 2n |
n or logn |
Selection | the least number of swaps among all the algorithms | n 2 ; n |
n 2 ; 1 |
1 |
Double selection | modified version of selection sort with more workload, but better efficiency | n 2 ; n |
n 2 ; 1 |
more than Selection |
Shellsort | it is optimization of insertion sort | n 3/2 or nlog 2 n |
nlogn |
1 |
Slow | it's slow, who would ever need it? | |||
Smooth | variant of heapsort, good for nearly sorted data | nlogn |
n |
n or 1 |
Stooge | it's a bit faster than slow sort | n 2.7095 |
n |
New algorithms implementations are planned