Bucket sort, or bin sort?

Bucket sort, or bin sort, is a sorting algorithm that works by distributing the elements of an array into a number of buckets. Each bucket is then sorted individually, either using a different sorting algorithm, or by recursively applying the bucket sorting algorithm.

Steps:

1. Set up an array of initially empty "buckets".

2. Scatter: Go over the original array, putting each object in its bucket.

3. Sort each non-empty bucket.

4. Gather: Visit the buckets in order and put all elements back into the original array.

Elements are distributed among bins

Elements are sorted within each bin

Bucket sort assumes that the input is drawn from a uniform distribution and has an average-case running time of O(n). The computational complexity estimates involve the number of buckets.

Worst case performance: O(n^2)

Best case performance: Omega(n+k)

Average case performance: Theta(n+k)

Worst case space complexity: O(n.k)

Simple implementation of Bucket sort

import java.util.*;

public class BucketSort {

     public static void sort(int[] tmpData, int maxVal) {

           /**

            * Initialize the Buckets Array to store elements

            **/

           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 occurence.

            **/

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

                bucket[tmpData[i]]++;

           }

           /**

            * Restore all the elements in sorted order.

            **/

           int outPos=0;

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

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

                     tmpData[outPos++]=i;

                }

           }

     }

    

     public static void main(String[] args) {

           int maxVal=5;

           int [] data= {5,3,0,2,4,1,0,5,2,3,1,4};

           System.out.println("Array:" + Arrays.toString(data));

          

           sort(data,maxVal);

          

           System.out.println("Sorted Array:" + Arrays.toString(data));

     }

}

Output:

Array: [5, 3, 0, 2, 4, 1, 0, 5, 2, 3, 1, 4]

Sorted Array:  [0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5]