Bucket Sort

                Bucket Sort is also called as Bin Sort.Bucket sort is a sorting algorithm,it works like partitioning an array into a number of Buckets.Each Bucket is sorted individually.Bucket sort run in linear time on the average.
                The idea of bucket sort is to divide the intervel [0,1) into n equal sized subintervals, or buckets and then distributes the n inputs numbers into the buckets.After the inputs are uniformly distributed over(0,1),we donot expect  many numbers fall into each bucket.
                To produce the output,simply sort the numbers in each bucket and puts bucket in order ,listing the elements in each.
                The worst case performance of Bucket Sort is O(n2) and average case performance is O(n+k).

The following program on  Bucket Sort:

import java.util.*;
public class bucket 
{
public static void main(String[] args) 
{
Scanner sc = new Scanner(System.in);
System.out.println("Enter a positive integer as range.");
int n = sc.nextInt();

Random rnd = new Random();
                                      int[] array = new int[100];
                                     //taking input as randomly from console into array
                                      for(int i = 0; i<100; i++)
                                     {
                                           array[i] = rnd.nextInt(n) +1;
            
                                     }
                                     // displaying array elements 
                                     for(int j = 0; j < 100; j++)
                                    {
                                        System.out.print(array[j] + ",");
                    
                                    }
                                    System.out.println("");
                                  //calling bucketsort() method
                                    bucketSort(array, n);
                     }

//bucket sort method
public static void bucketSort(int [] list, int range)
{
int[] countarray = new int[range];
int[] sorted = new int[list.length];
for(int k = 0; k < list.length; k++)
{
countarray[list[k]-1] = countarray[list[k]-1] + 1;
}
for(int i=0; i < countarray.length-1; i++)
{
int count = countarray[i];
int h = i;
while (count != 0)
{
sorted[i] = i+1;
count--;
h++;
}
}
for(int i=0; i<sorted.length; i++)
{
System.out.print(sorted[i] + ",");
}
}

}