Trait CountingSort

pub trait CountingSort<'a, T>
where
    T: Ord + Copy + TryIntoIndex + 'a,
    Self: Clone + Sized + Iterator<Item = &'a T>,
{
    // Provided methods
    fn cnt_sort(self) -> Result<Vec<T>, CountingSortError> { ... }
    fn cnt_sort_min_max(
        self,
        min_value: &T,
        max_value: &T,
    ) -> Result<Vec<T>, CountingSortError> { ... }
}

The interface for counting sort algorithm.

Interface provides blanket implementation of all collections that implement the Iterator trait. These collections must also implement Clone, since the iterator is iterated several times, and Sized. If your collection does provide these, you can simply implement this trait “empty”:

impl CountingSort for YourType {}

However the intention of this trait is to provide an implementation of all collections that implement the Iterator trait like Vec.

The types which are held by the collections must implement Ord in order to sort the elements, as well as Copy, since the elements are copied during the count phase as well as the re-order phase. Finally the type must implement the in this crate defined TryIntoIndex trait.

Provided Methods

fn cnt_sort(self) -> Result<Vec<T>, CountingSortError>

Sorts the elements in the Iterator with the counting sort algorithm.

This sort is stable (i.e., does not reorder equal elements) and O(n + d) worst-case, where d is the distance between the maximum and minimum element in the collection.

Memory usage is O(n + d) as well, since all elements of the collection are copied into a new Vec and the frequency of all elements in the collection are counted in a Vec of size d.

Caution: If distance d is large, than memory consumption is large and you process may run out of memory.

This method iterates Iterator in the beginning to identify the maximum and mimumum value in order to identify the distance d. This means the runtime is longer due to this additional n iterations and the checks needed to identify the minimum and maximum values.

Example

use counting_sort::CountingSort;

let slice = [20000,-1000,17,333];
let sorted_vec_result = slice.iter().cnt_sort();

assert_eq!(vec![-1000,17,333,20000], sorted_vec_result.unwrap());

Errors

• CountingSortError::IntoIndexFailed when converting into an index fails, this could happen if the distance d is larger than usize::max_value
• CountingSortError::IteratorEmpty when the iterator is empty (and there is nothing to sort)
• CountingSortError::SortingUnnecessary] when the minimum value is equal to the maximum value, this means all values are essentially equal and no sorting is necessary

fn cnt_sort_min_max( self, min_value: &T, max_value: &T, ) -> Result<Vec<T>, CountingSortError>

Sorts the elements in the Iterator with the counting sort algorithm given the minimum and maximum element of the collection.

This sort is stable (i.e., does not reorder equal elements) and O(n + d) worst-case, where d is the distance between the maximum and minimum element in the collection.

Memory usage is O(n + d) as well, since all elements of the collection are copied into a new Vec and the frequency of all elements in the collection are counted in a Vec of size d.

Caution: If distance d is large, than memory consumption is large and you process may run out of memory.

This method uses the given minimum and maximum element and therefore does not need to iterate the iterator to identify the minimum and maximum element.

Caution: If any element is either larger than the given maximum value or smaller than the given minimum value, the method will return with an error. Only use this method if you know these values.

Example

use std::collections::LinkedList;
use counting_sort::CountingSort;

let mut list = LinkedList::new();
list.push_back(1000001);
list.push_back(1000003);
list.push_back(1000002);
list.push_back(1000000);

let sorted_vec_result = list.iter().cnt_sort_min_max(&1000000, &1000003);

assert_eq!(vec![1000000, 1000001, 1000002, 1000003], sorted_vec_result.unwrap());

// minimum value incorrect
let error = list.iter().cnt_sort_min_max(&1000001, &1000003);
assert!(error.is_err());

Errors

• CountingSortError::IntoIndexFailed when converting into an index fails, this could happen if the distance d is larger than usize::max_value
• CountingSortError::SortingUnnecessary] when the minimum value is equal to the maximum value, this means all values are essentially equal and no sorting is necessary
• CountingSortError::MinValueLargerMaxValue] when the given minimum value is larger than the given maximum value
• CountingSortError::IndexOutOfBounds] when the given maximum value is smaller than the actual maximum value of the collection

Dyn Compatibility

This trait is not dyn compatible.

In older versions of Rust, dyn compatibility was called "object safety", so this trait is not object safe.

Implementors

impl<'a, T, ITER> CountingSort<'a, T> for ITER

where T: Ord + Copy + TryIntoIndex + 'a, ITER: Sized + Iterator<Item = &'a T> + Clone,