- Notifications
You must be signed in to change notification settings - Fork2
Sorting algorithms implemented in Rust
License
NotificationsYou must be signed in to change notification settings
flakusha/sorting_rs
Folders and files
| Name | Name | Last commit message | Last commit date | |
|---|---|---|---|---|
Repository files navigation
Sorting algorithms implemented in Rust.
- Add this dependency and please consider it's version into your Cargo.toml:
[dependencies]sorting_rs ="1.2.0"
- Use available sorting algorithms in your Rust code:
use sorting_rs::*;
- API for every sorting function is pretty the same: you just have to passmutable reference:
&mut [T], orvec![T, T, T, ...].Tshould havePartialOrdtrait, sometimes you may needCopyorClonetraits, thoughall implementations try to avoid this kind of additional requirements. - For more information about origin of algorithms and implementation details,please read modules documentation.Wikipedia is nice startingpoint too.
| 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 ornlogn2 | 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
About
Sorting algorithms implemented in Rust
Topics
Resources
License
Uh oh!
There was an error while loading.Please reload this page.
Stars
Watchers
Forks
Packages0
No packages published
Uh oh!
There was an error while loading.Please reload this page.