How to implement Bucket (Bin) sort ?

• Distribute the elements into a number of buckets
• Each bucket is then sorted individually (using any type of sorting algo)

• Elements are distributed among bins

       

• Elements are sorted within each bin

        


Implementation

/**

 * Initialize the Bucket array to store elements

 **/

int maxVal = 5;

int [] bucket = new int[maxVal+1];

for (int i=0; i<bucket.length; i++) {

    bucket[i]=0;

}

/**

 * Element as index and

 * value stored at array index is occurrence

 **/

for (int i=0; i<array.length; i++) {

    bucket[array[i]]++;

}

/**

 * Restore all the elements in sorted order

 **/

int outPos = 0;

for (int i=0; i<bucket.length; i++) {  // iterate through buckets

   for (int j=0; j<bucket[i]; j++) {

       array[outPos++]=i;

   }

}