셸 정렬

셸 정렬

갭 23, 10, 4, 1이 있는 조개껍질
클래스	정렬 알고리즘
데이터 구조	배열
최악의 경우 공연	O(n2) (최악의 경우 간격 시퀀스 중 가장 좋지 않은 것으로 알려져 있음) O(n logn2)(가장 잘 알려진 최악의 경우 간격 시퀀스)[1]
베스트 케이스 공연	O(n log n)(최대 간격 시퀀스) O(n logn2)(가장 잘 알려진 최악의 경우 간격 시퀀스)[2]
평균 공연	갭 순서에 따라 다름
최악의 경우 공간 복잡성	оCOB(n) 합계, O(1) 보조

Shellort의 연속된 단계에서 간격 5, 3, 1과 항목 쌍 교환

Shell sort 또는 Shell의 방법으로도 알려진 Shellort는 인플레이스 비교 sort이다.교환(버블 분류)에 의한 분류의 일반화 또는 삽입에 의한 분류(삽입 분류)로 볼 수 있다.^[3]이 방법은 원소 쌍을 서로 멀리 떨어져 정렬하는 것으로 시작하여, 점차적으로 비교할 원소 사이의 간격을 줄인다.멀리 떨어져 있는 요소들로 시작함으로써, 그것은 몇몇 외부 요소들을 간단한 가장 가까운 이웃 교환보다 더 빨리 제자리에 옮길 수 있다.도날드 셸은 1959년에 이런 종류의 첫 번째 버전을 출판했다.^[4][5]Shellsort의 러닝 시간은 사용하는 갭 순서에 따라 크게 좌우된다.많은 실제 변종에서 시간 복잡성을 결정하는 것은 여전히 공공연한 문제로 남아 있다.

설명

Shellsort는 멀리 떨어져 있는 아이템을 교환할 수 있는 삽입 종류를 최적화한 것이다.그 아이디어는 요소들의 목록을 배열하여 어디에서나 모든 요소들을 취하면 정렬된 리스트가 생성되도록 하는 것이다.그런 명단은 일그러진 것이라고 한다.그것은 또한 각각 개별적으로 분류된 인터리브 리스트라고 생각할 수 있다.^[6]h의 큰 값으로 시작하면 원소들이 원래 리스트에서 먼 거리를 이동할 수 있고, 많은 양의 장애를 빠르게 감소시키며, 더 작은 h-sort 단계가 할 수 있는 일은 더 적게 남는다.^[7]더 작은 정수 k에 대해 목록을 k-sort한 경우 리스트는 h-sort로 유지된다.1로 끝나는 h 값의 감소 순서에 대한 이러한 생각에 따라 결국 정렬된 목록을 남길 수 있다.^[6]

간단히 말해서, 이것은 우리가 1024개의 숫자를 배열한다면, 우리의 첫 번째 간격(h)은 512가 될 수 있다는 것을 의미한다.그런 다음 전반부의 각 원소와 후반부의 원소를 비교하여 목록을 훑어본다.우리의 두 번째 격차(k)는 256으로 배열을 4개 구간(0256,512,768부터)으로 나누며, 각 구간의 첫 번째 항목이 서로 상대적으로 정렬되고, 그 다음 각 구간의 두 번째 항목이 정렬되도록 한다.실제로 갭 시퀀스는 무엇이든 될 수 있지만, 마지막 갭은 항상 1로 분류(일반적인 삽입 정렬로 효과적으로 마무리)한다.

갭 5, 3, 1이 있는 Shellsort의 실행 예는 아래와 같다.

첫 번째 패스인 5-소트링은 5개의 별도 서브선(a₁, a, a₆₁₁, a), (a₂₁₂₃, a₇, a), (a₈₉, a), (a₄₁₀, a), (a₅, a)에 대해 삽입 정렬을 수행한다.예를 들어 서브 어레이(a₁, a₆, a, a₁₁)를 (62, 17, 25)에서 (17, 25, 62)로 변경한다.다음 패스인 3-소트링은 3개의 서브어레이(a₁, a₄, a, a₇, a₁₀), (a₂, a₅, a₈, a₁₁), (a₃, a₆, a₉, a₁₂)에 삽입 정렬을 수행한다.마지막 패스, 1-구문, 전체 배열(a₁,..., a₁₂)의 일반적인 삽입이다.

