### Bucket Sort Algorithm - The Coding Shala

Last Updated: 20-Jan-2021
Home >> Algorithms >> Bucket Sort

In this post, we will learn what is Bucket Sort Algorithm and will write a Java program to implement Bucket Sort.

## Bucket Sort Algorithm

Bucket Sort is a sorting algorithm. In bucket sort, we create n buckets and insert similar types of elements into the buckets. Bucket sort is mainly useful when input is uniformly distributed over a range. For example, a large set of floating-point numbers are in the range from 0.0 to 1.0 and uniformly distributed across the range. Another example a large set of numbers which are in the range from 1 to 99.

In these types of cases, we use the bucket sort algorithm.

### Working of Bucket Sort Algorithm

The following steps need to follow for the Bucket Sort Algorithm:
• Step 1. First, we create n empty buckets/lists.
• Step 2. Now for every element arr[i] of given array we insert arr[i] into buckets. Now the main point is how to insert into buckets. How we decide that? If array element are floating numbers over range 0.0 to 1.0 we can do n*arr[i] and insert into bucket[n*arr[i]]. Similarly, we can find some relation and insert it into buckets.
• Step 3. we sort individual buckets using insertion sort or merge sort.
• Step 4. Concatenate all the sorted buckets.

### Example of Bucket Sort Algorithm

Here is an example of the bucket sort algorithm
Input array -> 0.78 0.17 0.39 0.26 0.72 0.94 0.21 0.12 0.23 0.68

create 10 buckets
0    1          2          3     4     5      6        7      8        9
|           |       |        |        |          |
0.12     0.21    0.39    0.68    0.72       0.94
|           |                |
0.17     0.23      0.78
|
0.26

Sorted Output-> 0.12 0.17 0.21 0.23 0.26 0.39 0.68 0.72 0.78 0.94

### Time Complexity of Bucket Sort Algorithm

The time complexity of Bucket sort in the worst case is O(n logn) and in the average case is O(n).

### Bucket Sort Algorithm Java Program

The following Java program explains the bucket sort algorithm:

```import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

//bucket sort
//the coding shala

class Main{

public static void bucket_sort(double[] input) {
int len = input.length;
//create empty buckets
List[] bucket = new List[10];
for(int i=0; i<bucket.length; i++) {
bucket[i] = new ArrayList<Double>();
}
//insert into buckets
for(int i=0; i<len; i++) {
int index = (int)(10*input[i]);
}
//check bucket
/*for(int i=0; i<10; i++) {
for(int j = 0; j<bucket[i].size(); j++) {
System.out.print(bucket[i].get(j)+" ");
}
System.out.println();
}*/

//sort individual buckets
for(int i=0; i<10; i++) {
Collections.sort(bucket[i]);
}

//store back into input array
int in = 0;
for(int i=0; i<10; i++) {
for(int j = 0; j<bucket[i].size(); j++) {
input[in] = (double)bucket[i].get(j);
in++;
}
}
}

public static void main(String[] args) {
double[] input = {0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.68};
int len = input.length;
bucket_sort(input);
for(int i=0;i<len;i++) {
System.out.print(input[i]+" ");
}
}
}
```

Here is another example of the bucket sort

An input array is a number between 1 to 99.

Java Program:

```import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

//bucket sort
//the coding shala

class Main{

public static void bucket_sort(int[] input) {
int len = input.length;
//create empty buckets
List[] bucket = new List[10];
for(int i=0; i<bucket.length; i++) {
bucket[i] = new ArrayList<Integer>();
}
//insert into buckets
for(int i=0; i<len; i++) {
int index = (input[i]/10);
}
//check bucket
/*for(int i=0; i<10; i++) {
for(int j = 0; j<bucket[i].size(); j++) {
System.out.print(bucket[i].get(j)+" ");
}
System.out.println();
}*/

//sort individual buckets
for(int i=0; i<10; i++) {
Collections.sort(bucket[i]);
}

//store back into input array
int in = 0;
for(int i=0; i<10; i++) {
for(int j = 0; j<bucket[i].size(); j++) {
input[in] = (int)bucket[i].get(j);
in++;
}
}
}

public static void main(String[] args) {
int[] input = {80, 50, 30, 10, 90, 60, 0, 70, 40, 20, 50};
int len = input.length;
bucket_sort(input);
for(int i=0;i<len;i++) {
System.out.print(input[i]+" ");
}
}
}
```

Other Posts You May Like