BUCKET SORT

Specialty Definition: BUCKET SORT

Domain	Definition
Math	A distribution sort where input elements are initially distributed to several buckets based on an interpolation of the element's key. Each bucket is sorted if necessary, and the buckets' contents are concatenated. (references)
Source: compiled by the editor from various references; see credits.

Top

Specialty Definition: Bucket sort

(From Wikipedia, the free Encyclopedia)

Bucket sort is a sort algorithm that works by partitioning an array into a finite number of buckets and then sorting each bucket. It is a generalization of pigeonhole sort. Bucket sort runs in linear time (&Theta(n)) when input is drawn from a uniform distribution.

It works as follows:

Set up an array of initially empty "buckets" the size of the range.
Go over the original array, putting each object in its bucket.
Sort each non-empty bucket.
Put elements from non-empty buckets back into the original array.

Pseudocode

' A is the array
' n is the number of buckets
' MSBITS(n) returns the most significant bits of n.
'    This could be k*n for sorting numbers, or
'    the first character of n for sorting strings.
' NEXT-SORT is a sort algorithm
BUCKET-SORT(A, n, MSBITS, NEXT-SORT):
  make array B of n lists
  for i = 1 to n:
    insert A[i] into list B[MSBITS(A[i])]
    for i = 0 to n - 1:
      NEXT-SORT(B[i])
  concatenate the lists B[0]...B[n-1] in order

Relationships to other sorting algorithms

Using BUCKET-SORT itself as the NEXT-SORT produces a relative of the radix sort. Using BUCKET-SORT with n == 2 and itself as the NEXT-SORT produces quicksort.

Source: adapted by the editor from Wikipedia, the free encyclopedia under a copyleft GNU Free Documentation License (GFDL) from the article "Bucket sort."

Top

Crosswords: BUCKET SORT

Specialty definitions using "BUCKET SORT": comparison sort ♦ histogram sort ♦ range sort. (references)

Top

Frequency of Internet Keywords: BUCKET SORT

The following statistics estimate the number of searches per day across the major English-language search engines as identified by various trade publications. Hyperlinks lead to commercial use of the expression at Amazon.com.

Expression	Frequency per Day
bucket sort	6
Source: compiled by the editor from various references; see credits.

Top

Anagrams: BUCKET SORT

Scrabble® Enable2K-Verified Anagrams
	Words within the letters "b-c-e-k-o-r-s-t-t-u"
	-2 letters: brockets, buttocks, obstruct, roebucks.
	-3 letters: becrust, becurst, bescour, bettors, brocket, buckers, buckets, buckoes, butters, buttock, cotters, couters, curtest, cutters, obscure, obtuser, outsert, restock, rockets, roebuck, scouter, scutter, stocker, stouter, touters, tuckers, tuckets, turbots.
	-4 letters: bettor, bosker, bosket, bourse, brocks, brutes, bucker, bucket, buckos, burets, burkes, busker, buster, buteos, butter, buttes, cerous, corset, coster.
Source: compiled by the editor from various references; see credits. SCRABBLE® is a registered trademark. All intellectual property rights in and to the game are owned in the U.S.A and Canada by Hasbro Inc., and throughout the rest of the world by J.W. Spear & Sons Limited of Maidenhead, Berkshire, England, a subsidiary of Mattel Inc. Mattel and Spear are not affiliated with Hasbro.