Bucket Sort Algorithm  The Coding Shala
Last Updated: 20Jan2021
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 floatingpoint 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]+" "); } } }
 Bubble Sort Algorithm
 Binary Search Algorithm
 The Big O Notation
 Height of Binary Tree
 Find Number of Islands
Comments
Post a Comment