버킷 정렬 문서 원본 보기

{{위키데이터 속성 추적}}
{{알고리즘 정보|class=[[정렬 알고리즘]]|image=|data=[[배열]]|time=<math>O(n^2)</math>|average-time=<math>O(n+\frac{n^2}{k}+k)</math>, k는 버킷 수. <math>O(n), \text {when } k \approx n</math>.|space=<math>O(n\cdot k)</math>}}
[[파일:Bucket_sort_1.svg|오른쪽|프레임| 먼저 버킷마다 원소를 나누어 넣는다. ]]
[[파일:Bucket_sort_2.svg|오른쪽|프레임| 다음으로 버킷 안에서도 각 원소를 정렬한다. ]]
'''버킷 정렬'''(bucket 整列), '''버킷 소트'''({{Lang|en|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'' 이면 (피벗 선택이 나쁜) [[퀵 정렬]]과 동등하다.

== 분석 ==

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

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

: <math>\begin{align}
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{align} </math>

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

: <math>E(X_{ij}^2) = 1^2\cdot \left(\frac{1}{k}\right) + 0^2\cdot \left(1-\frac{1}{k}\right) = \frac{1}{k}</math>
: <math>E(X_{ij}X_{ik}) = 1\cdot \left(\frac{1}{k}\right)\left(\frac{1}{k}\right) = \frac{1}{k^2} </math>

적용하면

: <math>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}</math>

마지막으로 복잡도는<math>O\left(\sum_{i=1}^kE(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) </math> .

마지막 단계로 각 버킷을 '''연결'''하는 데는 <math>O(k)</math> 시간이 든다. 따라서 총 복잡도는 <math>O\left(n+\frac{n^2}{k}+k\right)</math>이다. 균등 분포에서 k를 <math>k = \Theta(n)</math>로 고르면 평균 시간 <math>O(n)</math>에 수행됨에 유의하라.<ref name="lfcs">{{서적 인용|제목=[[Introduction to Algorithms]]|성=Thomas H. Cormen|저자링크=Thomas H. Cormen|성2=Charles E. Leiserson|저자링크2=Charles E. Leiserson|인용문=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.|저자앰퍼샌드=yes|성3=Ronald L. Rivest|저자링크3=Ronald L. Rivest|성4=Clifford Stein|저자링크4=Clifford Stein}}</ref>

== 최적화 ==
일반적인 최적화로는 버킷을 정렬되지 않은 채로 ''먼저'' 원래 배열에 돌려 넣은 다음 전체 배열에 대해 [[삽입 정렬]]을 수행한다. 삽입 정렬의 실행시간은 각 원소가 마지막에 정렬된 위치에서 떨어진 거리에 의해 결정되므로 상대적으로 적은 비교 연산을 하게 된다. 원소의 리스트가 메모리에 연속적으로 저장되므로 메모리 계층 구조도 더 잘 활용된다.<ref>Corwin, E. and Logar, A. "Sorting in linear time — variations on the bucket sort".</ref>

== 종류 ==

=== 일반 버킷 정렬 ===
버킷 정렬의 가장 일반적인 형태는 0부터 최대 값 ''M'' 사이의 수를 각각의 크기가 ''M''/''n''인 ''n''개의 버킷으로 나누는 것이다. 각 버킷이 [[삽입 정렬]]을 사용하면 [[삽입 정렬|정렬]] 되면 선형 시간의 기대값으로 수행되는 것처럼 보인다. (모든 입력에 대해 평균을 취할 경우).<ref>[[Thomas H. Cormen]], [[Charles E. Leiserson]], [[Ronald L. Rivest]], and [[Clifford Stein]].</ref> 그러나 많은 값이 서로 인접해 있으면 클러스터를 이루었다고 하며 모두 단일 버킷으로 들어갈 수 있어 성능이 저하된다. 원래의 버킷 정렬 알고리즘은 ''[0,1)'' 구간에서 무작위로 발생시킨 값을 입력으로 취한다고 가정하여 이런 성능저하를 회피하였다.<ref name="lfcs">{{서적 인용|제목=[[Introduction to Algorithms]]|성=Thomas H. Cormen|저자링크=Thomas H. Cormen|성2=Charles E. Leiserson|저자링크2=Charles E. Leiserson|인용문=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.|저자앰퍼샌드=yes|성3=Ronald L. Rivest|저자링크3=Ronald L. Rivest|성4=Clifford Stein|저자링크4=Clifford Stein}}</ref>

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

=== 히스토그램 정렬 ===
히스토그램 정렬 또는 [[계수 정렬]]은 계수 배열을 이용해 각 버킷에 들어갈 원소의 수를 세는 초기화 단계를 추가한다. 이 정보를 이용하면 배열 원소들은 버킷 순서에 따라 위치 교환만으로 정렬할 수 있으므로 버킷에 따로 메모리를 할당하지 않아 공간 오버 헤드가 제거된다.<ref>[https://xlinux.nist.gov/dads/HTML/histogramSort.html NIST's Dictionary of Algorithms and Data Structures: histogram sort]</ref>

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

=== 셔플 정렬 ===
'''셔플 정렬'''<ref>[https://groups.google.com/group/fido7.ru.algorithms/msg/26084cdb04008ab3 A revolutionary new sort from John Cohen Nov 26, 1997]</ref> 은 정렬할 항목 ''n''개 가운데 첫 1/8을 제거하고 재귀적으로 정렬하여 새 배열에 넣는 것으로 시작한다. 이 방법으로 n/8개의 버킷을 하여 나머지 7/8을 분산시켜 넣을 버킷을 생성하고, 각 버킷은 정렬된 배열로 연결된다.

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

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

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

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

== 참고 문헌 ==
<references />

* Paul E. Black [https://xlinux.nist.gov/dads/HTML/postmansort.html "Postman 's Sort"(] [[미국 국립표준기술연구소|NIST]] 알고리즘 및 자료 구조 사전) .
* Robert Ramey [http://www.rrsd.com/software_development/postmans_sort/cuj/cuj.htm ' "The Postman 's Sort"] ''C Users Journal'' 1992년 8월
* [https://xlinux.nist.gov/dads/HTML/bucketsort.html NIST 알고리즘 및 자료 구조 사전 : 버킷 정렬]

== 외부 링크 ==
* [http://www.dcc.uchile.cl/~rbaeza/handbook/algs/4/423.sort.c.html Ansi C 버킷 정렬 코드]
* [http://www1bpt.bridgeport.edu/~dichter/lilly/bucketsort.htm 버킷 정렬의 변종 별 예제]

{{정렬 알고리즘}}

[[분류:정렬 알고리즘]]
[[분류:안정 정렬]]