Tag Archives: Bucket Sort Space Complexity

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 :");
	        printArray(items);

	        //Perform counting sort sort
	        bucketsort(items);

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

		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
				if(numbers[index]==null)
				{
					numbers[index]=new ArrayList();

				}
				//add items based on index position
				numbers[index].add(key);
			}

			//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++)
			{

				if(numbers[index]!=null)
				{
					//Here i am using Collections utility method but
					//you use any sorting algorithm.
					Collections.sort(numbers[index]);
					//iterate each value in sorted bucket
					//add it in original array position
					for(double  item:numbers[index])
					{
						items[i++]=item;
					}
				}

			}
		}

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

}

Output


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 
Advertisements