스무스소트

Smoothsort
스무스소트
An animation depicting smoothsort's operation, showing the heap being built and then disassembled,
어레이 상에서 동작하는 스무스 소트는 대부분 정상입니다.위쪽의 막대는 트리 구조를 나타냅니다.
학급정렬 알고리즘
data 구조어레이
최악의 경우 성능O(n log n)
베스트 케이스 성능O(n)
평균 성능O(n log n)
최악의 경우 공간의 복잡성O(n) 합계, O(1) 보조

컴퓨터 과학에서 스무드소트는 비교 기반 정렬 알고리즘입니다.힙소트의 변형으로 1981년 [1]Edsger Dijkstra에 의해 발명되어 출판되었습니다.힙소트와 마찬가지로 스무드소트는 상한 O(n log n)[2]의 임플레이스 알고리즘이지만 안정적인 [3][self-published source?][4]정렬은 아닙니다.스무스소트의 장점은 입력이 이미 어느 정도 정렬되어 있는 경우 O(n) 시간에 가까워진다는 것입니다.한편 힙소트는 초기 정렬 상태에 관계없이 O(n log n)의 평균을 냅니다.

개요

힙소트와 마찬가지로 스무드소트는 입력을 priority 큐에 정리한 후 최대값을 반복적으로 추출합니다.또한 힙소트와 마찬가지로 priority 큐는 암묵적인 힙 데이터 구조(히프 순서 암묵적인 바이너리 트리)로 배열의 프레픽스를 점유합니다.추출할 때마다 접두사가 축소되고 추출된 요소가 정렬된 접미사에 추가됩니다.프리픽스가 0으로 축소되면 어레이가 완전히 정렬됩니다.

힙소트는 트리의 너비부터 톱다운하여 어레이에 바이너리 트리를 매핑합니다.어레이는 트리의 루트부터 시작하여 2개의 자식, 4개의 손자, 기타 순서로 진행됩니다.모든 요소는 트리 루트 아래에 명확하게 정의된 깊이를 가지며 루트를 제외한 모든 요소는 어레이의 초기에 상위 요소를 가집니다.그러나 잎 위의 높이는 배열 크기에 따라 달라집니다.이 경우 정렬 프로세스의 일부로 모든 요소를 이동해야 한다는 단점이 있습니다. 즉, 최종 위치로 이동하기 전에 루트를 통과해야 합니다.

SmoothSort는 다른 매핑인 상향식 깊이 우선 사후 순서 트래버설을 사용합니다.왼쪽 자녀는 형제자매에 뿌리를 둔 하위 트리에 이어 오른쪽 자녀는 부모에 이어 이어집니다.모든 요소는 잎 위에 잘 정의된 높이를 가지며, 잎이 아닌 모든 요소는 배열의 앞부분에 하위 요소를 가집니다.그러나 루트 아래의 깊이는 어레이 크기에 따라 달라집니다.알고리즘은 루트가 힙의 끝에 오도록 구성되어 있으며 요소가 힙에서 추출되는 순간 이미 최종 위치에 있으므로 이동할 필요가 없습니다.또한 정렬된 배열은 이미 유효한 힙이며 정렬된 많은 간격은 유효한 힙 순서 하위 트리입니다.

좀 더 형식적으로 말하면, 모든 위치 i는 하나의 서브트리의 루트이며, 그 노드는 i로 끝나는 연속된 간격을 차지합니다.어레이의 첫 번째 프리픽스(배열 전체를 포함한다)는 서브트리에 대응하는 인터벌일 수 있지만 일반적으로는 연속되는 서브트리 인터벌의 조합으로 분해됩니다.Dijkstra는 이것을 「스트레치」라고 부릅니다.부모가 없는 하위 트리(즉, 부모가 고려 중인 접두사 너머에 있는 위치에 루트)는 해당 간격의 분해에 스트레치를 주며, 따라서 분해는 고유하다.새로운 노드가 프리픽스에 추가되면 두 가지 경우 중 하나가 발생합니다.위치가 리프이고 길이1의 스트레치를 분해에 추가하거나 마지막 2개의 스트레칭과 결합하여 각각의 루트의 부모가 되며, 따라서 2개의 스트레칭이 결합과 새로운 (루트)위치를 포함한 새로운 스트레칭으로 대체됩니다.

