인트로소트

Introsort
인트로소트
클래스정렬 알고리즘
데이터 구조배열
최악의 경우 공연O(n log n)
평균 공연O(n log n)

인트로포트 또는 자기성찰형 정렬은 빠른 평균 성능과 (비교적으로) 최적의 최악의 성능을 모두 제공하는 하이브리드 정렬 알고리즘이다.퀵소트로 시작하여, 재귀 깊이가 정렬되는 원소의 수(로그)에 근거한 수준을 초과할 때 힙소트로 전환하고, 원소의 수가 일부 임계값 미만일 때 삽입 정렬로 전환한다.이것은 3개의 알고리즘의 좋은 부분을 결합하여 일반적인 데이터 세트의 퀵소트 및 힙 소트 때문에 최악의 경우 O(n log n) 런타임에 버금가는 실용적인 성능을 제공한다.그것이 사용하는 세 가지 알고리즘이 비교 분류기 때문에, 그것은 비교 분류이기도 하다.

인트로소트는 무서(1997)의 데이비드 머서(David Musser)에 의해 발명되었는데, 여기서 그는 또한 퀵셀렉트(quicksort의 변종)에 기초한 하이브리드 선택 알고리즘인 인트로셀렉트(introselect)를 도입했는데, 이것은 다시 중위수(medians)로 떨어져 최악의 경우 선형 복잡성을 제공하므로 최적이다.두 알고리즘 모두 빠른 평균 성능과 최적의 최악의 성능을 모두 갖춘 C++ Standard Library에 대한 일반적인 알고리즘을 제공하기 위한 목적으로 도입되어 성능 요구사항이 강화되었다.[1]인트로소트는 제자리에 있고 안정적이지 않다.[2]

가성음

퀵소트 기사에서 논의한 유형의 힙소트 구현 및 분할 기능을 이용할 수 있는 경우, 인트로소트는 다음과 같이 간결하게 설명할 수 있다.

그 수속 sort(A:배열):자 maxdepth)⌊log2(길이())⌋×2introsort(A, maxdepth)절차 introsort(A, maxdepth):n← length(A)만약 n<>16:insertionsort(A) 다른 만약 maxdepth 0게 국가 주의적 관점에서 서술:heapsort(A)다른 것이 있어요. p← partition(A)을 끓여이 기능 pivot 선택 않으며 p은 최종 위치. pivot introsort(A[1:p-1, max depth - 1) introsort(A[p+1:n], maxdepth - 1)

최대 깊이에서 인자 2는 임의적이며, 실제 성능에 맞게 조정할 수 있다.A[i:j]는 A[i]와 A[j]를 모두 포함하는 항목 i의 배열 조각을 의미한다.

분석

퀵소트에서는 중요한 작업 중 하나가 피벗 선택, 즉 리스트가 분할되는 요소 선택이다.가장 간단한 피벗 선택 알고리즘은 목록의 첫 번째 또는 마지막 요소를 피벗으로 가져가는 것으로, 정렬되거나 거의 정렬된 입력의 경우 동작이 불량해진다.니클라우스 위르스의 변종은 이러한 발생을 막기 위해 중간 원소를 사용하며, 조작된 시퀀스의 경우 O(n2)로 변질된다.3의 중앙값 피벗 선택 알고리즘은 목록의 첫 번째, 중간 및 마지막 요소의 중앙값을 취하지만, 이것이 많은 실제 입력에서 좋은 성능을 발휘하지만, 여전히 이 피벗 선택 기법에 기초하여 퀵소트의 극적인 감속을 야기할 3의 중앙값 킬러 리스트를 작성할 수 있다.

무서는 10만 원소의 3중선 킬러 시퀀스에서 인트로스의 가동 시간은 3중선 퀵소트의 200분의 1이라고 보고했다.머서는 작은 범위가 한 번의 삽입 분류 통과로 끝에 정렬되는 세지윅의 지연된 작은 분류의 캐시에 미치는 영향도 고려했다.그는 캐시 누락 횟수를 두 배로 늘릴 수 있지만, 이중으로 끝나는 대기열을 사용하는 성능이 상당히 향상되었고 템플릿 라이브러리에 대해서는 유지되어야 한다고 보고했는데, 이는 바로 정렬을 함으로써 얻는 다른 사례의 이득이 크지 않기 때문이다.

구현

인트로포트 또는 일부 변종은 일부 C++ 정렬 구현을 포함한 다수의 표준 라이브러리 정렬 기능에 사용된다.

2000년 6월 SGI C++ Standard Template Library stl_algo.h 구현에서는 반복 깊이가 있는 Musser introsort 접근방식을 사용하여 파라미터로 전달된 heapsort, 3 피벗의 중간 선택 및 16보다 작은 파티션에 대한 Knuth 최종 삽입 정렬 통과로 전환한다.

GNU Standard C++ 라이브러리는 유사하다. 최대 깊이가2 2×log n인 introsort를 사용하고 16보다 작은 파티션에 삽입 정렬을 한다.[3]

LLVM libc++는 또한 최대 깊이가 2×log2 n인 introsort를 사용하지만 삽입 정렬의 크기 제한은 데이터 유형별로 다르다(스왑이 사소한 경우 30개, 그렇지 않은 경우 6개).또한 크기가 5 이하인 배열을 별도로 취급한다.[4]

마이크로소프트.버전 4.5(2012)부터 시작되는 NET Framework Class Library는 간단한 퀵소트 대신 introsort를 사용한다.[5]

Go는 12개 이하의 요소 조각에 대해서는 삽입 정렬 대신 Shellort를 사용하고, 퀵소트에는 3개의 피벗 선택 중 3개의 중간값으로 고급 중위수를 사용한다.

변형

pdqsort

패턴 제거 퀵소트(pdqsort)는 다음과 같은 개선사항을 포함하는 인트로포르트의 변형이다.[6]

  • 3의 중앙값 피벗,
  • 지점 오용 형벌을 완화하기 위한 "BlockQuicksort" 분할 기술
  • 특정 입력 패턴(어댑티브 정렬)에 대한 선형 시간 성능
  • 더 느린 힙스포트를 시도하기 전에 나쁜 케이스에 소자를 섞어라.

녹스와 GAP는 pdqsort를 사용한다.[7]

참조

  1. ^ 데이비드 머서 "Generic Algorithm",
  2. ^ "Know Your Sorting Algorithm Set 2 (Introsort- C++'s Sorting Weapon)". 26 June 2016.
  3. ^ libstdc++ 설명서:정렬 알고리즘
  4. ^ libc++ 소스 코드: 정렬
  5. ^ 배열.소트 방법(어레이)
  6. ^ Peters, Orson R. L. (2021). "orlp/pdqsort: Pattern-defeating quicksort". GitHub. arXiv:2106.05123.
  7. ^ "slice.sort_unstable(&mut self)". Rust. The current algorithm is based on pattern-defeating quicksort by Orson Peters, which combines the fast average case of randomized quicksort with the fast worst case of heapsort, while achieving linear time on slices with certain patterns. It uses some randomization to avoid degenerate cases, but with a fixed seed to always provide deterministic behavior.

일반