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)
“... it must be obvious that in the agitation preceding the enactment of [protective] laws the zeal of the reformers would be second to the zeal of the highly paid night-workers who are anxious to hold their trade against an invasion of skilled women. To this sort of interference with her working life the modern woman can have but one attitude: I am not a child.”
—Crystal Eastman (1881–1928)