Bucket sort, or bin sort, is a sorting algorithm that works by distributing the elements of 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,  a generalization of pigeonhole sort that allows multiple keys per bucket, and is a cousin of radix sort in the most-to-least significant digit flavor. Bucket sort can be implemented with comparisons and therefore can also be considered a comparison sort algorithm. The computational complexity depends on the algorithm used to sort each bucket, the number of buckets to use, and whether the input is uniformly distributed.

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.

Pseudocode

 function bucketSort(array, k) is
     buckets ← new array of k empty lists
     M ← 1 + the maximum key value in the array
     for i = 0 to length(array) do
         insert array[i] into buckets[floor(k × array[i] / M)]
     for i = 0 to k do 
         nextSort(buckets[i])
     return the concatenation of buckets[0], ...., buckets[k]

Let array denote the array to be sorted and k denote the number of buckets to use. One can compute the maximum key value in linear time by iterating over all the keys once. The floor function must be used to convert a floating number to an integer ( and possibly casting of datatypes too ). The function nextSort is a sorting function used to sort each bucket. Conventionally, insertion sort is used, but other algorithms could be used as well, such as selection sort or merge sort. Using bucketSort itself as nextSort produces a relative of radix sort; in particular, the case n = 2 corresponds to quicksort (although potentially with poor pivot choices).

Analysis

Worst-case analysis 
When the input contains several keys that are close to each other (clustering), those elements are likely to be placed in the same bucket, which results in some buckets containing more elements than average. The worst-case scenario occurs when all the elements are placed in a single bucket. The overall performance would then be dominated by the algorithm used to sort each bucket, for example  insertion sort or  comparison sort algorithms, such as merge sort.

Average-case analysis 
Consider the case that the input is uniformly distributed. The first step, which is initialize the buckets and find the maximum key value in the array, can be done in  time. If division and multiplication can be done in constant time, then scattering each element to its bucket also costs . Assume insertion sort is used to sort each bucket, then the third step costs , where  is the length of the bucket indexed . Since we are concerning the average time, the expectation  has to be evaluated instead. Let  be the random variable that is  if element  is placed in bucket , and  otherwise. We have . Therefore,

The last line separates the summation into the case  and the case . Since the chance of an object distributed to bucket  is ,  is 1 with probability  and 0 otherwise. 

With the summation, it would be

Finally, the complexity would be .

The last step of bucket sort, which is concatenating all the sorted objects in each buckets, requires  time. Therefore, the total complexity is . Note that if k is chosen to be , then bucket sort runs in  average time, given a uniformly distributed input.

Optimizations

A common optimization is to put the unsorted elements of the buckets back in the original array first, then run insertion sort over the complete array; because insertion sort's runtime is based on how far each element is from its final position, the number of comparisons remains relatively small, and the memory hierarchy is better exploited by storing the list contiguously in memory.

If the input distribution is known or can be estimated, buckets can often be chosen which contain constant density (rather than merely having constant size). This allows  average time complexity even without uniformly distributed input.

Variants

Generic bucket sort
The most common variant of bucket sort operates on a list of n numeric inputs between zero and some maximum value M and divides the value range into n buckets each of size M/n. If each bucket is sorted using insertion sort, the sort can be shown to run in expected linear time (where the average is taken over all possible inputs). However, the performance of this sort degrades with clustering; if many values occur close together, they will all fall into a single bucket and be sorted slowly.  This performance degradation is avoided in the original bucket sort algorithm by assuming that the input is generated by a random process that distributes elements uniformly over the interval [0,1).

ProxmapSort

Similar to generic bucket sort as described above, ProxmapSort works by dividing an array of keys into subarrays via the use of a "map key" function that preserves a partial ordering on the keys; as each key is added to its subarray, insertion sort is used to keep that subarray sorted, resulting in the entire array being in sorted order when ProxmapSort completes. ProxmapSort differs from bucket sorts in its use of the map key to place the data approximately where it belongs in sorted order, producing a "proxmap" — a proximity mapping — of the keys.

