Crate counting_sort

Source
Expand description

An counting sort implementation for Iterators.

Provides the trait CountingSort with a blanket implementation for Iterators 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 Vecs, LinkedLists, slices 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 an O(n*log(n)) of the Rust std library implementation of core::slice::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), a Vec of usize’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
  • 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 sub-optimal 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§

Traits§