Bucket Sort

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:

  1. Set up an array of initially empty "buckets."
  2. Scatter: Go over the original array, putting each object in its bucket.
  3. Sort each non-empty bucket.
  4. Gather: Visit the buckets in order and put all elements back into the original array.

Read more about Bucket SortPseudocode, Optimizations, Comparison With Other Sorting Algorithms

Other articles related to "bucket sort, sort, bucket, buckets":

Bucket Sort - Comparison With Other Sorting Algorithms
... Bucket sort can be seen as a generalization of counting sort in fact, if each bucket has size 1 then bucket sort degenerates to counting sort ... The variable bucket size of bucket sort allows it to use O(n) memory instead of O(M) memory, where M is the number of distinct values in exchange, it gives up counting sort's O(n + M) worst-case behavior ... Bucket sort with two buckets is effectively a version of quicksort where the pivot value is always selected to be the middle value of the value range ...
Summaries of Popular Sorting Algorithms - Bucket Sort
... Bucket sort is a divide and conquer sorting algorithm that generalizes Counting sort by partitioning an array into a finite number of buckets ... Each bucket is then sorted individually, either using a different sorting algorithm, or by recursively applying the bucket sorting algorithm ... A variation of this method called the single buffered count sort is faster than quicksort ...

Famous quotes containing the words sort and/or bucket:

    I think ... I have inside me a sort of answer to the want of today: to the real, deep want of the English people, not to just what they fancy they want. And gradually, I shall get my hold on them.
    —D.H. (David Herbert)

    And now, far removed from the loved habitation,
    The tear of regret will intrusively swell,
    As fancy reverts to my father’s plantation,
    And sighs for the bucket that hung in the well.
    Samuel Woodworth (1788–1842)