Bucket Sort
Time Complexity
| Best | Average | Worst |
|---|---|---|
| Ω(n+k) | Θ(n+k) | O(n^2) |
Space Complexity
| Worst |
|---|
| O(n) |
Overview
Bucket sort is a popular non-comparison sorting algorithm that relies on distribution rather than comparing elements. It's useful for large sets of data that are uniformly distributed. Let's delve into the mechanics of the algorithm step-by-step using the animation input list - [1, 2, 3, 4, 5, 6, 7, 8].
Steps of Bucket Sort:
- Determine the dataset range: Get the minimum and maximum values of the dataset.
- Create empty buckets: Divide the range into equal-sized buckets and create them.
- Distribute elements to buckets: Assign each element to the appropriate bucket based on its value.
- Sort each bucket individually: Choose a sorting algorithm to sort the elements within each bucket.
- Merge the sorted buckets: Concatenate the sorted buckets to obtain the final sorted dataset.
Example with [1, 2, 3, 4, 5, 6, 7, 8]:
- Determine the dataset range: Min = 1, Max = 8.
- Create empty buckets: Divide the range into three buckets - Bucket 1 (1-3), Bucket 2 (4-6), Bucket 3 (7-8).
- Distribute elements to buckets:
- Bucket 1:
[3, 1, 2] - Bucket 2:
[5, 4, 6] - Bucket 3:
[8, 7]
- Bucket 1:
- Sort each bucket individually:
- Bucket 1:
[1, 2, 3] - Bucket 2:
[4, 5, 6] - Bucket 3:
[7, 8]
- Bucket 1:
- Merge the sorted buckets: Concatenate the sorted buckets to get the final sorted output:
[1, 2, 3, 4, 5, 6, 7, 8].
In conclusion, Bucket Sort is efficient for uniformly distributed data but less effective for skewed data. Its time complexity varies depending on the distribution of data and the internal sorting algorithm used within each bucket. Additionally, its space complexity depends on the size of the input data and the number of buckets created.
Code
It's important to note that in these examples we focus solely on Bucket Sort itself, not on the inner algorithm it uses for sorting individual buckets. Meaning - we are not having implementation of the other algorithm in the example here and use the languge's premade sorting functionality (except in the C example). If you want more details on other algorithms, please, learn them from their dedicated pages in this course.
def bucket_sort(arr, num_buckets):
min_val, max_val = min(arr), max(arr)
# Calculate the range for each bucket
bucket_size = (max_val - min_val + 1) / num_buckets
# Create empty buckets
buckets = [[] for _ in range(num_buckets)]
# Distribute elements into the appropriate buckets
for num in arr:
bucket_index = int((num - min_val) / bucket_size)
buckets[bucket_index].append(num)
# Sort elements within each bucket (with an algorithm of choice)
for i in range(num_buckets):
buckets[i].sort()
# Concatenate the sorted buckets
sorted_arr = []
for bucket in buckets:
sorted_arr.extend(bucket)
return sorted_arr
arr = [8, 5, 3, 4, 6, 1, 2, 7]
num_buckets = 3
sorted_arr = bucket_sort(arr, num_buckets)
print(sorted_arr)
function bucketSort(arr, numBuckets) {
const minVal = Math.min(...arr);
const maxVal = Math.max(...arr);
// Calculate the range for each bucket
const bucketRange = (maxVal - minVal + 1) / numBuckets;
// Create empty buckets
const buckets = Array.from({ length: numBuckets }, () => []);
// Place elements into buckets
for (const num of arr) {
const bucketIndex = Math.floor((num - minVal) / bucketRange);
buckets[bucketIndex].push(num);
}
// Sort elements within each bucket
for (let i = 0; i < numBuckets; i++) {
buckets[i].sort((a, b) => a - b);
}
// Concatenate the sorted buckets
const sortedArr = [].concat(...buckets);
return sortedArr;
}
const arr = [8, 5, 3, 4, 6, 1, 2, 7];
const numBuckets = 3;
const sortedArr = bucketSort(arr, numBuckets);
console.log(sortedArr);
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
public class BucketSort {
public static void bucketSort(int[] arr, int numBuckets) {
int minVal = Arrays.stream(arr).min().getAsInt();
int maxVal = Arrays.stream(arr).max().getAsInt();
double bucketRange = (double) (maxVal - minVal + 1) / numBuckets;
// Create empty buckets
List<List<Integer>> buckets = new ArrayList<>();
for (int i = 0; i < numBuckets; i++) {
buckets.add(new ArrayList<>());
}
// Place elements into buckets
for (int num : arr) {
int bucketIndex = (int) ((num - minVal) / bucketRange);
buckets.get(bucketIndex).add(num);
}
// Sort elements within each bucket
for (List<Integer> bucket : buckets) {
Collections.sort(bucket);
}
// Concatenate the sorted buckets to get the final sorted array
int index = 0;
for (List<Integer> bucket : buckets) {
for (int num : bucket) {
arr[index++] = num;
}
}
}
public static void main(String[] args) {
int[] arr = {8, 5, 3, 4, 6, 1, 2, 7};
int numBuckets = 3;
bucketSort(arr, numBuckets);
System.out.println(Arrays.toString(arr));
}
}
#include <stdio.h>
#include <stdlib.h>
// Node structure for linked list to store elements in a bucket and link to the next bucket
struct Node {
int data;
struct Node* next;
};
void insertionSort(struct Node** bucket) {
struct Node* sorted = NULL;
struct Node* current = *bucket;
while (current != NULL) {
struct Node* next = current->next;
if (sorted == NULL || sorted->data >= current->data) {
current->next = sorted;
sorted = current;
} else {
struct Node* search = sorted;
while (search->next != NULL && search->next->data < current->data) {
search = search->next;
}
current->next = search->next;
search->next = current;
}
current = next;
}
*bucket = sorted;
}
void bucketSort(int arr[], int size, int numBuckets) {
int minVal = arr[0];
int maxVal = arr[0];
for (int i = 1; i < size; i++) {
if (arr[i] < minVal) {
minVal = arr[i];
}
if (arr[i] > maxVal) {
maxVal = arr[i];
}
}
// Determine the range for each bucket
double bucketRange = (double)(maxVal - minVal + 1) / numBuckets;
// Create an array of linked lists to represent the buckets
struct Node* buckets[numBuckets];
for (int i = 0; i < numBuckets; i++) {
buckets[i] = NULL;
}
// Place elements into appropriate buckets
for (int i = 0; i < size; i++) {
int bucketIndex = (int)((arr[i] - minVal) / bucketRange);
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = arr[i];
newNode->next = buckets[bucketIndex];
buckets[bucketIndex] = newNode;
}
// Sort elements within each bucket (using insertion sort)
for (int i = 0; i < numBuckets; i++) {
insertionSort(&buckets[i]);
}
// Concatenate the sorted buckets to obtain the final sorted array
int index = 0;
for (int i = 0; i < numBuckets; i++) {
struct Node* current = buckets[i];
while (current != NULL) {
arr[index++] = current->data;
struct Node* temp = current;
current = current->next;
free(temp);
}
}
}
int main() {
int arr[] = {8, 5, 3, 4, 6, 1, 2, 7};
int size = sizeof(arr) / sizeof(arr[0]);
int numBuckets = 3;
bucketSort(arr, size, numBuckets);
printf("Sorted array: ");
for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
<?php
function bucketSort($arr, $bucketCount) {
if (empty($arr)) {
return $arr;
}
// Find the minimum and maximum values in the input array
$min = min($arr);
$max = max($arr);
// Calculate the range for each bucket
$bucketRange = ($max - $min + 1) / $bucketCount;
// Create empty buckets
$buckets = array_fill(0, $bucketCount, []);
// Distribute elements into buckets
foreach ($arr as $num) {
$index = floor(($num - $min) / $bucketRange);
array_push($buckets[$index], $num);
}
// Sort each bucket using PHP's built-in sort() method
foreach ($buckets as &$bucket) {
sort($bucket);
}
// Concatenate the sorted buckets to get the final sorted array
$sortedArray = array_merge(...$buckets);
return $sortedArray;
}
$inputArray = [8, 5, 3, 4, 6, 1, 2, 7];
$bucketCount = 3;
$sortedArray = bucketSort($inputArray, $bucketCount);
print_r($sortedArray);
?>