Bucket sorting is a sorting algorithm that works with partitioning an array into a number of packets. Each bucket sorted individually using the same or different algorithm. Bucket sort and radix sort look like same. But it has some difference.
The following table shows the difference between Bucket sort and radix sort.
Bucket Sort | Radix Sort |
---|---|
Bucket sort adds the bucket and appends into one array. | Radix sort adds to the bucket without sorting or without bucket based on the second digit. |
Not in-place | In-place |
Stable sorting algorithm | Stable sorting algorithm |
Separates array into smaller groups or buckets and sorts them individually using a sub-sorting algorithm or recursive | Radix means base (binary, octal, decimal, etc). Therefore, this sorting is for numbers (also used for strings |
Combine step is trivial | Start from Most Significant Digit or Least Significant Digit |
It uses buckets or bins of the fixed range. | Call counting sort on the array at the digit position |
Write a program to implement bucket sort algorithm.
source Code
package com.dsacode.Algorithm.sorting; import java.util.Arrays; public class Bucketsort { public static int[] bucketSort(int[] arr) { int i, j; int[] count = new int[arr.length]; Arrays.fill(count, 0); for (i = 0; i < arr.length; i++) { count[arr[i]]++; } for (i = 0, j = 0; i < count.length; i++) { for (; count[i]>0; (count[i])--) { arr[j++] = i; } } return arr; } public static void main(String[] args) { int[] arr = new int[] { 1, 3, 4, 6, 4, 2, 9, 1, 2, 9 }; System.out.println("unsorted array before sorting : " + Arrays.toString(arr)); arr = bucketSort(arr); System.out.println("Sorted array After bucketSort sorting : " + Arrays.toString(arr)); } }
Output
Unsorted array before sorting: [1, 3, 4, 6, 4, 2, 9, 1, 2, 9] Sorted array after bucket Sort sorting: [1, 1, 2, 2, 3, 4, 4, 6, 9, 9]
Algorithm Explanation
![]() | Send the unsorted array to utility function and find its max value. |
![]() | Bucket size should be maxed Value + 1 since index of array starts from 0. |
![]() | Distribute the array element into bucket |
![]() | Walk through bucket from the start and pull the bucket element which should be already sorted. |
Time Complexity
Best Case | Average Case | Worst Case |
---|---|---|
O(n+k) | O(n+k) | O(n^2) |