Bucket Sort

The Bucket sort (bin sort) is a Sorting algorithm that works by distributing the elements of an array into a number of Buckets. Each bucket is then sorted individually, either using a different sorting algorithm, or by recursively applying the bucket sorting algorithm















Bucket sort works as follows:

1. Set up an array of initially empty "buckets".
2. Scatter: Go over the original array, putting each object in its bucket.
3. Sort each non-empty bucket.
4. Gather: Visit the buckets in order and put all elements back into the original array.

import java.util.*; /** * * @author Manoj */ 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=50; int [] data= {10,9,21,17,20,11}; System.out.println("Before: " + Arrays.toString(data)); sort(data,maxVal); System.out.println("After: " + Arrays.toString(data)); } }
Output: