Array - XIII [ Bucket Sort ]

---

Bucket Sort – Bucket sort algorithm works by dividing an array into a number of buckets and then sort the number in each bucket using different sorting algorithm. It has some similarities to radix-sort.

Bucket sort works as follows:

1.     Add the number of the array to the empty “buckets” depending number of digits.

2.     Sort each non-empty buckets.

3.  Pick the numbers from each buckets in order and put back the elements into the original array.

---

Complexity :

•         Worst case performance             O(n²)

•         Average case performance          O(n + k)

•         Worst case space complexity       O(n * k)

---

Algorithm.

---

function BucktSort(int Num[], int n)

          int max=min=Num[0];

for i=1 to n step 1

     do

                    if Num[i] > max

                         then

                                  max = Num[i];

                    else if    Num[i] < min

                         then

                                  min = Num[i];

                    endif

          endfor

int buck[] = new int[max-min+1];

for i = 0; to n step 1

              do

                   buck[Num[i]-min]++;

          endfor

          k = 0;

          for i = 0 to buck.length step 1 

              do

                  for  j = 0 to buck[i], step 1

                        do

                             Num[k++] = i+min;

                  endfor

          endfor

end

---

Source Code

---

import java.io.*;

public class Bucket_Sort

{

    int Num[],Size;

    void Input()

       {

          BufferedReader Br=new BufferedReader(new InputStreamReader(System.in));

             try

                {

                    System.out.print("\tEnter Size : ");

                    Size=Integer.parseInt(Br.readLine());

                    Num=new int[Size];

                    for( int i = 0; i < Size; i++ )    
                      {                          

                           System.out.print("\tEnter Element at ["+(i+1)+"] : " );

                           Num[i]=Integer.parseInt(Br.readLine());

                       }

                 }

             catch(Exception Ex){}

        }

    void BucketSort()

        {       

           int min,max;

           max=min=Num[0];

           for( int i = 1; i < Size; i++ )   

              {

                  if( Num[i] > max )

                    {

                      max = Num[i];

                    } 

                  else if( Num[i] < min )

                    {

                      min = Num[i];

                    } 

              } 

           int buck[] = new int[max-min+1];

           for( int i = 0; i < Size; i++ )

              {  

                 buck[Num[i]-min]++;

              }  

           int k = 0;                                 

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

              {

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

                    {

                        Num[k++] = i+min;                    

                    }

              }

       }

    void display()

        {

           for( int i = 0; i < Size; i++ )    
              {  

                  System.out.print(Num[i]+" ");

              }

           System.out.println();

        }     

    public static void main(String args[])

      {

           Bucket_Sort BST =new Bucket_Sort();

           BST.Input();

           System.out.print("\n\tOriginal Numrray : ");

           BST.display();

           BST.BucketSort ();

           System.out.print("\n\tSorted Numrray : ");

           BST.display();

       }

   }

---