Histogram sort
Another variant of bucket sort known as histogram sort or counting sort adds an initial pass that counts the number of elements that will fall into each bucket using a count array. Using this information, the array values can be arranged into a sequence of buckets in-place by a sequence of exchanges, leaving no space overhead for bucket storage.

Postman's sort
The Postman's sort is a variant of bucket sort that takes advantage of a hierarchical structure of elements, typically described by a set of attributes. This is the algorithm used by letter-sorting machines in post offices: mail is sorted first between domestic and international; then by state, province or territory; then by destination post office; then by routes, etc. Since keys are not compared against each other, sorting time is O(cn), where c depends on the size of the key and number of buckets. This is similar to a radix sort that works "top down," or "most significant digit first."

Shuffle sort
The shuffle sort is a variant of bucket sort that begins by removing the first 1/8 of the n items to be sorted, sorts them recursively, and puts them in an array. This creates n/8 "buckets" to which the remaining 7/8 of the items are distributed. Each "bucket" is then sorted, and the "buckets" are concatenated into a sorted array.

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. While this choice is effective for uniformly distributed inputs, other means of choosing the pivot in quicksort such as randomly selected pivots make it more resistant to clustering in the input distribution.

The n-way mergesort algorithm also begins by distributing the list into n sublists and sorting each one; however, the sublists created by mergesort have overlapping value ranges and so cannot be recombined by simple concatenation as in bucket sort. Instead, they must be interleaved by a merge algorithm. However, this added expense is counterbalanced by the simpler scatter phase and the ability to ensure that each sublist is the same size, providing a good worst-case time bound.

Top-down radix sort can be seen as a special case of bucket sort where both the range of values and the number of buckets is constrained to be a power of two. Consequently, each bucket's size is also a power of two, and the procedure can be applied recursively. This approach can accelerate the scatter phase, since we only need to examine a prefix of the bit representation of each element to determine its bucket.

See also

References

 Paul E. Black "Postman's Sort" from Dictionary of Algorithms and Data Structures at NIST.
 Robert Ramey '"The Postman's Sort" C Users Journal Aug. 1992
 NIST's Dictionary of Algorithms and Data Structures: bucket sort

External links
 Bucket Sort Code for Ansi C
 Variant of Bucket Sort with Demo

Sorting algorithms
Stable sorts
Articles with example pseudocode
버킷 정렬(bucket 整列), 버킷 소트()는 배열의 원소를 여러 버킷으로 분산하여 작동하는 정렬 알고리즘이다. 버킷은 빈(bin)이라고도 불리고, 버킷 정렬도 빈 정렬로도 불린다. 각 버킷은 다른 정렬 알고리즘을 사용하거나 버킷 정렬을 반복 적용해 각각 정렬한다. 분포 정렬이고 일반화된 비둘기집 정렬과 같다. 최하위 유효숫자부터 정렬하는 기수 정렬과도 비슷하다. 비교를 이용해 구현할 수도 있어서 비교 정렬 알고리즘으로 보기도 한다. 계산 복잡도는 각 버킷을 정렬하는 데 사용되는 알고리즘, 사용할 버킷 수, 버킷마다 균일한 입력이 들어가는지 여부에 따라 다르다.

정렬은 다음과 같이 이루어진다.

 빈 버킷의 배열을 준비한다.
 분산: 정렬할 배열의 원소를 각각 버킷에 넣는다.
 내용물이 있는 버킷을 각각 정렬한다.
 수집: 버킷을 순서대로 방문하며 모든 원소를 원래 배열에 다시 넣는다.

의사 코드 
 function bucketSort(array, k) is
     buckets ← new array of k empty lists
     M ← the maximum key value in the array
     for i = 1 to length(array) do
         insert array[i] into buckets[floor(k × array[i] / M)]
     for i = 1 to k do
         nextSort(buckets[i])
     return the concatenation of buckets[1], ...., buckets[k]
