Algorithm
Bucket sort is a sorting algorithm that works by distributing the elements of an array into a number of buckets or bins. Each bucket is then sorted individually, either using a different sorting algorithm or by recursively applying the bucket sort algorithm. Finally, the sorted elements from all the buckets are concatenated to obtain the fully sorted array.
Here's a basic overview of how the bucket sort algorithm works:
-
Bucket Creation: Create an array of empty buckets, where the number of buckets is determined by the range of the input elements.
-
Distribution: Iterate through the input array and distribute each element into the appropriate bucket based on some criteria. This criteria could be as simple as assigning each element to a bucket corresponding to its integer value, or it could involve more complex calculations.
-
Sorting: Sort each individual bucket. This step can be performed using any sorting algorithm, such as insertion sort, quicksort, or mergesort. If the range of input values is small, a simple sorting algorithm may be sufficient.
-
Concatenation: Concatenate the sorted buckets to obtain the final sorted array.
Bucket sort is generally efficient when the input is uniformly distributed across a range. However, its performance can degrade when the input values are not uniformly distributed, as it may result in a few buckets with a large number of elements.
Code Examples
#1 Bucket Sort implement in Python
Code -
Python Programming
def bucket_sort(arr):
"""
Bucket Sort implementation in Python.
Parameters:
- arr: The input list to be sorted.
Returns:
- Sorted list.
"""
# Find the maximum and minimum values in the input array
max_val = max(arr)
min_val = min(arr)
# Calculate the range of each bucket
bucket_range = (max_val - min_val) / len(arr)
# Create empty buckets
buckets = [[] for _ in range(len(arr))]
# Distribute elements into buckets
for i in range(len(arr)):
index = int((arr[i] - min_val) / bucket_range)
buckets[index].append(arr[i])
# Sort each bucket (using another sorting algorithm or recursion)
for i in range(len(arr)):
buckets[i] = sorted(buckets[i])
# Concatenate the sorted buckets to get the final sorted array
result = []
for bucket in buckets:
result.extend(bucket)
return result
# Example usage:
input_array = [4, 2, 7, 1, 9, 10, 5]
sorted_array = bucket_sort(input_array)
print("Input Array:", input_array)
print("Sorted Array:", sorted_array)
#2 Bucket Sort implement in Java
Code -
Java Programming
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class BucketSort {
public static void bucketSort(float[] arr) {
if (arr == null || arr.length == 0) {
return;
}
int n = arr.length;
List < Float>[] buckets = new ArrayList[n];
// Create empty buckets
for (int i = 0; i < n; i++) {
buckets[i] = new ArrayList<>();
}
// Put elements into buckets
for (int i = 0; i < n; i++) {
int bucketIndex = (int) (n * arr[i]);
buckets[bucketIndex].add(arr[i]);
}
// Sort each bucket
for (int i = 0; i < n; i++) {
Collections.sort(buckets[i]);
}
// Concatenate buckets to get the sorted array
int index = 0;
for (int i = 0; i < n; i++) {
for (float value : buckets[i]) {
arr[index++] = value;
}
}
}
public static void main(String[] args) {
float[] arr = {0.42f, 0.32f, 0.33f, 0.52f, 0.37f, 0.47f, 0.51f};
System.out.println("Original Array:");
printArray(arr);
bucketSort(arr);
System.out.println("\nSorted Array:");
printArray(arr);
}
public static void printArray(float[] arr) {
for (float value : arr) {
System.out.print(value + " ");
}
System.out.println();
}
}
#3 Bucket Sort implement in C
Code -
C Programming
#include <stdio.h>
#include <stdlib.h>
// Function to perform insertion sort on a bucket
void insertionSort(int arr[], int n) {
int i, key, j;
for (i = 1; i < n; i++) {
key = arr[i];
j = i - 1;
// Move elements of arr[0..i-1] that are greater than key to one position ahead of their current position
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
// Function to perform bucket sort
void bucketSort(int arr[], int n) {
// Find the maximum and minimum values in the array
int max_val = arr[0];
int min_val = arr[0];
for (int i = 1; i < n; i++) {
if (arr[i] > max_val) {
max_val = arr[i];
}
if (arr[i] < min_val) {
min_val = arr[i];
}
}
// Create buckets
int num_buckets = max_val - min_val + 1;
int **buckets = (int **)malloc(num_buckets * sizeof(int *));
for (int i = 0; i < num_buckets; i++) {
buckets[i] = (int *)malloc(n * sizeof(int));
}
// Initialize buckets
for (int i = 0; i < num_buckets; i++) {
for (int j = 0; j < n; j++) {
buckets[i][j] = 0;
}
}
// Distribute elements into buckets
for (int i = 0; i < n; i++) {
int index = arr[i] - min_val;
buckets[index][i] = arr[i];
}
// Sort each bucket using insertion sort
for (int i = 0; i < num_buckets; i++) {
insertionSort(buckets[i], n);
}
// Concatenate the sorted buckets to get the sorted array
int index = 0;
for (int i = 0; i < num_buckets; i++) {
for (int j = 0; j < n; j++) {
if (buckets[i][j] != 0) {
arr[index++] = buckets[i][j];
}
}
}
// Free memory allocated for buckets
for (int i = 0; i < num_buckets; i++) {
free(buckets[i]);
}
free(buckets);
}
// Function to print an array
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
// Driver program
int main() {
int arr[] = {64, 25, 12, 22, 11};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Original array: ");
printArray(arr, n);
bucketSort(arr, n);
printf("Sorted array: ");
printArray(arr, n);
return 0;
}
#4 Bucket Sort implement in C++
Code -
C++ Programming
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// Function to perform bucket sort
void bucketSort(vector < float>& arr) {
int n = arr.size();
// Create empty buckets
vector<vector<float>> buckets(n);
// Put elements into the buckets
for (int i = 0; i < n; ++i) {
int bucketIndex = n * arr[i];
buckets[bucketIndex].push_back(arr[i]);
}
// Sort individual buckets
for (int i = 0; i < n; ++i) {
sort(buckets[i].begin(), buckets[i].end());
}
// Concatenate the sorted buckets to get the final sorted array
int index = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < buckets[i].size(); ++j) {
arr[index++] = buckets[i][j];
}
}
}
// Function to print an array
void printArray(const vector < float>& arr) {
for (float value : arr) {
cout << value << " ";
}
cout << endl;
}
int main() {
// Example usage
vector < float> arr = {0.42, 0.32, 0.33, 0.52, 0.37, 0.47, 0.51};
cout << "Original array: ";
printArray(arr);
// Perform bucket sort
bucketSort(arr);
cout << "Sorted array: ";
printArray(arr);
return 0;
}
Demonstration
Bucket Sort Data Structure and Algorithm