버킷 정렬

버킷 정렬
클래스	정렬 알고리즘
데이터 구조	배열
최악의 경우 공연
평균 공연	+ + ) 여기서 k는 버킷 수입니다. ( )는 일 때 입니다
최악의 경우 공간 복잡성

원소들은 쓰레기통들 사이에 분포되어 있다.

그런 다음 각 빈에 요소를 정렬한다.

버킷 정렬 또는 빈 정렬은 배열의 요소를 여러 버킷으로 분산시켜 작동하는 정렬 알고리즘이다. 그런 다음 각 버킷은 다른 정렬 알고리즘을 사용하거나 버킷 정렬 알고리즘을 재귀적으로 적용하여 개별적으로 정렬된다. 버킷당 여러 개의 키가 가능한 비둘기구멍 종류를 일반화한 유통종류로, 라딕스 계열의 사촌동생으로 가장 많은 양의 자릿수 맛을 낸다. 버킷 정렬은 비교를 통해 구현될 수 있으므로 비교 정렬 알고리즘으로도 간주할 수 있다. 계산 복잡성은 각 버킷을 정렬하는 데 사용되는 알고리즘, 사용할 버킷의 수, 입력이 균일하게 분포되어 있는지 여부에 따라 달라진다.

버킷 정렬은 다음과 같이 작동한다.

처음에 비어 있는 "버킷" 배열을 설정하십시오.
산점: 각 개체를 버킷에 넣고 원래 어레이를 검토하십시오.
비어 있지 않은 각 버킷을 정렬하십시오.
수집: 순서대로 버킷을 방문하여 모든 요소를 원래 어레이에 다시 넣으십시오.

가성음

함수 buketSort(array, k)는 버킷 새 배열 k 빈 목록 M ← 새 배열 i = 0 ~ 길이(array)에 대해 배열[i]를 버킷에 삽입함 i = 0 ~ k do nextSort(bukets[i])에 대해 배합[0], ...., 버킷[k]을 반환함수

배열은 정렬할 배열을 나타내고 k는 사용할 버킷 수를 표시한다. 모든 키를 한 번 반복하여 최대 키 값 선형 시간을 계산할 수 있다. 플로어 함수는 부동수를 정수로 변환하는 데 사용되어야 한다(그리고 데이터 유형의 캐스팅도 가능하다). nextSort 기능은 각 버킷을 정렬하는 데 사용되는 정렬 기능이다. 일반적으로 삽입 정렬을 사용하지만 선택 정렬 또는 병합 정렬과 같은 다른 알고리즘도 사용할 수 있다. buckSort 자체를 nextSort로 사용하면 radix 분류의 상대적 요소가 생성되며, 특히 사례 n = 2는 퀵소트(피벗 선택이 미비할 가능성이 있지만)에 해당한다.

분석

최악의 경우 분석

