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