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:

Reference:
CLRS: http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/Sorting/bucketSort.htm

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)