   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