Ergonomic stooge sort implementation. Implements 3 methods for stooge-sorting [`[T]`](array)/[`Vec`](std::vec::Vec): * [`.stooge_sort()`](Stooge::stooge_sort) (for [`Ord`](std::cmp) types) * [`.stooge_sort_by()`](Stooge::stooge_sort_by) (for everything else; bring your own comparator function!) * [`.stooge_sort_by_key()`](Stooge::stooge_sort_by_key) (also for everything else) # Usage Add the following to your `Cargo.toml`, ```text [dependencies] stoogesort = "0.2.0" ``` and import the [`Stooge`] extension trait. ``` use stoogesort::Stooge; ``` Usage should be identical to [`slice::sort()`](slice::sort) and [`slice::sort_by()`](slice::sort_by). # Examples Sorting an [`Ord`](std::cmp::Ord) type using [`.stooge_sort()`](Stooge::stooge_sort): ``` use stoogesort::Stooge; let mut nums = [3, 2, 1, -5]; nums.stooge_sort(); assert_eq!(nums, [-5, 1, 2, 3]); ``` Sorting a [`PartialOrd`](std::cmp::PartialOrd) type using [`.stooge_sort_by()`](Stooge::stooge_sort_by) ``` use stoogesort::Stooge; let mut floats = [0.1, 0.0, 1.0, -1.6]; floats.stooge_sort_by(|a, b| a.partial_cmp(b).unwrap()); assert_eq!(floats, [-1.6, 0.0, 0.1, 1.0]); ``` Sorting strings tagged with numbers at the end: ``` use stoogesort::Stooge; let mut s = [ "foo_1", "bar_0", "quux_2" ]; s.stooge_sort_by_key(|t| t.split('_').last().unwrap().parse::().unwrap()); assert_eq!(s, [ "bar_0", "foo_1", "quux_2" ]); ``` # Acknowledgements * The Rust project code and docs (license in `LICENSE.rust`) I blatantly plagiarized * The pseudocode in the [Wikipedia article for stooge sort](https://en.wikipedia.org/wiki/Stooge_sort) # Prior Art (or: "Why do it again?") It's funny to implement slow algorithms in a "blazing-fast" language! Also, I wanted to learn how to write a library (and one with a cromulent, natural interface), use traits, and publish to crates.io. To my knowledge, 2 stooge sort implementations (not counting crates that promise to include stooge sort) already exist: * [`stooge`](https://github.com/tydus101/rust_stooge_sort) * [`sorting_rs`](https://github.com/flakusha/sorting_rs) At risk of sounding rude, I don't like them very much. ## `stooge` `stooge` can be forgiven here, as it was explicitly written as a learning project, but it's illustrative. Pulled from that crate's README (in all its Rust 2015 glory): ```ignore extern crate stooge; fn main() { let mut v: Vec = vec![1, 5, 4, 3]; stooge::sort(&mut v); return v; // [1, 3, 4, 5] } ``` The name is clever, but not particularly conducive to production use -- were this a serious project, I would have to write either `stooge::sort(v)` or `sort(v)` instead of `v.sort()`. It's backwards. The `sort()` function is also implemented on `[T: PartialOrd]`, which I find unsatisfying. More on that on the next subsection. ## `sorting_rs` This one is theoretically is intended for 'production' use (judging by the version number), or at least for dissection. However, its interface is still... wonky. ```ignore let mut vec = vec![5,3,2,4]; sorting_rs::oddeven_sort(&mut vec); assert_eq!(vec, &[2,3,4,5]); ``` There is [an obvious receiver here, it should've been a method](https://rust-lang.github.io/api-guidelines/predictability.html#c-method). At the same time, it also implements these sorting algorithms on `[T]` where `T: PartialOrd`, which I'll now describe my problem with: [`PartialOrd`](std::cmp::PartialOrd)'s [`.lt()`](std::cmp::PartialOrd::lt) (used by the `<` operator), [`.gt()`](std::cmp::PartialOrd::gt) (used by `>`), and its "-or-equal-to" variants are not mathematically airtight. Suppose there's an integer type, that, for some reason, has a NaN value. I'll call it `NaNInt`. NaN is not a number -- it is nonsense to use NaN in a comparison. Since there is at least one pair of `NaNInts` for which comparison is impossible or nonsensical, they form a [partial order](https://en.wikipedia.org/wiki/Partially_ordered_set). Thus, the `NaNInt` type can only be `PartialOrd`. As such: ```ignore use std::cmp::Ordering; let a = NaNInt::from(1); let b = NaNInt::from(2); let c = NaNInt::NaN; assert_eq!(a.partial_cmp(b), Some(Ordering::Less)); assert_eq!(a.partial_cmp(c), None); assert_eq!(c.partial_cmp(c), None); ``` Okay, we're good. This makes sense. Now, let's consider what happens when we use `.lt()` and `.gt()` on a NaN, keeping in mind that these methods return a [`bool`], not an [`Option`]. ```ignore let a = NaNInt::from(1); let b = NaNInt::from(2); let c = NaNInt::NaN; assert_eq!(c > a, false); assert_eq!(c < a, false); assert_eq!(b < c, false); assert_eq!(b > c, false); assert_eq!(c > c, false); assert_eq!(c < c, false); ``` That's right! It's nonsense. A NaN is never less than or greater than anything else, including itself. This causes sorting on `[T: PartialOrd]` to be unspecified if it contains incomparable pairs of elements. Indeed, this is documented (rather indirectly) in [`slice::sort_by()`]. > The comparator function must define a total ordering for the elements in > the slice. If the ordering is not total, the order of the elements is unspecified. For this reason, the standard library instead provides 3 methods (+ variants for unstable (not that stooge sort is stable) and cached) for sorting slices. They are: * [`slice::sort()`] * [`slice::sort_by()`] * [`slice::sort_by_key()`] Notice the bound [`Ord`](std::cmp::Ord) on [`sort()`](slice::sort) and the distinct lack of one on [`sort_by()`](slice::sort_by). Also notice the bound [`Ord`](std::cmp::Ord) on the type parameter `K` in [`sort_by_key()`](slice::sort_by_key). The standard library is protecting you from an attempt to naively sort [`PartialOrd`](std::cmp::PartialOrd)s by making you gaze upon the Wrongness that is `.sort_by(|a, b| a.partial_cmp(b).unwrap())` in the [`sort_by()`](slice::sort_by) example. As such, I've taken the liberty of imitating the standard library in this library. It also makes implementation easy, since I can just copy function signatures and even the code itself at times.