Table of content

Counting sort in Rust

Counting sort is a special integer sorting method that is considered a special case of Bucket sort . The principle is to count the number of occurrences of each key value within a known integer range and save it with an additional array (Count array). Finally, the element value of Count array is used as the new index of the sorted data.

The basic characteristics of Counting sort are as follows:
  • Non-in-place sorting: extra costing, non-fixed space to sort.
  • Stable sorting: Elements of the same key value, the relative position does not change after sorting.
  • Integer sort: The integer is used as the sorted key value.
  • Distributive sorting: Sorting by analyzing key-value distributions without comparing them. Linear execution time is available in specific situations.
  • Line type execution time: When the input data amount n is close to the difference between the upper and lower bounds of the known range, the execution time is close to the line type ( O(n) )
  • Expected distribution: The expected input data is an integer (eg, 0 to k) that falls within a known range.
  • Scope: Only applicable to small range integers (large space requirements).
Steps
  • Count occurrence : Calculates the number of occurrences of each key.
  • Prefix sum as start index : Calculates the prefix and (Prefix sum) as the start index of the element.
  • Copy output : Use the prefix and the second step to traverse the input data to obtain the index after the element is sorted.
/// Counting sort

/// * `arr` - Collection of value to be sorted in place.

/// * `min` - Lower bound of the integer range.

/// * `max` - Upper bound of the integer range.

/// * `key` - Function extracting key witn the integer range from elements.

pub fn counting_sort<F, T>(arr: &mut [T], min: usize, max: usize, key: F)
where F: Fn(&T) -> usize, T: Clone,
{ let mut prefix_sums = { // 1. Initialize the count array with default value 0. let len = max - min; let mut count_arr = Vec::with_capacity(len); count_arr.resize(len, 0);

// 2. Scan elements to collect counts. for value in arr.iter() { count_arr[key(value)] += 1; }

// 3. Calculate prefix sum. count_arr .into_iter() .scan(0, |state, x| { *state += x; Some(*state - x) }) .collect::<Vec<usize>>() };

// 4. Use prefix sum as index position of output element. for value in arr.to_vec().iter() { let index = key(value); arr[prefix_sums[index]] = value.clone(); prefix_sums[index] += 1; } }

#[cfg(test)]

mod base { use super::*; fn counting_sort_(arr: &mut [i32]) { counting_sort(arr, 1, 10, |int| *int as usize); } base_cases!(counting_sort_); }

#[cfg(test)]

mod stability { use super::*; fn counting_sort_(arr: &mut [(i32, i32)]) { counting_sort(arr, 1, 10, |t| t.0 as usize); } stability_cases!(counting_sort_); }

Comment / Suggestion Section
Point our Mistakes and Post Your Suggestions