Create counting-sort.rs

i-vishi · web-flow · commit 72bb7847d63b · 2020-10-01T09:29:00.000+05:30
diff --git a/Sorting/Counting Sort/Rust/counting-sort.rs b/Sorting/Counting Sort/Rust/counting-sort.rs
@@ -0,0 +1,63 @@
+/// 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_);
+}
