Bucket sort is a sorting algorithm that is used mainly when the input is distributed uniformly over a range. Foran instance, sorting a collection of floating point numbers uniformly distributed within the range [0.0, 1.0].
We may use any of the various sorting algorithms available such as quick sort, counting sort, insert sort, etc, each of which operates with varying space/time complexities. When, why, and how to use bucket sort, is something that we learn in this article.
- Pseudo-code of the bucket-sort algorithm.
- Explanation and Time complexity for the bucket-sort algorithm.
- Example with Implementation.
Explanation and Time Complexity
Suppose that inserting in a bucket consumes O(1) time. Thus the first 2 steps would consume O(n) time. The O(1) becomes possible if using a linked list for representing a bucket. The 3rd step also takes an average O(n) time, provided all the numbers are distributed uniformly. The final step also consumes O(n) time as the number of items in all the buckets will be n.