Dijkstra는[1] 모든 서브트리가 2-1k 크기의 완벽한 이진 트리가 되는 경우, 크기가 동일한 경우에만 스트레칭을 결합하는 것이 명백한 규칙이라고 지적했습니다.하지만, 그는 더 많은 가능한 나무 크기를 주는 다른 규칙을 선택했습니다.이 값은 [2]점근 효율은 동일하지만 각 구간을 커버하는 데 필요한 스트레칭이 적기 때문에 효율에서 작은 상수 요인을 얻을 수 있습니다.

Dijkstra가 사용하는 규칙은 마지막 두 스트레칭이 연속된 레오나르도 숫자 L(i+1)과 L(i)(순서대로)인 경우에만 결합된다는 것입니다. 숫자는 피보나치 숫자와 매우 유사한 방식으로 반복적으로 정의됩니다.

  • L(0) = L(1) = 1
  • L(k+2) = L(k+1) + L(k) + 1

결과적으로, 모든 서브트리의 크기는 레오나르도 숫자입니다.임의의 n개의 위치를 분해하는 스트레치 사이즈의 시퀀스는 탐욕스러운 방법으로 찾을 수 있습니다.첫 번째 사이즈는 n을 넘지 않는 가장 큰 레오나르도 수이고 나머지(있는 경우)는 재귀적으로 분해됩니다.스트레칭의 크기는 두 개의 최종 크기 1을 제외하고 엄격히 줄어들고 있으며, 마지막 두 크기를 제외하고 연속되는 레오나르도 숫자를 피하고 있습니다.

각 스트레칭이 히프 순서 트리인 것 외에 나무의 뿌리는 정렬 순서로 유지됩니다.이렇게 하면 세 번째 아이(Dijkstra는 이를 '의붓 아들'이라고 부른다)가 각 루트에 추가되어 이전 루트에 링크됩니다.이렇게 하면 모든 트리가 하나의 글로벌히프에 결합되고 마지막에 글로벌최대값이 표시됩니다.

각 노드의 의붓아들 위치는 고정되어 있지만 링크는 트리 루트에 대해서만 존재하므로 트리가 병합될 때마다 링크가 제거됩니다.이것은 부모가 존재하는 한 연결되어 있는 일반적인 아이들과는 다릅니다.

정렬의 첫 번째(히프 성장) 단계에서는 어레이의 점점 더 큰 초기 부분이 각 스트레칭의 서브트리가 최대 히프가 되도록 재구성된다.잎 이외의 위치에서의 엔트리는 적어도 그 자녀인 위치에서의 엔트리와 같은 크기이다.게다가, 모든 뿌리는 적어도 의붓아들만큼 크다.

두 번째(히프 축소) 단계에서는 최대 노드가 어레이 끝에서 분리되고(이동할 필요 없이) 힙 불변수가 자식 간에 재정립됩니다(구체적으로는 새로 생성된 스텝셋 중).

실제 구현에서는 레오나르도 숫자 L(k)을 계산해야 하는 경우가 많습니다.Dijkstra는 정수 변수가 필요할 때 필요한 값을 효율적으로 계산하기 위해 고정된 수의 정수 변수를 사용하는 현명한 코드를 제공합니다.또, 정렬하는 어레이의 사이즈에 유한한 바운드 N이 있는 경우에는, 미리 계산된 레오나르도수의 테이블을 O(log N) 공간에 격납할 수 있다.

운용

정렬 절차의 두 단계는 시퀀스 오브 헤프 구조의 진화에 관한 한 서로 반대이지만, 이들은 이진수 max-heap에서 "하강" 연산에 해당하는 하나의 코어 프리미티브를 사용하여 구현됩니다.

체를 내리다

코어 시프터다운 조작(Dijkstra는 이것을 「트링클」이라고 부릅니다)은, 루트 노드만으로 위반되었을 가능성이 있는 경우, 히프의 불변성을 복원합니다.루트 노드가 하위 노드보다 작을 경우 가장 큰 자노드와 스왑되고 새 하위 트리의 루트 노드에서 프로세스가 반복됩니다.

스무드소트와 바이너리 max-heap의 차이점은 각 스트레치의 루트가 세 번째 "계자" 즉, 이전 스트레치의 루트에 대해 순서가 매겨져야 한다는 것입니다.따라서 체를 거르는 절차는 의붓아들이 최대 요소가 아닐 때까지 일련의 4방향 비교(루트 노드와 3개의 자식)에서 시작하여 루트 노드가 최종 홈을 찾고 불변수가 재정립될 때까지 일련의 3방향 비교(루트 + 2개의 자식)에서 시작합니다.