입력에 서로 가까운 여러 개의 키(클러스터링)가 포함된 경우, 그러한 요소는 동일한 버킷에 배치될 가능성이 높으며, 이로 인해 일부 버킷은 평균보다 많은 요소를 포함하게 된다. 최악의 시나리오는 모든 요소를 하나의 버킷에 넣을 때 발생한다. 그런 다음 $O(n^{2})$ 성능은 각 버킷을 정렬하는 데 사용되는 알고리즘(예: O $O(n^{2})$ ( n $O(n^{2})$ ) ${\displaystyle$ O ( $n^{2})$ 삽입 $O(n^{2})$ 정렬 또는 O ( $O(n\log(n))$ log $O(n\log(n))$ ) ${\displaystyle O(n\log(n)})$ 비교 $O(n\log(n))$ 정렬 알고리즘(예: 병합 정렬)이 지배하게 된다.

평균 사례 분석

입력 내용이 균일하게 분포된 경우를 고려하십시오. 버킷을 초기화하고 어레이에서 최대 키 값을 찾는 첫 번째 단계는 $O(n)$ ( $O(n)$ ) ${\displaystyle$ O $(n)}$ 번으로 $O(n)$ 수행할 수 있다. If division and multiplication can be done in constant time, then scattering each element to its bucket also costs $O(n)$ . Assume insertion sort is used to sort each bucket, then the third step costs $O(\textstyle \sum _{i=1}^{k}\displaystyle n_{i}^{2})$ , where $n_{i}$ ${\$ 은 $n_{i}$ (는) 버킷 $인덱싱된$ i {\ $displaystyle$ i}의 길이인데 $i$ 평균 시간에 관한 것이므로 기대 $E(n_{i}^{2})$ ( $E(n_{i}^{2})$ $E(n_{i}^{2})$ $){\displaystyle E(n_{i}^{2})$ 를 대신 평가해야 한다 $E(n_{i}^{2})$ . 요소 $j$ $j$ 이 $(가)$ $버킷$ i ${\displaystyle$ $i$ $i$ 에 $0$ 되어 $0$ 있으면 $1$ $j$ $X_{ij}$ $X_{ij}$ $X_{ij}$ {\ $displaystyle$ X_{ij $}}$ 를 1인 랜덤 변수가 되도록 $X_{ij}$ 한다 $.$ $n_{i}=\sum _{j=1}^{n}X_{ij}$ 는 n $n_{i}=\sum _{j=1}^{n}X_{ij}$ = $n_{i}=\sum _{j=1}^{n}X_{ij}$ j $n_{i}=\sum _{j=1}^{n}X_{ij}$ = $n_{i}=\sum _{j=1}^{n}X_{ij}$ X $n_{i}=\sum _{j=1}^{n}X_{ij}$ $n_{i}=\sum _{j=1}^{n}X_{ij}$ ${\$ 을(를) 가지고 있다 $n_{i}=\sum _{j=1}^{n}X_{ij}$ 그러므로

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

마지막 줄은 $j=k$ j $j=k$ = $j=k$ $j=k$ 과 $j=k$ 사례 $j\neq k$ $j\neq k$ $j\neq k$ ${\displaystyle$ $j$ $\neq$ k $}$ 로 합계를 구분한다 $j\neq k$ 물체가 $버킷$ i{\ $displaystyle$ $i$ }에 분산될 $1/k$ 은 $i$ $1/k$ / $1/k$ k {\ $displaystyle$ $1/k$ i $1/k$ $X_{ij}$ 은 $X_{ij}$ $1/k$ 1 $1/k$ / ${\displaystystystystytype$ }이다. $그렇지 않으면$ 1 $/$ k}과 $1/k$ 0이다.

E(X_{ij}^{2})=1^{2}\cdot \왼쪽({\frac {1}{k}\오른쪽)+0^{2}\cdot \left(1-{\frac {1}{k}\오른쪽)={\frac {1}{k}}}}}}}}}}}}}}