이 예에서 알 수 있듯이, Shellort가 운용하는 하위 선들은 처음에는 짧고, 나중에는 더 길지만 거의 주문된다.두 경우 모두 삽입 정렬이 효율적으로 작동한다.

쉘포트는 안정적이지 않다: 그것은 동일한 값을 가진 원소의 상대적 순서를 바꿀 수 있다.입력이 부분적으로 정렬되면 더 빨리 실행된다는 점에서 적응형 정렬 알고리즘이다.

가성음

내부 삽입 정렬과 함께 마르신 시우라의 간격 시퀀스를 사용한다.

# 배열 a[0...n-1]를 정렬하십시오. 틈새 = [701, 301, 132, 57, 23, 10, 4, 1]  // Ciura 갭 시퀀스  # 가장 큰 격차부터 시작해 1의 격차까지 내려간다. # 삽입 정렬과 유사하지만 1 대신 각 단계에서 공백이 사용됨 앞을 내다 (갭 에 틈새) {     # 틈새에 있는 모든 요소에 대해 가선 삽입 정렬 수행     # 각 간격 정렬에는 간격띄우기 인터리브 정렬(0..gap-1)이 포함된다.     을 위해 (상쇄하다 = 0; 상쇄하다 < 갭; 상쇄하다++)       을 위해 (i = 상쇄하다; i < n; i += 갭)       {           # 임시변통으로 a[i]를 아끼고 제자리에 구멍을 뚫는다.           임시 변통하다 = a[i]           # a[i]에 대한 올바른 위치가 발견될 때까지 이전의 갭 메우기 요소를 위로 이동           을 위해 (j = i; j >= 갭 그리고 a[j - 갭] > 임시 변통하다; j -= 갭)           {               a[j] = a[j - 갭]           }           # 온도(원래 a[i])를 정확한 위치에 배치           a[j] = 임시 변통하다        } } 

간격 시퀀스

어떤 갭 시퀀스를 사용할지 결정하는 문제는 어렵다.1을 포함하는 모든 갭 시퀀스는 정확한 정렬을 산출한다(이것이 최종 패스를 일반적인 삽입 정렬로 만들기 때문에). 그러나 이렇게 획득한 Shellsort 버전의 속성은 매우 다를 수 있다.간격이 너무 적으면 패스가 느려지고, 간격이 너무 많으면 오버헤드가 발생한다.

아래 표는 지금까지 발표된 대부분의 제안된 갭 시퀀스를 비교한다.이들 중 일부는 정렬된 배열의 크기(N)에 따라 달라지는 감소 요소를 가지고 있다.다른 이들은 무한 시퀀스를 증가시키고 있는데, 이 시퀀스는 N보다 작은 원소를 역순으로 사용해야 한다.

