버킷 정렬

버킷 정렬
분류	정렬 알고리즘
자료 구조	배열
최악 시간복잡도
평균 시간복잡도	, k는 버킷 수. .
공간복잡도

버킷 정렬(bucket 整列), 버킷 소트(bucket sort)는 배열의 원소를 여러 버킷으로 분산하여 작동하는 정렬 알고리즘이다. 버킷은 빈(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 이면 (피벗 선택이 나쁜) 퀵 정렬과 동등하다.

분석

최악 시간 복잡도

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

평균 시간 복잡도

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

{\begin{aligned}E(n_{i}^{2})&=E\left(\sum _{j=1}^{n}X_{ij}\sum _{k=1}^{n}X_{ik}\right)\\&=E\left(\sum _{j=1}^{n}\sum _{k=1}^{n}X_{ij}X_{ik}\right)\\&=E\left(\sum _{j=1}^{n}X_{ij}^{2}\right)+E\left(\sum _{1\leq j,k\leq n}\sum _{j\neq k}X_{ij}X_{ik}\right)\end{aligned}}

마지막 줄은 $j=k$ 인 경우와 $j\neq k$ 인 경우를 나누어 각각 합산한다. 각 원소가 버킷 $i$ 에 들어갈 확률은 $1/k$ 이므로, $X_{ij}$ 은 $1/k$ 확률로 1, 아니면 0이다.

E(X_{ij}^{2})=1^{2}\cdot \left({\frac {1}{k}}\right)+0^{2}\cdot \left(1-{\frac {1}{k}}\right)={\frac {1}{k}}

E(X_{ij}X_{ik})=1\cdot \left({\frac {1}{k}}\right)\left({\frac {1}{k}}\right)={\frac {1}{k^{2}}}

적용하면

E\left(\sum _{j=1}^{n}X_{ij}^{2}\right)+E\left(\sum _{1\leq j,k\leq n}\sum _{j\neq k}X_{ij}X_{ik}\right)=n\cdot {\frac {1}{k}}+n(n-1)\cdot {\frac {1}{k^{2}}}={\frac {n^{2}+nk-n}{k^{2}}}

마지막으로 복잡도는 $O\left(\sum _{i=1}^{k}E(n_{i}^{2})\right)=O\left(\sum _{i=1}^{k}{\frac {n^{2}+nk-n}{k^{2}}}\right)=O\left({\frac {n^{2}}{k}}+n\right)$ .

마지막 단계로 각 버킷을 연결하는 데는 $O(k)$ 시간이 든다. 따라서 총 복잡도는 $O\left(n+{\frac {n^{2}}{k}}+k\right)$ 이다. 균등 분포에서 k를 $k=\Theta (n)$ 로 고르면 평균 시간 $O(n)$ 에 수행됨에 유의하라.^[1]

최적화

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

종류

일반 버킷 정렬

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

프록스맵 정렬

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

히스토그램 정렬

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

우체부 정렬

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

셔플 정렬

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

다른 정렬 알고리즘과 비교

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

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

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

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

참고 문헌

↑ ^가 ^나 Thomas H. Cormen; Charles E. Leiserson; Ronald L. Rivest & Clifford Stein. 《Introduction to Algorithms》. Bucket sort runs in linear time on the average. Like counting sort, bucket sort is fast because it assumes something about the input. Whereas counting sort assumes that the input consists of integers in a small range, bucket sort assumes that the input is generated by a random process that distributes elements uniformly over the interval [0,1). The idea of bucket sort is to divide the interval [0, 1) into n equal-sized subintervals, or buckets, and then distribute the n input numbers into the buckets. Since the inputs are uniformly distributed over [0, 1), we don't expect many numbers to fall into each bucket. To produce the output, we simply sort the numbers in each bucket and then go through the buckets in order, listing the elements in each.
↑ Corwin, E. and Logar, A. "Sorting in linear time — variations on the bucket sort".
↑ Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein.
↑ NIST's Dictionary of Algorithms and Data Structures: histogram sort
↑ http://www.rrsd.com/psort/cuj/cuj.htm
↑ A revolutionary new sort from John Cohen Nov 26, 1997

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

외부 링크

[lfcs-1] 가 ^나 Thomas H. Cormen; Charles E. Leiserson; Ronald L. Rivest & Clifford Stein. 《Introduction to Algorithms》. Bucket sort runs in linear time on the average. Like counting sort, bucket sort is fast because it assumes something about the input. Whereas counting sort assumes that the input consists of integers in a small range, bucket sort assumes that the input is generated by a random process that distributes elements uniformly over the interval [0,1). The idea of bucket sort is to divide the interval [0, 1) into n equal-sized subintervals, or buckets, and then distribute the n input numbers into the buckets. Since the inputs are uniformly distributed over [0, 1), we don't expect many numbers to fall into each bucket. To produce the output, we simply sort the numbers in each bucket and then go through the buckets in order, listing the elements in each.

[2] Corwin, E. and Logar, A. "Sorting in linear time — variations on the bucket sort".

[3] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein.

[4] NIST's Dictionary of Algorithms and Data Structures: histogram sort

[5] ttp://www.rrsd.com/psort/cuj/cuj.htm

[6] A revolutionary new sort from John Cohen Nov 26, 1997

[1]

[2]

[3]

[4]

[5]

[6]