The key to performance is elegance, not battalions of special cases. Jon Bentley and Doug McIlroy

Bucket sort

Language Java | Level Intermediate | Category Algorithms | August 3, 2015 7:41 am


Algorithm Problem Description

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.

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]

          	        
          	        				    


Comments



Please login to add comments.