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(n2)
• 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();
}
}
