counting sort Algorithm
Bucket sort may be used for many of the same tasks as counting sort, with a like time analysis; however, compared to counting sort, bucket sort necessitates associated lists, dynamic arrays or a large amount of preallocated memory to keep the sets of items within each bucket, whereas counting sort instead stores a individual number (the count of items) per bucket.
Because counting sort uses key values as indexes into an array, it is not a comparison sort, and the Ω(n log N) Although radix sorting itself dates back far longer,
counting sort, and its application to radix sorting, were both invented by Harold H. Seward in 1954.
/// In place counting sort for collections of u32
/// O(n + maxval) in time, where maxval is the biggest value an input can possibly take
/// O(maxval) in memory
/// u32 is chosen arbitrarly, a counting sort probably should'nt be used on data that requires bigger types.
pub fn counting_sort(arr: &mut [u32], maxval: usize) {
let mut occurences: Vec<usize> = vec![0; maxval + 1];
for &data in arr.iter() {
occurences[data as usize] += 1;
}
let mut i = 0;
for (data, &number) in occurences.iter().enumerate() {
for _ in 0..number {
arr[i] = data as u32;
i += 1;
}
}
}
use std::ops::AddAssign;
/// Generic implementation of a counting sort for all usigned types
pub fn generic_counting_sort<T: Into<u64> + From<u8> + AddAssign + Copy>(
arr: &mut [T],
maxval: usize,
) {
let mut occurences: Vec<usize> = vec![0; maxval + 1];
for &data in arr.iter() {
occurences[data.into() as usize] += 1;
}
// Current index in output array
let mut i = 0;
// current data point, necessary to be type-safe
let mut data = T::from(0);
// This will iterate from 0 to the largest data point in `arr`
// `number` contains the occurances of the data point `data`
for &number in occurences.iter() {
for _ in 0..number {
arr[i] = data;
i += 1;
}
data += T::from(1);
}
}
#[cfg(test)]
mod test {
use super::super::is_sorted;
use super::*;
#[test]
fn counting_sort_descending() {
let mut ve1 = vec![6, 5, 4, 3, 2, 1];
counting_sort(&mut ve1, 6);
assert!(is_sorted(&ve1));
}
#[test]
fn counting_sort_pre_sorted() {
let mut ve2 = vec![1, 2, 3, 4, 5, 6];
counting_sort(&mut ve2, 6);
assert!(is_sorted(&ve2));
}
#[test]
fn generic_counting_sort() {
let mut ve1: Vec<u8> = vec![100, 30, 60, 10, 20, 120, 1];
super::generic_counting_sort(&mut ve1, 120);
assert!(is_sorted(&ve1));
}
#[test]
fn presorted_u64_counting_sort() {
let mut ve2: Vec<u64> = vec![1, 2, 3, 4, 5, 6];
super::generic_counting_sort(&mut ve2, 6);
assert!(is_sorted(&ve2));
}
}
