Bucket sort, or bin sort, is a sorting algorithm that works by partitioning an array into a number of buckets. Each bucket is then sorted individually, either using a different sorting algorithm, or by recursively applying the bucket sorting algorithm. It is a distribution sort, and is a cousin of radix sort in the most to least significant digit flavour. Bucket sort is a generalization of pigeonhole sort. Since bucket sort is not a comparison sort, the Ω(n log n) lower bound is inapplicable. The computational complexity estimates involve the number of buckets.
Bucket sort works as follows:
- Set up an array of initially empty "buckets."
- Scatter: Go over the original array, putting each object in its bucket.
- Sort each non-empty bucket.
- Gather: Visit the buckets in order and put all elements back into the original array.
Read more about Bucket Sort: Pseudocode, Optimizations, Comparison With Other Sorting Algorithms
Famous quotes containing the words bucket and/or sort:
“Dear fellow-artist, why so free
With every sort of company,
With every Jack and Jill?
Choose your companions from the best;
Who draws a bucket with the rest
Soon topples down the hill.”
—William Butler Yeats (1865–1939)
“I fly in dreams, I know it is my privilege, I do not recall a single situation in dreams when I was unable to fly. To execute every sort of curve and angle with a light impulse, a flying mathematics—that is so distinct a happiness that it has permanently suffused my basic sense of happiness.”
—Friedrich Nietzsche (1844–1900)