Tuesday, July 30, 2013

What is Bucket Sort?

Bucket Sort (alternatively know as bin sort) is an algorithm that sorts numbers and comes under the category of distribution sort.
This sorting algorithm doesn't compare the numbers but distributes them, it works as follows:
1. Partition a given array into a number of buckets
2. One-by-one the numbers in the array are placed in the designated bucket
3. Now, only sort the bucket that bare numbers by recursively applying this Bucket Sorting algorithm
4. Now, visiting the buckets in order, the numbers should be sorted
Java code:
```public class BucketSort{

public static void sort(int[] a, int maxVal) {
int [] bucket=new int[maxVal+1];

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

for (int i=0; i<a.length; i++) {
bucket[a[i]]++;
}

int outPos=0;
for (int i=0; i<bucket.length; i++) {
for (int j=0; j<bucket[i]; j++) {
a[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("Before: " + Arrays.toString(data));
sort(data,maxVal);
System.out.println("After:  " + Arrays.toString(data));
}
}
```

Thanks.