Bucket Sort

Bucket sort, or bin sort, is a sorting algorithm that works by partitioning 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. It is a distribution sort, and is a cousin of radix sort in the most to least significant digit flavour

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.

Optimizations         

A common optimization is to put the elements back in the original array first, then run insertion sort over the complete array; because insertion sort's runtime is based on how far each element is from its final position, the number of comparisons remains relatively small, and the memory hierarchy is better exploited by storing the list contiguously in memory.

Comparision with other sorting techniques:

1.Bucket sort can be seen as a generalization of counting sort; in fact, if each bucket has size 1 then bucket sort degenerates to counting sort.

2.Bucket sort with two buckets is effectively a version of quicksort where the pivot value is always selected to be the middle value of the value range. While this choice is effective for uniformly distributed inputs, other means of choosing the pivot in quicksort such as randomly selected pivots make it more resistant to clustering in the input distribution.

3.The n-way mergesort algorithm also begins by distributing the list into n sublists and sorting each one; however, the sublists created by mergesort have overlapping value ranges and so cannot be recombined by simple concatenation as in bucket sort. Instead, they must be interleaved by a merge algorithm. However, this added expense is counterbalanced by the simpler scatter phase and the ability to ensure that each sublist is the same size, providing a good worst-case time bound.

4.Top-down radix sort can be seen as a special case of bucket sort where both the range of values and the number of buckets is constrained to be a power of two. Consequently, each bucket's size is also a power of two, and the procedure can be applied recursively. This approach can accelerate the scatter phase, since we only need to examine a prefix of the bit representation of each element to determine its bucket.

Java code :

import java.util.ArrayList;
import java.util.Arrays;


public class BucketSort {


public static void main(String args[]) {


Double[] array = { 9.0, 8.0, 7.0, 6.0, 5.0, 4.0, 3.0, 2.0, 1.0 };


ArrayList<Double> masterlist = new ArrayList<Double>(Arrays
.asList(array));


// all of the doubles will be 0.0 <= x < 100.0
double rangeOfBucket = 100.0 / masterlist.size();


// creating a new ArrayList of n buckets
ArrayList[] buckets = new ArrayList[masterlist.size()];
buckets = fillBuckets(buckets);


double d;
for (int i = 0; i < masterlist.size(); i++) {
d = (Double) masterlist.get(i);
// this mess discovers the appropriate bucket and dumps d in it
buckets[(int) (d / rangeOfBucket)].add(d);
}


masterlist = new ArrayList<Double>();


for (int m = 0; m < buckets.length; m++) {
buckets[m] = insertionSort(buckets[m]); // sort the bucket
for (int n = 0; n < buckets[m].size(); n++) {
masterlist.add((Double) buckets[m].get(n));// reading the
// numbers back into
// the original list
// in order
}
}


System.out.println(masterlist.toString());


}


/**
* Modified version of InsertionSort found at
* http://www.samspublishing.com/articles/article.asp?p=31526&seqNum=4&rl=1
* 
* @param a
*            The ArrayList to be sorted
* @return A sorted ArrayList
*/
public static ArrayList insertionSort(ArrayList a) {


int in, out;


for (out = 1; out < a.size(); out++) {
double temp = (Double) a.get(out); // remove marked item


in = out; // start shifts at out


// until one is smaller,
while (in > 0 && (Double) a.get(in - 1) >= temp) {
a.set(in, a.get(in - 1));// shift item right
in--; // go left one position
}


a.set(in, temp); // insert marked item
}


return a;
}


/**
* Helper method to fill an array of ArrayLists with _unique_ ArrayLists,
* something that Arrays.fill() does not do.
* 
* @param b
*            The array of ArrayLists to be filled
* @return The original array filled with empty ArrayLists
*/
private static ArrayList[] fillBuckets(ArrayList[] b) {
for (int i = 0; i < b.length; i++) {
b[i] = new ArrayList();
}
return b;
}


}