Bucket Sort

Overview

Bucket Sorts works under the premise of partitioning an array (or list) into  a number of buckets and then sorting the buckets individually.

Concept

The way bucket sort works is:

  1. Set up the empty buckets. Typically these are arrays or some other sort of collection.
  2. Iterate over the unsorted array and place each object in the bucket it belongs based on a characteristic of the value.
  3. Sort each non-empty bucket.
  4. Iterate over the buckets, in order, and pull out all the elements back into the original array.

Algorithmic Complexity

Big-O

AlgorithmData StructureTime Complexity - BestTime Complexity - AverageTime Complexity - WorstWorst Case Auxiliary Space Complexity
Bucket SortArray O(n+k) O(n+k) O(n^2) O(nk)

 

Implementation

Java Implementation

Coming soon!

References

Wikipedia: Bucket sort

 

<- back