OEIS	일반용어(k 1 1)	콘크리트 틈새	최악의 경우 시간의 복잡성	작성자 및 발행연도
	${\displaystyle \left\lfloor {\frac {n}{2^{k}}\right\rfloor }$	${\displaystyle \left\lfloor {\frac {N}{2}}\right\rfloor,\frac {n}{4}\right\rfloor,\ldots,1}$	${\displaystyle \mathrm{\theta }}$(${\displaystyle {}^{}}$ ${\displaystyle {2\mathrm{}}^{}}$) ${\$N$^{2}\오른쪽)}$ [예:$$ N = 2p]	1959년[4] 셸
	${\displaystyle 2\좌측\l바닥 {\frac {N}{2^{k+1}}\오른쪽\rfloor +1}$	${\displaystyle 2\좌측\l바닥 {\frac {N}{4}\오른쪽\rfloor +1,\ldots,3,1}$	${\displaystyle \Theta \left(N^{\frac {3}{2}}\오른쪽)}$	프랭크 & 레자로스, 1960년[8]
A000225	${\displaystyle 2^{k}-1}$	${\displaystyle 1,3,7,15,31,63,\ldots }$	${\displaystyle \Theta \left(N^{\frac {3}{2}}\오른쪽)}$	히바드, 1963년[9]
A083318	${\displaystyle {}^{}\mathrm{2k}{}^{}}$+ 1 ${\displaystyle$ 2$^{k}+1$ 접두사 1	${\displaystyle 1,3,5,9,17,33,65,\ldots }$	${\displaystyle \Theta \left(N^{\frac {3}{2}}\오른쪽)}$	페이퍼노브 & 스타세비치, 1965년[10]
A003586	${\displaystyle {2p}^{}}$ ${\displaystyle {3q}^{}}$ ${\$3-smooth number) 양식의 연속 번호	${\displaystyle 1,2,3,4,6,8,9,12,\ldots }$	${\displaystyle \Theta \left(N\log ^{2}N\right)}$	프랫, 1971년[1]
A003462	${\displaystyle \frac{{3k}^{}}{}}$- ${\displaystyle \frac{1}{}}$ ${\displaystyle \frac{\mathrm{}}{}}$ ${\$$,{\displaystyle }$ N ${\displaystyle \frac{3}{}}$ ${\displaystyle \rceil }$ ${\$보다 크지 않음	${\displaystyle 1,4,13,40,190,\ldots }$	${\displaystyle \Theta \left(N^{\frac {3}{2}}\오른쪽)}$	크누스,[3] 1973년 프랫 기준 1971년[1]
A036569	${\displaystyle {\begin{aligned}&\prod \limits _{I}a_{q},{\hbox{where}}\\a_{0}={}&3\\a_{q}={}&\min \left\{n\in \mathbb {N} \colon n\geq \left({\frac {5}{2}}\right)^{q+1},\forall p\colon 0\leq p<q\Rightarrow \gcd(a_{p},n)=1\right\}\\I={}&\왼쪽\{0\leq q<r\mid q\neq {\1}{1}{1}:{1}2}}:\왼쪽(r^{2}+r\오른쪽)-k\right\}\r={}}}\sqrt{2k+}\sqrloor \{lineed}}}}}}}}}$	${\displaystyle 1,3,7,21,48,198,\ldots }$	${\displaystyle O\left(N^{1+{\sqrt {\frac {8\ln \left (5/2\오른쪽)}{\ln(N)}}}}}$	Incerpi & Sedgewick, 1985년,[11] Knuth[3]
A036562	${\displaystyle {4k}^{}}$+ ${\displaystyle 3}$ ${\displaystyle \cdot }$ ${\displaystyle {2k}^{}}$- ${\displaystyle 1{}^{}}$+ ${\displaystyle 1^{}}$ ${\displaystyle 4^{k}+3\cdot$ 2$^{k-1}+1$ 앞에 1이 있음	${\displaystyle 1,8,23,77,281,\ldots }$	${\displaystyle O\왼쪽(N^{\frac {4}{3}\오른쪽)}$	세지윅, 1982년[6]
A033622	${\displaystyle {\case}9\좌측(2^{k}-2^{\frac {k}{2}}\오른쪽)+1&k{{k}\cdot 2^{k}-6^{k}-cdot 2^{(k+1)/}+1&k{\cdext{}}}}이상한장면{}}}}}}}}}}}}}}}}}}}:{}}}}}}}}}}}}}}}:{}}}}}}}}}}}}}}}}}}}}$	${\displaystyle 1,5,19,41,41,7,\ldots }$	${\displaystyle O\왼쪽(N^{\frac {4}{3}\오른쪽)}$	세지윅, 1986[12]
	${\displaystyle h_{k}=\max \좌측\{\floor {5h_{k-1}-1}{11}}\우측\rfloor ,1\우측\}h_{0}=N}$	${\displaystyle \왼쪽\lfloor, {5N-1}{11}\오른쪽\rfloor,\왼쪽\lfloor{11}\frac {5N-1}{11}\오른쪽\rfloor,\ldots}$	알 수 없음	곤넷 & 배자 예이츠, 1991년[13]
A108870	${\displaystyle \left\lceil {\frac {1}{5}\왼쪽(9\cdot\frac {9}{4}\오른쪽)^{k-1}-4\right\rceil }}$	${\displaystyle 1,4,9,20,46,164,\ldots }$	알 수 없음	토쿠다, 1992년[14]
A102549	알 수 없음(실험적으로 파생됨)	${\displaystyle 1,4,10,23,57,197,190,701}$	알 수 없음	시우라, 2001년[15]

