부분 정렬

Partial sorting

컴퓨터 과학에서 부분 분류는 분류 문제의 완화된 변형이다.전체 정렬은 해당 요소가 모두 순서대로 나타나도록 항목 목록을 반환하는 문제인 반면 부분 정렬은 k 가장 작은(또는 k 가장 큰) 요소의 목록을 순서대로 반환하는 문제인 것이다.다른 요소(k 최소 요소 위)도 내부 부분 정렬에서와 같이 정렬하거나, 부분 정렬을 스트리밍할 때 일반적으로 폐기할 수 있다.부분 정렬의 일반적인 실제 예는 일부 목록의 "상위 100"을 계산하는 것이다.

지수의 관점에서, 부분 정렬된 리스트에서, 1에서 k까지의 모든 지수 i에 대해, i번째 요소는 완전히 정렬된 리스트에 있을 때와 같은 위치에 있다: 부분 정렬된 리스트의 요소 i는 입력 리스트의 순서 통계 i를 포함한다.

오프라인 문제

힙 기반 솔루션

힙스는 k가 고정될 때 간단한 단일 패스 부분 정렬을 허용한다. 입력의 첫 번째 k 요소를 최대 heap에 삽입한다.그런 다음 나머지 요소 위로 한 번 통과하고 각 요소를 차례로 힙에 추가한 다음 가장 큰 요소를 제거하십시오.각 삽입 작업에는 O(log k) 시간이 소요되어 전체적으로 O(n log k) 시간이 소요되며, 이 알고리즘은 k의 작은 값과 온라인 설정에 실용적이다.[1]또 다른 옵션은 모든 값에 대해 최소 heap을 작성하는 것이다(빌드에는 O(n)가 필요하며, 힙의 헤드는 K번 꺼내고, 제거 작업에는 O(log n)가 필요하다.이 경우 알고리즘은 O(n+klog n)를 사용한다.

파티셔닝 선택 시 솔루션

k 가장 작은 원소의 목록만 필요로 하는 추가적인 이완은 이러한 요소들을 정렬할 필요 없이, 문제를 파티션 기반 선택과 동등하게 만든다; 최초의 부분 정렬 문제는 그러한 선택 알고리즘을 통해 해결되어 첫 번째 k 원소가 k 가장 작은 원소가 있는 배열을 얻고 이들을 토타에서 정렬할 수 있다.L O(n + k 로그 k) 작업 비용.이 알고리즘 체계를 구현하기 위한 일반적인 선택은 퀵셀렉트와 퀵소트를 결합하는 것이다. 그 결과를 "퀵셀소트"[1]라고 부르기도 한다.

전문 정렬 알고리즘

앞서 언급한 것보다 더 효율적인 것은 병합과 퀵소트를 기반으로 한 전문 부분 정렬 알고리즘이다.퀵소트 변종에서는 최종 정렬된 배열에서 k'위 이후("왼쪽" 경계부터)에 해당하는 요소만 포함하는 파티션을 재귀적으로 정렬할 필요가 없다.따라서 피벗이 위치 k 이상일 경우 왼쪽 파티션에서만 반복된다.[2]

함수 부분_quicksort(A, i, j, k)는 i when p if p pivot 피벗(A, i, i, j, j) p ← 파티션(A, i, j, p) 부분_quicksort(A, i, p-1, k)인 경우 p partial p quart_quicksort(A, p+1, j, k)이다.

결과 알고리즘은 부분 퀵소트라고 불리며 O(n + k log k)의 예상 시간만을 필요로 하며, 특히 k가 n에 비해 작아졌을 때 선택 분류가 베이스 케이스로 사용되는 경우 실전에 있어서는 상당히 효율적이다.그러나 최악의 경우 시간 복잡성은 피벗 선택이 잘못된 경우 여전히 매우 나쁘다.최악의 경우 선형 시간 선택 알고리즘의 라인을 따라 피벗 선택을 사용하여 최악의 경우 성능을 향상시킬 수 있다.

증분 정렬

증분 정렬은 입력이 전면으로 포기되지만 k를 알 수 없는 부분 정렬 문제의 한 버전이다. k-형 정렬 어레이를 사용할 경우 어레이가 (k+1)형 정렬이 되도록 부분 정렬된 부분을 확장할 수 있어야 한다.[3]

Haps는 증분 부분 정렬에 대한 O(n + k log n) 솔루션으로 이어진다. 첫 번째 "heapify"는 선형 시간 내에 전체 입력 배열을 통해 최소 heap을 생성한다.그런 다음 최소 힙 k 번을 추출하십시오.[1]

퀵 선택을 수정하면 다른 증분 정렬을 얻을 수 있다.Paredes와 Navarro로 인한 버전은 호출에 걸쳐 피벗 스택을 유지하므로, 다음 알고리즘에서 어레이 A의 가장 작은 항목을 반복적으로 요청하여 증분 정렬을 수행할 수 있다.[3]

알고리즘 IQS(A : 어레이, i : 정수, S : 스택)는 A에서 i번째 가장 작은 원소를 반환한다.

  • i = top(S):
    • 팝 S
    • 반품 A[i]
  • 피벗 ← 랜덤 [i, 상단(S))]으로 설정
  • 피벗 ← 파티션 업데이트(A[i : top(S)), A[pivot])
  • 피벗을 S에 푸시
  • IQS 반환(A, i, S)

스택 S는 A k-sorting의 길이 n만 포함하도록 초기화되며, i = 0, 1, 2, ...에 대해 IQS(A, i, S)를 호출하여 어레이를 정렬한다.; 이 통화 순서는 평균 사례 복잡성 O(n + k log k)를 가지며, 이는 점증상으로는 O(n + k log n)와 동일하다.최악의 경우 시간은 2차지만, 이것은 중위수 알고리즘으로 무작위 피벗 선택을 대체함으로써 해결할 수 있다.[3]

언어/도서관 지원

참고 항목

참조

  1. ^ a b c Conrado Martínez (2004). On partial sorting (PDF). 10th Seminar on the Analysis of Algorithms.
  2. ^ Martínez, Conrado (2004). Partial quicksort (PDF). Proc. 6th ACM-SIAM Workshop on Algorithm Engineering and Experiments and 1st ACM-SIAM Workshop on Analytic Algorithmics and Combinatorics.
  3. ^ a b c Paredes, Rodrigo; Navarro, Gonzalo (2006). "Optimal Incremental Sorting". Proc. Eighth Workshop on Algorithm Engineering and Experiments (ALENEX). pp. 171–182. CiteSeerX 10.1.1.218.4119. doi:10.1137/1.9781611972863.16. ISBN 978-1-61197-286-3.

외부 링크