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:

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.

/// Bucket sort

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

/// Ref:

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], } } }


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


mod stability { use super::*; fn bucket_sort_(arr: &mut [(i32, i32)]) { bucket_sort(arr, |t| t.0 / 4); } stability_cases!(bucket_sort_); }

Recommended Readings

Comment / Suggestion Section
Point our Mistakes and Post Your Suggestions