Bucket Sort Program and Complexity (Big-O)

Bucket sort/Bin sort is a distribution sort as a generalization of pigeonhole sort. It’s useful when input values are uniformly distributed over a range then divide this range in some interval and put values in a bucket which lies within these intervals.Finally, sort values in each bucket by any sorting technique and then print by sequence by iterating intervals.

Bucket Sort Steps

  1. Set up an array of empty “buckets” initially.
  2. Go over the original array, putting each item in its interval bucket.
  3. Sort all non-empty bucket.
  4. Visit each interval buckets in order and put all elements back into the original array.

Points to Remember

  • Data structure: Array
  • Best Time Complexity: Ω(n+k)
  • Average Time Complexity: Θ(n+k)
  • Worst Time Complexity: O(n^2)
  • Worst Space Complexity: O(n)

Bucket Sort Java Program

public class BucketSort {

		public static void main(String[] args) {

			//Assuming our key values are with in range 0 - 1
			double[] items = { 0.23, 0.67, 0.32, 0.25, 0.88, 0.45, 0.86, 0.16, 0.59, 0.38, 0.19, 0.43,  0.02 };
	        System.out.println("Before Bucket Sorting :");

	        //Perform counting sort sort

	        System.out.println("After Bucket Sorting :");

		private static void bucketsort(double []items)
			//create array of size 10 that will have index value as 0-9
			//Initially will keep empty bucket
			java.util.List []numbers=new ArrayList[10];
			for(double key:items)
				//To equally distribute input values , multiply key with array size.
				int index=(int)(key*numbers.length);
				//index position is not having any value yet create blank bucket
					numbers[index]=new ArrayList();

				//add items based on index position

			//Now sort values in each bucket by any sorting method
			// and add in initial array
			int i=0;
			for(int index=0; index<span id="mce_SELREST_start" style="overflow:hidden;line-height:0;">&#65279;</span>&lt;numbers.length; index++)

					//Here i am using Collections utility method but
					//you use any sorting algorithm.
					//iterate each value in sorted bucket
					//add it in original array position
					for(double  item:numbers[index])


		static void printArray(double items[])
	        for (double item:items)
	            System.out.print(item + &quot; &quot;);



Before Bucket Sorting :
0.23 0.67 0.32 0.25 0.88 0.45 0.86 0.16 0.59 0.38 0.19 0.43 0.02 
After Bucket Sorting :
0.02 0.16 0.19 0.23 0.25 0.32 0.38 0.43 0.45 0.59 0.67 0.86 0.88 

One thought on “Bucket Sort Program and Complexity (Big-O)”

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s