array는 정렬할 배열, k는 사용할 버킷 수이다. 키 값의 최대값은 모든 키를 한 번씩 조회하여 선형 시간에 계산할 수 있다. floor는 바닥 함수로써 부동 소수점 수를 정수로 변환한다. nextSort는 각 버킷 내부를 정렬하는 함수이다. 일반적으로 삽입 정렬을 사용하지만 다른 알고리즘도 사용할 수 있다. 여기서 정의한 bucketSort 자체를 nextSort로 사용하면 기수 정렬과 흡사하고, 특히 n = 2 이면 (피벗 선택이 나쁜) 퀵 정렬과 동등하다.

분석

최악 시간 복잡도 
주로 입력이 일정 범위에 걸쳐 균등 분포에 가까울 때 유용하다. 가까운 값을 가진 값을 가진 키가 여럿일 경우 (클러스터를 형성할 경우) 이 키들은 같은 버킷에 들어갈 확률이 높아 어떤 버킷은 다른 버킷보다 더 많은 원소를 가질 수 있다. 최악의 경우에는 모든 원소가 하나의 버킷에 들어갈 수 있다. 이 경우 전체 성능은 버킷 내부를 정렬하는 알고리즘에 따라 결정된다. 주로 삽입 정렬이 이용되므로 이어서, 병합 정렬과 같은 비교 정렬 알고리즘의 보다 나빠질 수 있다.

평균 시간 복잡도 
입력이 균등하게 분포한다고 생각하자. 첫 단계에서 버킷을 초기화하고 배열에서 최대 값을 찾는 데  시간이 든다. 나눗셈과 곱셈이 상수 시간 복잡도를 가진다면 원소 분산에 드는 시간도 역시 이다. 각 버킷 정렬에 삽입 정렬이 이용된다고 가정하면, 세 번째 단계인 버킷 내부 정렬로는 가 로 정렬된 버킷의 길이일 때 가 든다. 평균적인 경우에 관심이 있으므로 기대값 로 대신 평가할 수 있다. 를 원소 가 버킷 에 들었으면 , 그렇지 않으면 인 확률 변수로 두면, 이다. 따라서,

 

마지막 줄은 인 경우와 인 경우를 나누어 각각 합산한다. 각 원소가 버킷 에 들어갈 확률은 이므로, 은  확률로 1, 아니면 0이다.

 
 

적용하면

 

마지막으로 복잡도는 .

마지막 단계로 각 버킷을 연결하는 데는  시간이 든다. 따라서 총 복잡도는 이다. 균등 분포에서 k를 로 고르면 평균 시간 에 수행됨에 유의하라.

최적화 
일반적인 최적화로는 버킷을 정렬되지 않은 채로 먼저 원래 배열에 돌려 넣은 다음 전체 배열에 대해 삽입 정렬을 수행한다. 삽입 정렬의 실행시간은 각 원소가 마지막에 정렬된 위치에서 떨어진 거리에 의해 결정되므로 상대적으로 적은 비교 연산을 하게 된다. 원소의 리스트가 메모리에 연속적으로 저장되므로 메모리 계층 구조도 더 잘 활용된다.

종류

일반 버킷 정렬 
버킷 정렬의 가장 일반적인 형태는 0부터 최대 값 M 사이의 수를 각각의 크기가 M/n인 n개의 버킷으로 나누는 것이다. 각 버킷이 삽입 정렬을 사용하면 정렬 되면 선형 시간의 기대값으로 수행되는 것처럼 보인다. (모든 입력에 대해 평균을 취할 경우). 그러나 많은 값이 서로 인접해 있으면 클러스터를 이루었다고 하며 모두 단일 버킷으로 들어갈 수 있어 성능이 저하된다. 원래의 버킷 정렬 알고리즘은 [0,1) 구간에서 무작위로 발생시킨 값을 입력으로 취한다고 가정하여 이런 성능저하를 회피하였다.

