• Assume the elments are generated by a random process that distributes elements uniformly and independently over the interval [0, 1)
• Average case Θ(n), worst case O(n^2)

import java.util.*;

public class Bucket
{
	/* Bucket sort
	 * @param array Double array
	 */
	public static void bucketSort(Double [] array) throws ArrayIndexOutOfBoundsException
	{
		List [] bucket = new List<?>[10];

		//create a list for each slot of the bucket
		for(int i = 0; i < 10; i++)
			bucket[i]  = new ArrayList<Double>();

		//insert element
		for(int i = 0; i < array.length; i++)
			bucket[(int)(array[i]*10)].add(array[i]);

		//sort elements in each slot
		for(int i = 0; i < 10; i++)
			Collections.sort(bucket[i]);

		//add all elements into one bucket
		for(int i = 1; i < 10; i++)
			bucket[0].addAll(bucket[i]);

		//output all elements
		for(int i = 0; i < bucket[0].size(); i++)
			array[i] = (Double)bucket[0].get(i);
	}

	public static <T> void display(T [] array)
	{
		for(int i = 0; i < array.length; i++)
			System.out.printf("%5.2f ", (Double)array[i]);
		System.out.println();
	}

	public static void main(String args[])
	{
		Double [] array = {0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.68};

		bucketSort(array);

		display(array);
	}
}
			

• CLRS Chapter 8