Bucket Sort

• Time Complexity - O(N log N) || Space Complexity - O(N)
• In bucket sort, we create buckets first, using some formula. After the creation of the bucket, we one by one put the elements into the buckets, again using some formula. After we put all the elements into created buckets, we sort the elements bucketwise using any sorting algorithm like quicksort, mergesort, etc
• After sorting elements in all the buckets, we concatenate the elements from all the buckets together.
• The biggest advantage of Bucket Sort compared to other sort is that each bucket can be sorted independently. Hence, it is a great suite for distributed computing.
• Suppose we have given a very large array of Person objects and we have to sort the people in increasing order of age. We know it is a large array hence efficiency is very important. Also, we know that the value of 'age' lies in a small range. Bucket sort is perfect for these kinds of situations. We can make small multiple buckets of 1 different year each and would be able to achieve O(n) running time. Just O(n), isn't it fascinating?
• So, bucket sort can be used if the input is uniformly distributed over a range.
• Formulae:
• No. of buckets to be created = ceil(Square root of total no. of items)
• We have to iterate through each number and put it in the appropriate bucket, so the formula for appropriate bucket = floor[ (Value * no. of buckets) / (maximum value in array+1) ] 
• It is very important to have input distributed uniformly over a range. If it is not distributed uniformly, all the data will not go in different buckets, or it might be possible that all the data goes into a single bucket and thus defeating the whole purpose of bucket sort.

__________________________________________________________________________________________________________________________________________________________________



import java.util.*;

public class Main {
 
    public static void getStatusOfBuckets(ArrayList<Integer>[] buckets){
        for(int i=0; i<buckets.length;i++){
            System.out.println("Bucket "+(i+1)+" : "+buckets[i]);
        }
        System.out.println();
    }
 
    public static void main(String[] args) throws Exception {
        int[] arr = {40,10,30,80,70,20,60,50,100,0,-1};
     
        System.out.println("UnSorted Array :");
        for(int i=0;i<arr.length;i++){
            System.out.print(arr[i]+" ");
        }
     
        System.out.println();
        int noOfBuckets = (int) Math.ceil(Math.sqrt(arr.length));
        System.out.println("No. of buckets created: "+ noOfBuckets);
     
        // this is an array of arrayList
        // buckets are implemented using arrayList
        ArrayList<Integer>[] buckets = new ArrayList[noOfBuckets];
        for(int i=0;i<noOfBuckets;i++) {
        buckets[i]=new ArrayList<Integer>();
        }
        getStatusOfBuckets(buckets);
     
        // finding max value in array
        int maxValueInArray=arr[0];
        for(int i=1;i<arr.length;i++){
            if(arr[i]>maxValueInArray){
                maxValueInArray=arr[i];
            }
        }
     
        // now we have to iterate through array and put the element in appropriate bucket
        for(int i=0;i<arr.length;i++){
            int appropriateBucket = (int) Math.floor((arr[i]*noOfBuckets)/(maxValueInArray+1));
             buckets[appropriateBucket].add(arr[i]);
        }
        getStatusOfBuckets(buckets);
     
        // now we sort the buckets individually
        for(int i=0;i<noOfBuckets;i++){
            Collections.sort(buckets[i]);
        }
     
        getStatusOfBuckets(buckets);
     
        // now concatenate all buckets
        int index=0;
        for(int i=0;i<noOfBuckets;i++){
            for(int value : buckets[i]){
                arr[index]=value;
                index++;
            }
        }
     
        System.out.println("Sorted Array...");
        for(int i=0;i<arr.length;i++){
            System.out.print(arr[i]+" ");
        }
    }
}

Output:

UnSorted Array :
40 10 30 80 70 20 60 50 100 0 -1 
No. of buckets created: 4
Bucket 1 : []
Bucket 2 : []
Bucket 3 : []
Bucket 4 : []

Bucket 1 : [10, 20, 0, -1]
Bucket 2 : [40, 30, 50]
Bucket 3 : [70, 60]
Bucket 4 : [80, 100]

Bucket 1 : [-1, 0, 10, 20]
Bucket 2 : [30, 40, 50]
Bucket 3 : [60, 70]
Bucket 4 : [80, 100]

Sorted Array...
-1 0 10 20 30 40 50 60 70 80 100