N의 이진 표현에 연속적인 0이 많이 포함되어 있을 때, Shell의 원래 갭 시퀀스를 이용한 Shellort는 최악의 경우 θ(N²) 비교를 한다.예를 들어, 이 경우는 중앙값보다 큰 원소와 작은 원소가 각각 홀수 및 짝수 위치를 차지할 때 2의 검정력과 같은 N에 대해 발생한다.

비교 분류에 최적인 O(N log N)보다 복잡도가 높지만, 프랫의 버전은 분류 네트워크에 자신을 빌려주고 배쳐의 바이톤 소러터와 같은 점증적 게이트 복잡성을 가지고 있다.

곤넷과 백자예이츠는 셸포트가 연이은 격차의 비율이 대략 2.2일 때 평균적으로 가장 적은 비교를 한다고 관측했다.^[13]이들의 순서는 비율 2.2, 도쿠다의 순서는 비율 2.25로 효율성이 입증된 이유다.그러나 왜 이런지는 알려지지 않았다.Sedgewick은 가장 큰 공통 디비저가 낮거나 쌍으로 짝을 이루는 간격을 사용할 것을 권장한다.^{[16][failed verification]}

평균 비교 횟수와 관련하여, Ciura의^[15] 시퀀스는 가장 잘 알려진 성능을 가지고 ${\displaystyle {있다}_{}}$; 701과의 간격은 결정되지 않았지만, 재귀 $공식{\displaystyle {}_{}}$ h${\displaystyle {}_{}}$= ${\displaystyle 2.25}$ ${\displaystyle h_{}}$ ${\displaystyle {}_{}}$- ${\displaystyle 1_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle h_{k}=\lfloor 2.25h_{k-1}\rfloor }$에 따라 시퀀스를 더 확장할 수 있다$.$

