Bucket Sort Algorithm - The Coding Shala

Bucket Sort Algorithm - The Coding Shala

January 20, 2021

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]);
			bucket[index].add(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);
			bucket[index].add(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] = (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

Please leave a comment below if you like this post or found some errors, it will help me to improve my content.

Comments