각 트리는 완전한 바이너리 트리입니다.각 노드에는 2개의 서브가 있습니다.표준 암묵적 바이너리 힙에서 발생하는 한 자녀의 특수한 경우를 처리할 필요는 없습니다(그러나 의붓아들 링크의 특수한 경우는 이 절약을 보충하는 것 이상입니다).

각각 깊이 O(log n)의 트리인 O(log n)의 연장이 있기 때문에, 각 체내 연산을 실시하는 시간은 O(log n)로 한정된다.

오른쪽에 요소를 통합하여 힙 영역 확대

추가 요소가 스트레칭 시퀀스에 통합될 것으로 고려되면(분리된 힙 구조의 목록) 새로운 단일 요소 스트레칭을 형성하거나, 두 루트의 부모가 되어 시퀀스에서 두 요소를 대체하는 새로운 스트레칭을 형성하여 두 개의 오른쪽 스트레칭을 결합합니다.두 가지 중 어느 것이 발생할지는 현재 존재하는 스트레칭의 크기(그리고 궁극적으로 추가된 요소의 지수에만 의존함)에만 달려 있다.Dijkstra는 일부 연속된 레오나르도 숫자에 대해 그 크기가 L(k+1)과 L(k)인 경우에만 스트레칭이 결합된다고 규정했다. 새 스트레칭의 크기는 L(k+2)이다.

어느 경우든 새로운 요소는 히프 구조의 올바른 위치로 이동해야 합니다.새 노드가 단일 요소 스트레치인 경우에도 이전 스트레치의 루트를 기준으로 정렬해야 합니다.

최적화

Dijkstra의 알고리즘은 성장 단계의 마지막에 완전한 힙 불변성이 필요하지만 모든 중간 단계에서 필요한 것은 아니라는 것을 관찰함으로써 작업을 절약합니다.특히, 요소가 의붓아들 보다 크다는 요건은 최종 트리 루트인 요소에만 중요합니다.

따라서 요소가 추가되면 미래의 부모 위치를 계산합니다.이 값이 정렬할 수 있는 나머지 값 범위 내에 있는 경우 의붓아들이 없는 것처럼 행동하고 현재 트리 내에서만 시프팅합니다.

맨 오른쪽 요소를 분리하여 힙 영역 축소

이 단계 동안, 스트레칭의 순서의 형태는 성장 단계의 변화를 거꾸로 거친다.리프 노드를 분리할 때는 작업이 전혀 필요하지 않지만, 비리프 노드의 경우 두 아이는 새로운 스트레칭의 루트가 되고 스트레칭의 루트의 순서로 올바른 위치로 이동해야 합니다.이것은 두 번 체를 내려서 얻을 수 있다.처음에는 왼쪽 아이, 그 다음에 오른쪽 아이(의붓아들이 왼쪽 아이였다)를 위해서.

완전한 바이너리 트리에 있는 모든 노드의 절반이 Leave이기 때문에 노드당 평균1개의 시프트다운 조작이 실행됩니다.

최적화

새로 노출된 뿌리는 정상 자녀에 대해 올바른 순서로 정렬되어 있다는 것은 이미 알려진 사실이다; 문제가 되고 있는 것은 의붓아들과 관련된 순서일 뿐이다.따라서 히프를 축소하는 동안 다운의 첫 번째 단계는 의붓아들과의 단일 비교로 단순화할 수 있습니다.스왑이 발생하는 경우 후속 절차에서 완전한 4방향 비교를 수행해야 합니다.

분석.

Smoothsort는 사전 정렬된 배열, 최악의 경우 O(n log n)를 처리하는 데 O(n) 시간이 걸리며 거의 정렬된 많은 입력에서 거의 선형에 가까운 성능을 달성합니다.그러나 거의 정렬된 모든 시퀀스를 최적으로 처리하지는 않습니다.반면에 다른 적응 정렬 알고리즘 이 c를 해결할 수 있un-sortedness(지수의 쌍의 개수 i와 j에 거야. j과 A[나는]>, A[j], 무작위로 정렬된 입력을 위해 이것은 대략n2/4은 <)의 단위로 역전의 수를 사용하여, 그것 Ω(nlogn)시간이 걸리게 한다 O(nlogn)역전으로 가능한 입력 시퀀스,asesO([2]n log n) 시간 내에.

