3 unstable releases
0.2.0 | Mar 9, 2024 |
---|---|
0.1.1 | Feb 28, 2024 |
0.1.0 | Feb 28, 2024 |
#124 in #sorting
28KB
694 lines
Ergonomic stooge sort implementation.
Implements 3 methods for stooge-sorting [T]
/Vec<T>
:
.stooge_sort()
(forOrd
types).stooge_sort_by()
(for everything else; bring your own comparator function!).stooge_sort_by_key()
(also for everything else)
Usage
Add the following to your Cargo.toml
,
[dependencies]
stoogesort = "0.2.0"
and import the Stooge
extension trait.
use stoogesort::Stooge;
Usage should be identical to slice::sort()
and
slice::sort_by()
.
Examples
Sorting an Ord
type using
.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
type using
.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::<i64>().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
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:
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):
extern crate stooge;
fn main() {
let mut v: Vec<i32> = 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.
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.
At the same time, it also implements these sorting algorithms
on [T]
where T: PartialOrd
, which I'll now describe my problem with:
PartialOrd
's .lt()
(used by the <
operator), .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.
Thus, the NaNInt
type can only be PartialOrd
. As such:
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
.
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
on sort()
and the distinct lack
of one on sort_by()
. Also notice the bound Ord
on the
type parameter K
in sort_by_key()
.
The standard library is protecting you from an attempt to naively sort
PartialOrd
s by making you gaze upon the Wrongness that is
.sort_by(|a, b| a.partial_cmp(b).unwrap())
in the 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.
Dependencies
~245–530KB