bucket Sort Algorithm
The bucket sort algorithm is a sorting technique that works by distributing the elements of an array into a number of "buckets" based on their values, followed by sorting each bucket individually. This method is particularly useful for sorting data that is uniformly distributed over a range of values, as it can provide efficient sorting with minimal comparisons. The main idea behind bucket sort is to divide the data set into a series of smaller, more manageable groups, which can be sorted independently, and then combined to form the final sorted result.
To implement the bucket sort algorithm, first, determine the range of the input data and the number of buckets to be used. Each bucket represents a range of values within the overall range of the data. Then, iterate through the input array, placing each element into the appropriate bucket based on its value. Once all elements have been added to their respective buckets, sort each bucket individually using any suitable sorting algorithm, such as insertion sort or quick sort. Finally, concatenate the sorted buckets together to obtain the fully sorted array. The efficiency of the bucket sort algorithm largely depends on the distribution of the input data and the choice of the sorting algorithm used for sorting individual buckets.
// C++ program to sort an array using bucket sort
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
// Function to sort arr[] of size n using bucket sort
void bucketSort(float arr[], int n)
{
// 1) Create n empty buckets
vector<float> b[n];
// 2) Put array elements in different buckets
for (int i = 0; i < n; i++)
{
int bi = n * arr[i]; // Index in bucket
b[bi].push_back(arr[i]);
}
// 3) Sort individual buckets
for (int i = 0; i < n; i++)
sort(b[i].begin(), b[i].end());
// 4) Concatenate all buckets into arr[]
int index = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < b[i].size(); j++)
arr[index++] = b[i][j];
}
/* Driver program to test above funtion */
int main()
{
float arr[] = {0.897, 0.565, 0.656, 0.1234, 0.665, 0.3434};
int n = sizeof(arr) / sizeof(arr[0]);
bucketSort(arr, n);
cout << "Sorted array is \n";
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
return 0;
}