스무스소트 알고리즘은 레오나르도 힙의 모든 트리 크기를 메모리에 저장할 수 있어야 합니다.이러한 순서는 순서별로 정렬되고 모든 순서는 구별되기 때문에 일반적으로 존재하는 순서를 나타내는 비트벡터를 사용합니다.게다가 가장 큰 순서는 기껏해야 O(log n)이기 때문에, 이들 비트는 트랜스디코토머스 머신 모델을 상정해 O(1) 머신 워드로 부호화할 수 있다.

O(1) 기계어는 하나의 기계어와 동일하지 않습니다.32비트 벡터는 L(32) = 7049155보다 작은 크기에만 충분합니다.64비트 벡터는 L(64) = 34335360355129 22보다45 작은 사이즈에 적합합니다.일반적으로 크기의 비트당 1/log2(θ) 1 1.44비트의 벡터가 필요합니다.

포플러 분류

스무스소트에서 영감을 얻은 간단한 알고리즘은 포플러 [5]정렬입니다.네덜란드 폴더에서 자주 볼 수 있는 크기가 감소하는 트리 행의 이름을 따서 명명된 이 도구는 대부분 정렬되지 않지만 정렬된 입력에 대해 선형 시간을 달성할 수 없는 입력에 대해 스무스 정렬보다 더 적게 비교합니다.

포플러 정렬에 의해 이루어진 중요한 변화는 다양한 나무의 뿌리가 정렬된 순서로 유지되지 않는다는 것입니다. 즉, 이들을 하나의 힙으로 묶는 "계자" 링크는 없습니다.대신 두 번째 단계에서 힙이 축소될 때마다 루트가 검색되어 최대 엔트리를 찾습니다.

각각 O(log n) 트리 루트의 최대값을 검색해야 하는 축소 단계가 n개 있기 때문에 포플러 정렬의 최적의 실행 시간은 O(n log n)입니다.

저자들은 또한 레오나르도 나무보다 완벽한 이진수를 사용하는 것을 제안하지만, 이것은 덜 중요한 변화이다.

동일한 구조가 [6]후순서 힙이라는 이름으로 범용 priority 큐로 제안되어 암묵적 이항 힙보다 단순한 구조에서 O(1) 상각 삽입 시간을 달성했습니다.

적용들

musl C 라이브러리는 smoothsort를 사용하여 다음을 구현합니다.qsort()를 클릭합니다.[7][8]

레퍼런스

  1. ^ a b 데이 크스트라, 에츠허르 168월 1981년(EWD-796a)(PDF). E.W. 데이 크스트라 기록 보관소.센터 미국 역사에, Austin에서 Texas의 대학교.또 왜 내가 가능하게 뻗어 있는 길이들 선택하지 못하고 있기 때문에 각각의 스트레칭 균형을 이룬 2진 트리의postorder 순회로 보여질 수 있는 매력적으로 보이는 질문:...633115731를 높일 수 있다게다가 복귀 관계 훨씬 더 간단할 것이다.왜 나는 레오나르도 숫자:(전사)을 선택했다 하지만 전 알아요.
  2. ^ a b c Hertel, Stefan (13 May 1983). "Smoothsort's behavior on presorted sequences" (PDF). Information Processing Letters. 16 (4): 165–170. doi:10.1016/0020-0190(83)90116-3.
  3. ^ Brown, Craig (21 Jan 2013). "Fastest In-Place Stable Sort". Code Project.[자체 확인 소스]
  4. ^ Eisenstat, David (13 September 2020). "Where is the smoothsort algorithm used?". Stack Overflow. Retrieved 2020-10-28. Smoothsort is not stable, and stability is often more desirable than in-place in practice
  5. ^ Bron, Coenraad; Hesselink, Wim H. (13 September 1991). "Smoothsort revisited". Information Processing Letters. 39 (5): 269–276. doi:10.1016/0020-0190(91)90027-F.
  6. ^ Harvey, Nicholas J. A.; Zatloukal, Kevin (26–28 May 2004). The Post-Order Heap. Third International Conference on Fun with Algorithms (FUN 2004). Elba, Italy.
  7. ^ Felker, Rich (30 April 2013). "How do different languages implement sorting in their standard libraries?". Stack Overflow. Retrieved 2020-10-28.
  8. ^ Ochs, Valentin; Felker, Rich (11 August 2017). "src/stdlib/qsort.c". musl - an implementation of the standard library for Linux-based systems. Retrieved 2021-01-26.

외부 링크