# 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;
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
}

//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
``````