## 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:

1. Bucket Creation: Create an array of empty buckets, where the number of buckets is determined by the range of the input elements.

2. 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.

3. 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.

4. 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)
``````
Copy The Code &

### #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]);
}

// 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();
}
}
``````
Copy The Code &

### #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;
}
``````
Copy The Code &

### #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;
}
``````
Copy The Code &