E(X_{ij}X_{ik}=1\cdot \왼쪽({\frac {1}{k}\오른쪽)\왼쪽({\frac {1}{k}\오른쪽)={\frac {1}{1}{k^{2}}:

합계가 되면, 그렇게 될 것이다.

E\left(\sum _{j=1}^{n}X_{ij}^{2}\오른쪽)++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 $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)$ i = $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\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\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\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)$ i $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 $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)$ i = $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)$ k $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\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)$ k - $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\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)$ 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\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\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)$ 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\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\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)$ {\ $displaysty O\left(\sum _{i=1}^{$ i}^{2}) $E($ 가 될 것이다. $O\left(\sum _{i=1}^{k}{\frac {n^{2}+nk-n}{k^{2}}\오른쪽)=$ $O\왼쪽({\frac{n^{2}}:{k}+n\오른쪽)}$ .

각 버킷의 정렬된 모든 객체를 연결하는 버킷 정렬의 마지막 단계에는 $O(k)$ $O(k)$ $O(k)$ 시간이 $O(k)$ 필요하다. 따라서 총 복잡도는 $O\left(n+{\frac {n^{2}}{k}}+k\right)$ + n $O\left(n+{\frac {n^{2}}{k}}+k\right)$ $O\left(n+{\frac {n^{2}}{k}}+k\right)$ + k $O\left(n+{\frac {n^{2}}{k}}+k\right)$ ) ${\$ $k=\Theta (n)$ 를 k $k=\Theta (n)$ = $k=\Theta (n)$ $k=\Theta (n)$ ${\displaystyle$ k $=\)$ 로 선택한 경우 유의하십시오. $Theta (n)}$ , 그리고 버킷 정렬은 균일하게 분산된 입력을 주어진 $O(n)$ ( $O(n)$ ) $O(n)$ 평균 시간으로 $O(n)$ 실행된다.^[1]

최적화

일반적인 최적화는 먼저 버킷의 정렬되지 않은 요소를 원래 어레이에 다시 넣은 다음 전체 어레이에 걸쳐 삽입 정렬을 실행하는 것이다. 삽입 정렬의 런타임은 각 요소가 최종 위치로부터 얼마나 멀리 떨어져 있는지 기반으로 하기 때문에 비교 횟수는 상대적으로 적고 메모리 계층은 스토리지에 의해 더 잘 활용된다.그 목록을 계속 기억에 남는다.^[2]

입력 분포를 알거나 추정할 수 있는 경우 버킷은 종종 일정한 밀도를 가진 버킷을 선택할 수 있다(단순히 크기가 일정하지 않음). 이렇게 하면 균일하게 분산된 입력이 없어도 $O(n)$ ( $O(n)$ $O(n)$ $O(n)$ 의 $O(n)$ 평균 시간 복잡성이 허용된다.

변형

일반 버킷 정렬

버킷 정렬의 가장 일반적인 변형은 0과 일부 최대값 M 사이의 n개의 숫자 입력 목록에서 작동하며 값 범위를 각각 크기 M/n의 n개의 버킷으로 나눈다. 각 버킷을 삽입 정렬을 사용하여 정렬하면 예상 선형 시간(가능한 모든 입력에 대해 평균을 취함)^[3]에 해당 정렬이 실행되는 것을 보여줄 수 있다. 그러나 이러한 종류의 성능은 클러스터링과 함께 저하된다. 많은 값이 가까이서 발생하면 모두 하나의 버킷으로 떨어져 천천히 정렬될 것이다. 이 성능 저하는 원래 버킷 정렬 알고리즘에서 [0,1] 간격에 걸쳐 균일하게 요소를 분배하는 임의의 프로세스에 의해 입력이 생성된다고 가정함으로써 피한다.^[1]

프록시맵소트

위에서 설명한 일반적인 버킷 정렬과 유사하게, ProxmapSort는 키의 부분 순서를 보존하는 "맵 키" 함수를 사용하여 키 배열을 하위 배열로 나누는 방식으로 작동한다. 각 키가 하위 배열로 추가됨에 따라 삽입 정렬을 사용하여 해당 하위 배열의 정렬 상태를 유지함으로써, Proxma가 정렬될 때 전체 배열이 정렬되도록 한다.pSort 완료. ProxymapSort는 데이터를 정렬된 순서로 배치하여 "프록스맵" 즉, 근접 매핑을 생성하기 위해 맵 키를 사용하는 버킷 소트와는 다르다.

히스토그램 정렬

히스토그램 정렬 또는 카운팅 정렬로 알려진 버킷 정렬의 또 다른 변종은 카운트 배열을 사용하여 각 버킷에 포함될 요소의 수를 카운트하는 초기 패스를 추가한다.^[4] 이 정보를 사용하면 일련의 교환에 의해 배열 값을 내 버킷의 순서로 배열할 수 있어 버킷 저장소의 공간 오버헤드가 남지 않는다.^{[failed verification]}

우편배달부

포스트맨의 분류는 버킷 분류의 변형으로서, 일반적으로 속성 집합에 의해 설명되는 요소의 계층 구조를 이용한다. 우체국에서 편지 소트기가 사용하는 알고리즘이다: 우편물은 국내와 국제 간 먼저 분류되고, 주, 지방 또는 영토별로 분류되며, 그 다음엔 목적지 우체국별로, 그 다음엔 노선별로 분류된다. 키가 서로 비교되지 않기 때문에 정렬 시간은 O(cn)이며 여기서 c는 키의 크기와 버킷 수에 따라 달라진다. 이것은 "top down" 또는 "most imple digital first"^[5]로 작동하는 radix 분류와 유사하다.

순서 섞기 정렬

shuffle sort는^[6] 정렬할 n개의 항목 중 처음 1/8을 제거하고 재귀적으로 정렬하여 배열하는 것으로 시작하는 버킷 정렬의 변형이다. 이렇게 하면 항목의 나머지 7/8이 분배되는 n/8 "버킷"이 생성된다. 그런 다음 각 "버킷"을 정렬하고 "버킷"을 정렬된 배열로 연결한다.

다른 정렬 알고리즘과 비교

버킷 정렬은 카운트 정렬의 일반화로 볼 수 있다. 실제로 각 버킷의 크기가 1이면 버킷 정렬은 카운트 정렬로 변질된다. 버킷 정렬의 가변 버킷 크기는 O(M) 메모리 대신 O(n) 메모리를 사용할 수 있게 하는데, 여기서 M은 구별되는 값의 수입니다. 대신, Sort의 O(n + M) 최악의 경우 동작을 계산하는 것을 포기한다.

두 버킷으로 정렬하는 버킷은 사실상 피벗 값이 항상 값 범위의 중간 값으로 선택되는 퀵소트의 버전이다. 이 선택은 균일하게 분포된 입력에 효과적이지만, 임의로 선택한 피벗과 같은 빠른 정렬에서 피벗을 선택하는 다른 수단은 입력 분포의 군집화에 대한 내성을 높인다.

n-way 병합 알고리즘도 목록을 n개의 하위 목록으로 분산하고 각각의 하위 목록으로 정렬하는 것으로 시작하지만, 병합에 의해 생성된 하위 목록에는 중복되는 값 범위가 있으므로 버킷 정렬과 같이 단순 결합으로 재결합할 수 없다. 대신 병합 알고리즘에 의해 인터리브되어야 한다. 그러나 이러한 추가 비용은 보다 단순한 분산 단계와 각 하위 목록의 크기가 동일하도록 보장할 수 있는 능력에 의해 균형을 이루며, 최악의 경우 시간 제한을 제공한다.

하향식 라딕스 정렬은 값의 범위와 버킷 수가 모두 2의 검정력으로 제한되는 버킷 정렬의 특별한 경우로 볼 수 있다. 결과적으로 각 버킷의 크기 또한 2의 힘이 되며, 그 절차는 반복적으로 적용될 수 있다. 이 접근법은 버킷을 결정하기 위해 각 원소의 비트 표현 접두사만 검토하면 되기 때문에 산란 단계를 가속화할 수 있다.

참조

^ ^a ^b 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., Logar, A. "선형으로 정렬 - 버킷 정렬의 변형" 대학 전산학 저널, 20, 1, 페이지 197–202. 2004년 10월.
^ 토마스 H. 코멘, 찰스 E. Leiserson, Ronald L. Rivest, Clifford Stein. 알고리즘 소개, Second Edition. MIT 프레스 앤 맥그로우 힐, 2001. ISBN 0-262-03293-7 제8.4절: 버킷 정렬, 페이지 174–177.
^ NIST 알고리즘 및 데이터 구조 사전: 히스토그램 정렬
^ http://www.rrsd.com/psort/cuj/cuj.htm
^ 1997년 11월 26일 존 코헨의 혁명적인 새로운 종류

NIST 알고리즘 및 데이터 구조 사전의 Paul E. Black "Postman's Sort"
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., Logar, A. "선형으로 정렬 - 버킷 정렬의 변형" 대학 전산학 저널, 20, 1, 페이지 197–202. 2004년 10월.

[3] 토마스 H. 코멘, 찰스 E. Leiserson, Ronald L. Rivest, Clifford Stein. 알고리즘 소개, Second Edition. MIT 프레스 앤 맥그로우 힐, 2001. ISBN 0-262-03293-7 제8.4절: 버킷 정렬, 페이지 174–177.

[4] NIST 알고리즘 및 데이터 구조 사전: 히스토그램 정렬

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

[6] 1997년 11월 26일 존 코헨의 혁명적인 새로운 종류

[1]

[2]

[3]

[4]

[5]

[6]

v t 정렬 알고리즘
이론	계산 복잡성 이론 빅 O 표기법 총순번 목록 배치 안정성 비교 정렬 적응 정렬 정렬 네트워크 정수 정렬 X + Y 정렬 트랜스디코토머스 모형 양자 분류
Exchange sort	버블 정렬 칵테일 셰이커 분류 홀수-짝수 정렬 콤 정렬 Gnome sort 비율 확장 정렬 퀵소트 슬로우토트 스투지 분류 보고소트
선택 정렬	선택 정렬 힙스포트 스무스소트 데카르트 트리 정렬 토너먼트 정렬 사이클 정렬 약한 heap 분류
삽입 정렬	삽입 정렬 조개류 스플레이소트 트리 정렬 라이브러리 정렬 인내 정렬
정렬 병합	병합 정렬 계단식 병합 정렬 병합 정렬 진동 다상 병합 정렬
분포 정렬	미국 국기 종류 비드 정렬 버킷 정렬 버스토트 카운팅 정렬 보간 정렬 비둘기홀 정렬 프록시맵 정렬 라딕스 분류 플래시소트
동시 정렬	비토닉 정렬기 배처 홀수-짝수 병합 쌍방향 정렬 네트워크 샘플포트
잡종류	병합 정렬 차단 커크패트릭-레이시 분류 팀소트 인트로소트 스프레스포트 병합 삽입 정렬
기타	위상 분류 위상전순서 팬케이크 분류 스파게티 종류

Search