# Bucket Sort

Pseudocode:

```bucketSort(arr[], n)
1) Create n empty buckets (Or lists).
2) Do following for every array element arr[i].
.......a) Insert arr[i] into bucket[n*array[i]]
3) Sort individual buckets using insertion sort.
4) Concatenate all sorted buckets.```

Implemented Code:

```#include<bits/stdc++.h>
using namespace std;
void bucketSort(float A[],int n){
//1. create an n empty buckets
vector<float> b[n];
//2. Put array elements in different buckets
for(int i=0;i<n;i++)
{
int bi=n*A[i]; //index in bucket
b[bi].push_back(A[i]);
}
//3. Sort individual buckets
for(int i=0;i<n;i++)
{
sort(b[i].begin(),b[i].end());
}
//4. concatenate all bucket into an array
int index=0;
for(int i=0;i<n;i++)
for(int j=0;j<b[i].size();j++)
{
A[index++]=b[i][j];
}
{

}
}
int main()
{
float arr[]={0.78,0.17,0.39,0.26,0.72,0.94,0.21,0.12,0.23,0.68};
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;
}
```

output:

```Sorted array is
0.12 0.17 0.21 0.23 0.26 0.39 0.68 0.72 0.78 0.94```

Tuts:

http://www.geeksforgeeks.org/bucket-sort-2/

Harumanchi Book implementation:

```#include <stdio.h>
#include <stdlib.h>

int max(int a[],int n)
{
int max=0,i;
for(i=0; i<n; i++)
{
if(a[i]>max)
{
max=a[i];
}
}

return max;
}

void bucket_sort(int a[],int n)
{
int bucket=max(a,n);
int b[bucket],i,k,j=-1;

for(i=0; i<=bucket; i++)
b[i]=0;

for(i=0; i<n; i++)
{
b[a[i]]=b[a[i]]+1;
}

for(i=0; i<=bucket; i++)
{
for(k=b[i]; k>0; --k)
{
a[++j]=i;
}
}

}

int main()
{
int i;

// scanf("%d",&n);
int arr[]={78,17,39,26,72,94,21,12,23,68};
int n=sizeof(arr)/sizeof(arr[0]);

bucket_sort(arr,n);

for(i=0; i<n; i++)

printf(" %d",arr[i]);

return 0;
}
```

output:

` 12 17 21 23 26 39 68 72 78 94`

Time and Space complexity: O(n)

It would be a great help, if you support by sharing :)
Author: zakilive