Bucket Sort

Definition

Definition

Bucket Sort is a comparison sort algorithm that works by distributing the elements of an array into a number of buckets. Each bucket is then sorted individually, either using a different sorting algorithm or by recursively applying the bucket sort algorithm

Explanation

The Bucket Sort algorithm starts by dividing the input data's range into equally-sized buckets. Then, it distributes each element from the input array into its corresponding bucket based on a predefined function. Subsequently, it sorts each bucket separately, employing either a recursive application of Bucket Sort or another sorting algorithm. Finally, it concatenates the sorted buckets to produce the final sorted array

Guidance

• Determine the range of the input data
• Create an array of empty buckets
• Iterate through the input array, placing each element into its corresponding bucket
• Sort each bucket, either by recursively applying bucket sort or using another sorting algorithm
• Concatenate the sorted buckets into a single sorted array

Tips

• choose an appropriate function to map elements to buckets, ensuring even distribution
• consider the distribution of input data when choosing the number and size of buckets
• use an efficient sorting algorithm to sort individual buckets
• be mindful of the memory usage when working with large datasets, as bucket sort can require additional space for the buckets

Practice

Practice

bucketSort(arr):
  n = length(arr)
  create n empty buckets
  max_val = maximum value in arr
  min_val = minimum value in arr
  range = (max_val - min_val) / n

  // Scatter elements into buckets
  for each element in arr:
    bucket_index = (element - min_val) / range
    append element to bucket[bucket_index]

  // Sort each bucket
  for each bucket in buckets:
    sort(bucket)

  // Concatenate sorted buckets
  sorted_arr = []
  for each bucket in buckets:
    append bucket to sorted_arr

  return sorted_arr

Solution

package main

import (
    "sort"
)

func bucketSort(arr []float64) {
    if len(arr) <= 1 {
        return
    }

    n := len(arr)
    buckets := make([][]float64, n)

    for _, v := range arr {
        index := int(v * float64(n))
        buckets[index] = append(buckets[index], v)
    }

    for i := 0; i < n; i++ {
        sort.Float64s(buckets[i])
    }

    k := 0
    for i := 0; i < n; i++ {
        for j := 0; j < len(buckets[i]); j++ {
            arr[k] = buckets[i][j]
            k++
        }
    }
}

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class BucketSort {

  public static void bucketSort(double[] arr) {
    if (arr.length <= 1) {
      return;
    }

    int n = arr.length;
    List<Double>[] buckets = new ArrayList[n];

    for (int i = 0; i < n; i++) {
      buckets[i] = new ArrayList<>();
    }

    for (double v : arr) {
      int index = (int) (v * n);
      buckets[index].add(v);
    }

    for (int i = 0; i < n; i++) {
      Collections.sort(buckets[i]);
    }

    int k = 0;
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < buckets[i].size(); j++) {
        arr[k] = buckets[i].get(j);
        k++;
      }
    }
  }
}

function bucketSort(arr) {
  if (arr.length <= 1) {
    return arr;
  }

  const n = arr.length;
  const buckets = Array.from({ length: n }, () => []);

  for (let i = 0; i < n; i++) {
    const index = Math.floor(arr[i] * n);
    buckets[index].push(arr[i]);
  }

  for (let i = 0; i < n; i++) {
    buckets[i].sort((a, b) => a - b);
  }

  let k = 0;
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < buckets[i].length; j++) {
      arr[k] = buckets[i][j];
      k++;
    }
  }
}

fun bucketSort(arr: DoubleArray) {
    if (arr.size <= 1) {
        return
    }

    val n = arr.size
    val buckets = Array(n) { mutableListOf<Double>() }

    for (v in arr) {
        val index = (v * n).toInt()
        buckets[index].add(v)
    }

    for (i in 0 until n) {
        buckets[i].sort()
    }

    var k = 0
    for (i in 0 until n) {
        for (j in 0 until buckets[i].size) {
            arr[k] = buckets[i][j]
            k++
        }
    }
}

def bucket_sort(arr):
    if len(arr) <= 1:
        return

    n = len(arr)
    buckets = [[] for _ in range(n)]

    for v in arr:
        index = int(v * n)
        buckets[index].append(v)

    for bucket in buckets:
        bucket.sort()

    k = 0
    for i in range(n):
        for j in range(len(buckets[i])):
            arr[k] = buckets[i][j]
            k += 1

fn bucket_sort(arr: &mut [f64]) {
    if arr.len() <= 1 {
        return;
    }

    let n = arr.len();
    let mut buckets: Vec<Vec<f64>> = vec![vec![]; n];

    for &v in arr.iter() {
        let index = (v * n as f64) as usize;
        buckets[index].push(v);
    }

    for bucket in buckets.iter_mut() {
        bucket.sort_by(|a, b| a.partial_cmp(b).unwrap());
    }

    let mut k = 0;
    for bucket in buckets.iter() {
        for &v in bucket.iter() {
            arr[k] = v;
            k += 1;
        }
    }
}

function bucketSort(arr: number[]): void {
  if (arr.length <= 1) {
    return;
  }

  const n = arr.length;
  const buckets: number[][] = Array.from({ length: n }, () => []);

  for (const v of arr) {
    const index = Math.floor(v * n);
    buckets[index].push(v);
  }

  for (const bucket of buckets) {
    bucket.sort((a, b) => a - b);
  }

  let k = 0;
  for (const bucket of buckets) {
    for (const v of bucket) {
      arr[k] = v;
      k++;
    }
  }
}