How to do Bucket sort in Java?

In this tutorial, we will learn to perform bucket sort in java to sort any given array. Bucket sort can sort an array in linear time but it only works for special set of inputs.

The time complexity of this algorithm is O(n).

The concept of bucket sort is very simple, we distribute the elements of an array into a number of buckets and then sort the individual buckets by a different sorting algorithm or by using recursion of bucket sort algorithm.

• This algorithm works best if the function to partition the array is efficient.

Java Code: Bucket Sort

import java.util.*;

public class Main
{
public static int[] bucket_sort(int[] arr, int max_value)
{
int[] bucket = new int[max_value + 1];
int[] sorted_arr = new int[arr.length];

for (int i= 0; i <arr.length; i++)
bucket[arr[i]]++;

int pos = 0;
for (int i = 0; i < bucket.length; i++)
for (int j = 0; j < bucket[i]; j++)
sorted_arr[pos++] = i;

return sorted_arr;
}

static int maxValue(int[] arr)
{
int max_value = 0;
for (int i = 0; i < arr.length; i++)
if (arr[i] > max_value)
max_value = arr[i];
return max_value;
}

public static void main(String args[])
{
int[] arr ={80, 50, 30, 10, 90, 60, 0, 70, 40, 20, 50};
int max_value = maxValue(arr);

System.out.print("\nOriginal : ");
System.out.println(Arrays.toString(arr));

System.out.print("\nSorted : ");
System.out.println(Arrays.toString(bucket_sort(arr,max_value)));

}
}

Bucket sort is only useful when the input elements are uniformly distributed over a range.

Bucket sort can be made stable, the algorithm is known as radix sort.

The worst-case complexity of bucket sort is when all the elements are in the same bucket – O(n^2) as it has to be sorted by a different sorting algorithm in that case. The space complexity of bucket sort is O(n) because to sort sequential elements, we will need an array as big as the original array.

Output:

Original : [80, 50, 30, 10, 90, 60, 0, 70, 40, 20, 50]
Sorted : [0, 10, 20, 30, 40, 50, 50, 60, 70, 80, 90]