토쿠다의 순서는 ${\displaystyle {단순}_{}^{}}$ 공식 $h{\displaystyle {}_{}}$ ${\displaystyle k_{}}$=${\displaystyle {}_{}^{}}$ h k { ${\displaystyle \{}$ { { { ${$ {\$displaystyle h_{$k}=\$lceil h'_{$k}\$rceil$}에 ${\displaystyle \mathrm{의해}}$ 정의되며, ${\displaystyle {여기}_{}^{}}$서 $h{\displaystyle {}_{}^{}}$k${\displaystyle \mathrm{}{25}_{}^{}}$ = 2.${\displaystyle {25}_{}^{}}$h${\displaystyle {}_{}^{}}$-${\displaystyle }$1$$${\displaystyle 1}$ + 1 ${\displaystystyle h'_{k}=2$.$25h'_{k-1}+1$ ${\displaystyle \mathrm{h}}$ ${\displaystyle {1\mathrm{}}_{}^{}}$ ${\displaystyle {}_{}^{}}$= 1 ${\displaystyle h'_{1}=1}$를 실제 적용에 권장할 수 있다$.$

최대 입력 크기가 작을 경우, 퀵소트 또는 병합 정렬과 같은 다른 재귀적 정렬 알고리즘에 의해 작은 하위 Array에 Shellort를 사용할 경우, 각 입력 크기에 대한 최적의 시퀀스를 표로 작성할 수 있다.^[17]

계산 복잡성

다음 속성은 다음과 같다: 모든 배열의₁ 정렬₂ 후 배열은₁ 정렬 상태를 유지한다.^[18]모든 H형₁ 및 H형 배열은 음이₂ 아닌 정수 a와₁ a에₂ 대해서도 (아₁₁+a₂₂)형 배열이다.따라서 쉘포트의 최악의 복잡성은 프로베니우스 문제와 연관된다: 주어진 정수 h₁, ..., gcd_n = 1인 경우 프로베니우스 수 g(h₁,..., h_n)는 아+로₁₁ 나타낼 수 없는 최대 정수다.+ah_nn non-negative 정수₁ a_n,..., a. 프로베니우스 숫자에 대해 알려진 공식을 사용하여, 우리는 갭 시퀀스의 여러 등급에 대해 쉘포트의 최악의 복잡성을 결정할 수 있다.^[19]검증된 결과는 위 표에 나와 있다.

평균 작동 횟수와 관련하여 입증된 결과 중 실제 갭 순서와 관련된 것은 없다.2의 권력 공백 들어, Espelid 0.5349 NN로 0.4387 N− 0.097 N+O(1){\displaystyle 0.5349N{\sqrt{N}}-0.4387N-0.097{\sqrt{N}}+O(1)}− .[20]크누스 2N2h+π N3h{\displaystyle{\와 같이 두군데 빈곳(h, 1)을 가진 N-element 배열을 분류하는 평균 복잡도로 결심했다 이 평균을 계산했다.fra$c {2N^{2}}:{h}+{\sqrt{\pi N^{3}h$^[3] h = ((N^1/3)의 투패스 쉘포트가 평균 O(N^5/3) 비교/반복/런닝 시간을 만드는 데 따른 것이다.야오밍은 3패스 셸포트의 평균적인 복잡성을 발견했다.^[21]그의 결과 Janson과 크누스고 있N24ch+첫 단계에서 O(N){\displaystyle{\frac{N^{2}}{4ch}}+O(N)}, 18gπ ch(h− 1)N3/2+O(h. comparisons/inversions/running 평균 시간 많hg은 coprime 셸 정렬 3격차로(ch, cg, 1), 중에 이루어져[22]변모해 갔다 N)${\displaystyle {\frac {1}{8g}}{\sqrt {\frac {\pi }{ch}}}(h-1)N^{3/2}+O(hN)}$ in the second pass and ${\displaystyle \psi (h,g)N+{\frac {1}{8}}{\sqrt {\frac {\pi }{c}}}(c-1)N^{3/2}+O\left((c-1)gh^{1/2}N\right$$)+O\left(c^{2}g^{3}$h^{$2}\right)}$ 세 번째 패스의 경우$$.ψ(h, g) in the last formula is a complicated function asymptotically equal to ${\displaystyle {\sqrt {\frac {\pi h}{128}}}g+O\left(g^{-1/2}h^{1/2}\right)+$$O\좌(gh^{-1/2}\오른쪽$ 특히 h = θ(N^7/15)과 g = θ(N^1/5)일 때, 정렬의 평균 시간은 o(N^23/15)이다.

실험을 바탕으로 히바드의 갭 시퀀스를 가진 셸포트는 O(N5/4)평균 시간으로 운행되며,[3]곤넷과 배자예이츠의 시퀀스는 평균 0.41N ln N(ln N+1/6이기)이동해야 원소가하는 것으로 추측된다.[13]정렬된 배열들이 수백만 개의 요소를 포함할 때 이전에 다른 시퀀스에 대해 제시되었던 평균 연산 수의 근사치가 실패한다.

The graph below shows the average number of element comparisons in various variants of Shellsort, divided by the theoretical lower bound, i.e. log₂N!, where the sequence 1, 4, 10, 23, 57, 132, 301, 701 has been extended according to the formula ${\displaystyle h_{k}=\lfloor 2.25h_{k-1}\rfloor }$.

콜모고로프 복잡성 이론을 적용하여 장, 리, 비타니는 p-pass Shellsort: p ≤ logN일₂ 때 Ω(pN^1+1/p), p > logN일₂ 때 Ω(pN)의 평균 동작/실행 시간 순서에 대해 다음과 같은 하한을 증명하였다.따라서 Shellort는 배열 크기의 로그에 비례하여 갭 수가 증가하는 갭 시퀀스를 사용해야 N logN처럼 점증적으로 증가하는 평균 시간에 실행될 가능성이 있다.그러나 셸포트가 비교 분류에 최적인 평균 사례 복잡성의 이 점증적 순서에 도달할 수 있을지는 알 수 없다.어디 h0N{\displaystyle h_{0}=N}(N∑ k=1phk− 1/hkm그리고 4.9초 만){\displaystyle \Omega(N\sum_{k=1}^{p}h_{k-1}/h_{k})}Ω에{p\displaystyle}p은 하한 Vitányi[24]에 의해 패스의 모든. 이는 Jiang-Li-Vitányi 낮은 모든 p{\d으로 향하는 예를 들어 의미를 내포하고 개선되었다.isp$레이스타일 p}$ -통과 증분 시퀀스$$ 및 특정 증분 시퀀스에 대한 하한을 개선한다.실제로 현재 평균 사례로 알려진 모든 한계(하한과 상한)는 이 하한과 정확히 일치한다.예를 들어, 이것은 잰슨-크누스 상한이 사용된 증분 순서에 대한 결과 하한과 일치한다는 새로운 결과를 제공하며, 이 증분 순서에 대한 3개의 통과 쉘포트는 $\theta {\displaystyle \mathrm{}}$ ${\displaystyle ({}^{}}$ $23$) ${\displaystyle \Theta ({{23/15})}$ 비교$$/반복/실행 시간을 사용한다는 것을 보여준다.공식을 통해 알 수 없는 하한을 산출하는 증분 시퀀스를 검색할 수 있다. 예를 들어, $\Omega {\displaystyle \mathrm{}({p\mathrm{}}^{}}$1 +${\displaystyle 1^{}}$ /${\displaystyle {}^{}{p}^{}}$) = Ω${\displaystyle ({n\mathrm{}}^{}\mathrm{5}}$ /${\displaystyle {}^{}{4\mathrm{}}^{}}$ )$${\$displaystyle \Oomega(pn^{1+1/p})=\Oomega(n^{5/4})}$에서 증분 순서 h =${\displaystyle {}_{}{n\mathrm{}}_{}}$ ${\displaystyle {11}^{}}$/ ${\displaystyle {16}^{}}$을 검색할 수 있다.${\displaystyle {}^{}}$$,$ ${\displaystyle h_{1}=n^{11/16},}$ ${\displaystyle {h\mathrm{}}_{}}$ $2$${\displaystyle {}_{}}$= ${\displaystyle {n\mathrm{}}^{}}$ ${\displaystyle {}^{}}$/ ${\displaystyle {16}^{}}$ ${\displaystyle h_{2}=n^{7/16},}$ ${\displaystyle {h\mathrm{}}_{}}$ $3$${\displaystyle {}_{}}$= ${\displaystyle {n\mathrm{}}^{}}$ ${\displaystyle {}^{}}$/ ${\displaystyle {16}^{}}$ ${\displaysty h_{3}=16},$ ${\displaystyle 4_{}}$ =$$ {\$displaystyle h_h_{4}$The lower bound becomes ${\displaystyle T=\Omega (n\cdot (n^{1-11/16}+n^{11/16-7/16}+n^{7/16-3/16}+n^{3/16})=$$\Oomega(n^{1+5/16}}=$$\오메가(n^{21/16}).$$}$

The worst-case complexity of any version of Shellsort is of higher order: Plaxton, Poonen, and Suel showed that it grows at least as rapidly as ${\displaystyle \Omega \left(N\left({\log N \over \log \log N}\right)^{2}\right)}$.^[25][26]

적용들

Shellort는 퀵소트보다 더 많은 작업을 수행하고 캐시 미스 비율이 더 높다.그러나, 그것은 작은 코드를 사용하여 구현될 수 있고 콜 스택을 사용하지 않기 때문에, 임베디드 시스템을 대상으로 하는 C 표준 라이브러리의 qsort 기능의 일부 구현은 퀵소트 대신 그것을 사용한다.예를 들어 Shellsort는 uClibc 도서관에서 사용된다.^[27]비슷한 이유로 과거에 쉘포트는 리눅스 커널에서 사용되었다.^[28]

셸포트는 또한 내성적인 종류의 하위 알고리즘의 역할을 할 수 있으며, 짧은 서브레이를 분류하고, 재귀 깊이가 주어진 한계를 초과할 때 속도를 늦추는 것을 방지한다.예를 들어 이 원칙은 bzip2 압축기에 사용된다.^[29]

참고 항목

• 콤 정렬

참조

참고 문헌 목록

• Knuth, Donald E. (1997). "Shell's method". The Art of Computer Programming. Volume 3: Sorting and Searching (2nd ed.). Reading, Massachusetts: Addison-Wesley. pp. 83–95. ISBN 978-0-201-89685-5.
• 1996년 9월, 바르셀로나에서 열린 제4차 유럽 알고리즘 심포지엄인 Robert Sedgewick의 Shellsort 및 관련 알고리즘 분석.

외부 링크

Wikibook 알고리즘 구현에는 다음과 같은 주제의 페이지가 있다.셸 정렬

• 애니메이션 정렬 알고리즘: 웨이백 머신에서 셸 정렬(2015년 3월 10일 자료 보관) – 그래픽 시연
• 헝가리의 민속무용으로서 5,3,1 틈새로 조개껍데기