Bucket sort
Introduction:
This is a hashing based algorithm using hash table ( or map in c++ ) data structure.
This method is used if there are many nearby decimal numbers are to be sorted.
Problem Statement:
Sort an array of n integers
Algorithm
1. we have an array of n numbers.
2. we create k buckets into which we drop then number from the array.
3. put number \(a[i]\) into bucket \( \frac{a[i]-min}{k}\)
4. sort each bucket.
5. merge all buckets into result array
Code :
// this is counting sort for all kinds of rationals
// mixture of couting and merge sort.
#include <bits/stdc++.h>
using namespace std;
void bucket_sort(float a[], int n, int k)
{
// find range by finding min and max
float max = 0, min = FLT_MAX;
for (int i = 0; i < n; i++)
{
if (max < a[i])
{
max = a[i];
}
if (min > a[i])
{
min = a[i];
}
}
float range = (max - min) / k;
if (min == max) // all elements are equal
{
return;
}
// filling buckets
vector<vector<float>> bucket(k);
for (int i = 0; i < n; i++)
{
cout << "key = " << floor((a[i] - min) / range) << "\nvalue = " << a[i] << "\n";
int key = floor((a[i] - min) / range);
bucket[key % k].push_back(a[i]);
}
// sorting each bucket
for (int i = 0; i < k; i++)
{
sort(bucket[i].begin(), bucket[i].end());
}
// copying e=result into array
int cnt = 0;
for (int i = 0; i < k; i++)
{
for (auto j : bucket[i])
{
a[cnt] = j;
cnt++;
}
}
}
int main()
{
int n, k;
cout << "Enter n: ";
cin >> n;
float a[n];
for (int i = 0; i < n; i++)
{
cin >> a[i];
}
cout << "Enter number of buckets: ";
cin >> k;
bucket_sort(a, n, k);
for (int i = 0; i < n; i++)
{
cout << a[i] << " ";
}
printf("\n");
}
Complexity Analysis :
Time Complexity : \(O(n+k)\)
Worst case : \(O(n^2)\) when almost all elements are supper close and only one bucket is supper full whereas other have very few elements.