[−][src]Crate counting_sort
An counting sort implementation for Iterator
s.
Provides the trait CountingSort
with a blanket implementation for
Iterator
s
for all types T
that implement (beyond other std
or core
traits) the here defined
TryIntoIndex
trait.
Types that implement this trait can be tried to be converted to an
usize
, i.e. an index.
This trait is already implemented for the following integer types:
This means for all Vec
s,
LinkedList
s,
slice
s or any other
of the implementors of the Iterator
trait holding one of the above integers types, counting sort can be executed.
Note: Counting sort is also implemented for BTreeSet
,
however it makes no sense to execute it there, since all elements are already in order and further sorting is completely
useless.
Example
/* * Add counting sort to your source code. * counting sort immediately works "out of the box" * for all Iterators and integers like * u8, i8, u16, i16. */ use counting_sort::CountingSort; let vec = vec![2,4,1,3]; // counting sort may fail, therefore a result is returned let sorted_vec_result = vec.iter().cnt_sort(); assert!(sorted_vec_result.is_ok()); // if successful sorted elements were copied into a Vec assert_eq!(vec![1,2,3,4], sorted_vec_result.unwrap());
Notes
 The counting sort algorithm has an
O(n+d)
(d
being the range between the minimum value and the maximum value) asymptotic runtime in comparison to anO(n*log(n))
of the Rust std library implementation ofslice.sort
 However the memory consumption is higher
 Dependent on the range
d
between the minumum value and the maximum value (d = max_value  min_value
), aVec
ofusize
's is allocated  This may fast result in GB of memory: the maximum range of
u32
is 4294967295, if usize is 4 bytes, than the memory consumption is 17179869180 bytes or approximately 16 GB (1 GB = 102410241024 bytes)  Additionally the current implementation does not consume the given iterator
 Dependent on the range
 This means the counting sort algorithm excels whenever there are a lot of elements to be sorted but the range range between minumum value and maximum value is small
 counting sort for e.g. HashSet's is suboptimal since every element exists only once in a HashSet. Counting sort excels when a lot of elements exist in the collection but the number of distinct elements is small.
 Caution: Be careful using this algorithm when the range between minumum value and maximum value is large
 An excellent illustration about the counting sort algorithm can be found here
 Wikipedia article on counting sort
Enums
CountingSortError  This enumeration is a list of all possible errors that can happen during

Traits
CountingSort  The interface for counting sort algorithm. 
TryIntoIndex  The interface for converting values into an index. 