프록스맵 정렬 
프록스맵(proxmap ← proximity mapping) 정렬은 위에서 설명한 일반 버킷 정렬과 유사하지만, 키의 반 순서(partial order)를 유지하는 "맵 키" 함수를 사용해 키 배열을 부분배열로 분할한다. 각 키를 하위 배열에 추가하면 삽입 정렬을 사용해 하위 배열을 정렬된 상태로 유지하여 전체 배열을 정렬된 상태로 유지한다. 맵 키 함수를 이용해 자료를 정렬순에 근사한 대략의 위치로 옮긴다는 점에서 버킷 정렬과 다르다.

히스토그램 정렬 
히스토그램 정렬 또는 계수 정렬은 계수 배열을 이용해 각 버킷에 들어갈 원소의 수를 세는 초기화 단계를 추가한다. 이 정보를 이용하면 배열 원소들은 버킷 순서에 따라 위치 교환만으로 정렬할 수 있으므로 버킷에 따로 메모리를 할당하지 않아 공간 오버 헤드가 제거된다.

우체부 정렬 
우체부 정렬(postman's sort)은 보통 속성 집합으로 표현되는 원소의 계층 구조를 활용하는 버킷 정렬의 일종이다. 우체국의 편지 분류기에 사용된다. 우편물은 국내와 국제로, 다음에는 광역지자체별로, 다음에는 지역 우체국으로, 다음에는 각각의 배달 경로로 분류된다. 이 과정에서 각 키를 서로 비교하지 않기 때문에 정렬의 시간복잡도는 O(cn)이다. c는 키의 크기와 버킷 수에 따라 결정된다. 최상위 유효숫자 우선 기수 정렬과 유사하다.

셔플 정렬 
셔플 정렬 은 정렬할 항목 n개 가운데 첫 1/8을 제거하고 재귀적으로 정렬하여 새 배열에 넣는 것으로 시작한다. 이 방법으로 n/8개의 버킷을 하여 나머지 7/8을 분산시켜 넣을 버킷을 생성하고, 각 버킷은 정렬된 배열로 연결된다.

다른 정렬 알고리즘과 비교 
버킷 정렬은 계수 정렬의 일반화로 볼 수 있다. 각 버킷의 크기가 1인 버킷 정렬은 계수 정렬의 꼴을 띈다. 가변 크기의 버킷을 사용하면 버킷 정렬의 공간복잡도는 O(M) 대신 O(n)이 된다.

두 개의 버킷을 사용하는 버킷 정렬은 피벗 값을 항상 값 범위의 중간 값으로 선택하는 퀵 정렬과 같은 효과이다. 균등 분포하는 입력에 효과적이지만, 클러스터링에 상대적으로 취약해 진다.

n- way 합병 정렬은 전체 항목을 n개의 부분배열로 나누고 각각을 정렬하는 것으로 시작한다. 그러나 합병 정렬이 생성하는 부분배열은 부분배열 사이에 겹치는 범위를 공유하기 때문에 버킷 정렬처럼 간단하게 이어붙일 수 없고, 병합 알고리즘을 사용해야 한다. 그러나 이런 비용을 더 치르는 대신 분산 단계가 더 간단해 지고 부분배열의 크기가 동일한 것이 보장되어 최악의 경우에 더 좋은 성능을 제공한다.

하향식 기수 정렬은 값의 범위와 버킷 수가 모두 2의 제곱으로 제한되는 버킷 정렬의 특수한 경우로 볼 수 있다. 결과적으로 각 버킷의 크기도 2의 거듭 제곱이며 재귀적으로 적용할 수 있다. 각 원소의 비트 표현의 접두사만으로 버킷을 결정할 수 있어 분산 단계를 가속할 수 있다.

참고 문헌 

 Paul E. Black "Postman 's Sort"( NIST 알고리즘 및 자료 구조 사전) .
 Robert Ramey ' "The Postman 's Sort" C Users Journal 1992년 8월
 NIST 알고리즘 및 자료 구조 사전 : 버킷 정렬

외부 링크 
 Ansi C 버킷 정렬 코드
 버킷 정렬의 변종 별 예제

정렬 알고리즘
안정 정렬