   Table of content

## Bucket sort in Rust

Bucket sort is a non-comparative sort. The principle is to create some buckets, each of which corresponds to a data interval, and the data to be sorted is allocated to different buckets, and the buckets are internally sorted.

Since it is not a sort of sorting, using Bucket sort requires knowing the scope and distribution of the data in advance to determine the interval corresponding to the bucket.

##### The basic characteristics of Bucket sort are as follows:
• Also known as bin sort.
• Stable sorting : Elements of the same key value, the relative position does not change after sorting.
• Distributive sorting : Sorting by analyzing key-value distributions without comparing them. Linear execution time is available in specific situations.
• Expected distribution : The data is evenly distributed .
##### step

Suppose you want to sort an array of \$n \$ elements whose values are scattered evenly within a known expected range , such as 1 to 100.

• Create buckets : Create an array of \$k \$ buckets. Each bucket corresponds to a certain range of the expected range , such as the first bucket is placed 1 to 10, and the second is placed 11 to 20.
• Scatter : Put each element into the corresponding bucket according to this value.
• Inner sort : Sort all non-empty buckets.
• Gather : Visit all the buckets in sequence and put the elements in the bucket back into the original array.

``````/// Bucket sort

/// * `arr` - Collection of value to be sorted in place.
/// * `hasher` - Function hashing to map elements to correspoding buckets.

/// Ref: https://codereview.stackexchange.com/a/145124

pub fn bucket_sort<H, F, T>(arr: &mut [T], hasher: F)

where
H: Ord,
F: Fn(&T) -> H,
T: Ord + Clone,
{
// 1. Create buckets.
let mut buckets: Vec<Bucket<H, T>> = Vec::new();

// 2. Iterate all elements.
for value in arr.iter() {
// 2.1 Create hasher mapping to certain bucket.
let hash = hasher(&value);

// 2.2 Search if the bucket with same hash exists.
let value = value.clone();
match buckets.binary_search_by(|bucket| bucket.hash.cmp(&hash)) {
// If exists, push the value to the bucket.
Ok(index) => buckets[index].values.push(value),
// If none, create and new bucket and insert value in.
Err(index) => buckets.insert(index, Bucket::new(hash, value)),
}
}

// 3. Iterate all buckets and flatten their internal collections.
let ret = buckets
.into_iter()
.flat_map(|mut bucket| {
bucket.values.sort(); // We use built-in sorting here.
bucket.values
})
.collect::<Vec<T>>();

// 4. Clone back to original array.
arr.clone_from_slice(&ret);
}

/// Bucket to store elements.

struct Bucket<H, T> {
hash: H,
values: Vec<T>,
}

impl<H, T> Bucket<H, T> {
/// Create a new bucket and insert its first value.
///
/// * `hash` - Hash value generated by hasher param of `bucket_sort`.
/// * `value` - Value to be put in the bucket.
pub fn new(hash: H, value: T) -> Bucket<H, T> {
Bucket {
hash,
values: vec![value],
}
}
}

#[cfg(test)]

mod base {
use super::*;
fn bucket_sort_(arr: &mut [i32]) {
bucket_sort(arr, |int| int / 4);
}
base_cases!(bucket_sort_);
}

#[cfg(test)]

mod stability {
use super::*;
fn bucket_sort_(arr: &mut [(i32, i32)]) {
bucket_sort(arr, |t| t.0 / 4);
}
stability_cases!(bucket_sort_);
}``````
Comment / Suggestion Section
Point our Mistakes and Post Your Suggestions

## Subscribe to See Videos

Subscribe to my Youtube channel for new videos : Subscribe Now