다상 병합 정렬

다상 병합 정렬은 주로 외부 정렬에 사용되는 하위 목록(실행)의 초기 불균일 분포를 사용하여 목록을 정렬하는 상향 병합 정렬의 변형이며, 8개 미만의 외부 작업 파일(예: 테이프 드라이브 또는 하드 드라이브의 파일)이 있을 때 일반 병합 정렬보다 효율적이다.다상 병합 분류는 안정적인 분류가 아니다.

일반 병합 정렬

병합 정렬은 데이터 집합의 레코드를 정렬된 레코드 실행으로 분할한 다음 정렬된 런을 반복적으로 병합하여 하나의 실행, 즉 정렬된 데이터 집합만 남아 있을 때까지 더 큰 정렬된 실행으로 병합한다.

작업 파일 4개를 사용하는 일반적인 병합 정렬은 입력 파일 한 쌍과 출력 파일 한 쌍으로 구성된다.데이터 집합은 정렬된 실행으로 또는 가장 간단한 경우 단일 레코드로 작업 파일 두 개 사이에 균등하게 배포되며, 이는 크기 1의 실행으로 분류된 것으로 간주할 수 있다.모든 데이터 세트가 두 개의 작업 파일로 전송되면, 그 두 개의 작업 파일은 첫 번째 병합 반복을 위한 입력 파일이 된다.각 병합 반복 병합은 두 입력 작업 파일에서 실행되어 병합된 출력을 두 출력 파일 간에 교환하고, 병합된 실행을 두 출력 파일 사이에 다시 균등하게 분배한다(마지막 병합 반복까지).두 입력 파일의 모든 실행이 병합되고 출력되면 출력 파일은 입력 파일이 되고 그 반대의 경우 다음 병합 반복이 된다.실행 횟수는 64, 32, 16, 8, 4, 2, 1과 같이 각 반복마다 2배씩 감소한다. 최종 병합 반복의 경우, 두 입력 파일은 각각 하나의 정렬된 실행(데이터셋의 1/2)만을 가지며, 병합된 결과는 출력 파일 중 하나에 대한 단일 정렬된 실행(정렬된 데이터 집합)이다.이는 또한 Merge sort § Use with 테이프 드라이브에서도 설명된다.

작업 파일이 3개뿐이면 두 개의 작업 파일에서 하나의 작업 파일로 정렬된 일반 병합 정렬 병합이 실행된 다음 두 개의 출력 파일 사이에 실행을 고르게 분산시킨다.병합 반복은 런 카운트를 2배 감소시키고, 재배포 반복은 런 카운트를 감소시키지 않는다(인자는 1).각 반복은 평균 √2 ≈ 1.41의 런 계수를 감소시키는 것으로 간주할 수 있다.작업 파일이 5개일 경우 패턴은 평균 √6 ≈ 2.45의 3방향 병합과 2방향 병합 사이에서 번갈아 나타난다.

일반적으로 작업 파일의 짝수 N의 경우, 일반 병합 정렬의 각 반복은 실행 카운트를 N/2 인수로 감소시키는 반면, 작업 파일의 홀수 N의 경우 각 반복은 실행 카운트를 평균 √(N-1²)/4 = √N-1²/2 인수로 감소시킨다.

다상 병합

N < 8개의 작업 파일의 경우, 다상 병합 정렬은 N-1 작업 파일 사이에 정렬된 실행을 불균일하게 분산시킴으로써 더 높은 유효 실행 카운트 감소 계수를 달성한다(다음 절에서 설명함).각 반복은 N-1 작업 파일에서 단일 출력 작업 파일로 실행된다.N-1 작업 파일 중 하나의 끝에 도달하면 새로운 출력 파일이 되고 출력 파일이었던 것이 N-1 작업 입력 파일 중 하나가 되어 다상 병합 정렬의 새로운 반복을 시작한다.각 반복은 모든 데이터 집합을 하나의 정렬된 실행으로 병합하는 마지막 반복을 제외하고 데이터 집합의 일부(약 1/2 ~ 3/4)만 병합한다.초기 배포는 N-1 입력 작업 파일에서 단일 출력 파일로 N-1 단일 실행(다양한 크기, 다음에 설명됨)을 병합하는 최종 병합 반복을 제외하고 한 번에 하나의 입력 작업 파일만 비우도록 설정되며, 결과적으로 단일 정렬 실행, 정렬된 데이터 집합이 발생한다.

각 다상 반복에 대해 총 런 수는 상위 시퀀스의 역순 피보나치 숫자와 유사한 패턴을 따른다.4파일 및 57타점을 기록의 데이터로, 각 반복에서 전체 운행 횟수가 될 것 57,31,17,9,5,3, 1.[1][2]다는 것은 지난 반복을 제외하고, 달리수 감소 인자 좀 2, 57/31, 31/17, 17/9, 9/5, 5/3, 3/1, 약 4천만 4파일 상자보다 줄었지만 마지막을 제외하고 각 반복이 운영하는 횟수 시간을 줄였다. proce데이터 집합의 약 65%를 ssing하므로 중간 반복 동안 처리된 데이터 집합당 실행 카운트 감소 계수는 약 1.84 / 0.65 = 2.83이다.각각 1개의 레코드로 57개의 런으로 구성된 데이터 집합의 경우, 초기 배포 후, 데이터 집합을 정렬하는 데 필요한 6번의 반복 동안 232개의 레코드를 이동시켜 전체 감소율 2.70(이것은 나중에 더 자세히 설명함)을 얻는다.

1차 다상 반복 후 출력 파일이었던 것이 지금은 N-1 원래 런을 병합한 결과를 포함하고 있지만, 나머지 N-2 입력 작업 파일에는 여전히 나머지 원본 런이 포함되어 있으므로, 2차 병합 시 크기(N-1) + (N-2) = (2N - 3) 원본 런을 생성한다.세 번째 반복은 원래 런 크기(4N - 7)의 런을 생성한다.4개의 파일로, 1차 반복은 3차 원점 주행, 2차 반복 5차 원점 주행, 3차 반복 9차 원점 주행 등을 생성하므로, 1, 3, 5, 9, 17, 31, 57 등의 패턴에 따라 런 크기 증가가 역점 주행 횟수 감소와 동일한 패턴을 따른다.각각 1개의 레코드를 4개 파일 및 57개의 실행의 예에서 마지막 반복은 크기 31, 17, 9의 3개의 실행을 병합하여 31+17+9 = 57개의 레코드를 하나의 정렬된 실행으로 분류한 데이터 집합이다.4개의 파일에 대한 실행 수와 실행 크기의 예, 31개의 레코드는 의 표 4.3에서 찾을 수 있다.^[3]

완벽한 3 파일 다상 병합 정렬

다상 병합은 종말 조건부터 시작해서 역작용을 하는 것이 가장 쉽다.각 반복이 시작될 때, 2개의 입력 파일과 1개의 출력 파일이 있을 것이다.반복이 끝나면 하나의 입력 파일이 완전히 소비되어 다음 반복을 위한 출력 파일이 된다.현재 출력 파일은 다음 반복을 위한 입력 파일이 될 것이다.나머지 파일(파일 케이스 3개 중 1개만)은 부분적으로만 사용되었으며 나머지 실행은 다음 반복을 위해 입력될 것이다.

1번 파일이 방금 비워서 새로운 출력 파일이 되었다.각 입력 테이프에는 한 번의 실행이 남아 있으며, 이 실행들을 병합하면 정렬된 파일이 된다.

파일 1 (out): <1 run> * (정렬된 파일) 파일 2 (in ) : ...<1 run> * --> ...<1 run> * (소비) 파일 3 (in ): <1 run> * <1 run> * (소비) ... 이미 읽혀진 가능한 실행은 파일의 * 마크를 * 파일의 끝을 표시한다.

이전 반복으로 돌아가서, 우리는 1번과 2번부터 읽고 있었다.1번 실행은 1번과 2번에서 병합된 후 1번 파일이 비어진다.파일 2가 완전히 소모되지 않는다는 점에 유의하십시오. 최종 병합(위)과 일치하도록 한 번의 실행이 남아 있다.

1번 파일(인 ): ... 1번 실행 > * ...1번 실행 > * 2번 파일(인 ): 2번 실행 > * --> 1번 실행 > 1번 실행 > 파일 3번 파일(아웃): 1번 실행

다시 한 번 반복하면 파일 3이 비기 전에 1과 3에서 2회 실행이 병합된다.

파일 1 ( ) : <3 run> ...<2 run> <1 run> * 파일 2 (out): --> <2 run> * 파일 3 (in ) : ... <2 run> * <2 run> *

다시 한 번 반복하면 2번과 3번에서 3번 실행이 병합된 후 2번 파일이 비워진다.

파일 1 (out): <3 run> * 파일 2 (in ) : ...<3 run> * --> ...<3 run> * 파일 3 (in ) : <5 run> * <3 run> <2 run> *

다시 한 번 반복하면 파일 1이 비기 전에 1과 2에서 5개의 실행이 병합된다.

파일 1 ( ) : ... <5 run> * ...<5 run> * 파일 2 (in ): <8 run> * --> <5 run> *<3 run> * 파일 3 (out): <5 run> *

다상 병합 정렬에 대한 분포

완벽한 3개의 파일 케이스를 보면, 병합된 실행 횟수가 거꾸로 작용하는 1, 1, 2, 3, 5, ... 피보나치 시퀀스를 보여준다.3개 이상의 파일에 대한 순서는 좀 더 복잡하다. 4개 파일의 경우 최종 상태에서 시작하여 역방향으로 작동하는 경우 실행 카운트 패턴은 {1,0,0,0}, {0,1,1,1,2,2}, {3,2,0,4}, {7,13,11,7}, {13,24,20}, ...

모든 것이 최적으로 해결되려면 마지막 병합 단계는 각 입력 파일에 대해 정확히 한 번의 실행이 있어야 한다.입력 파일에 실행이 두 개 이상 있는 경우 다른 단계가 필요할 것이다.따라서 다상 병합 정렬은 초기 출력 파일에 대한 입력 데이터 실행의 초기 배포에 대해 영리할 필요가 있다.예를 들어, 13개의 실행이 있는 입력 파일은 1번 파일에 5개의 실행, 2번 파일에 8개의 실행이 기록된다.

실제로 입력 파일은 완벽한 배포에 필요한 정확한 실행 횟수를 갖지 못할 것이다.이를 처리하는 한 가지 방법은 이상적인 런 분포를 시뮬레이션하기 위해 실제 분포를 가상의 "덤미 런"으로 채우는 것이다.^[1]더미 런은 기록이 없는 런처럼 동작한다.하나 이상의 더미 런을 하나 이상의 실제 런으로 병합하면 실제 런만 병합되고 실제 런이 없는 더미 런을 하나 이상 병합하면 단일 더미 런이 된다.또 다른 접근방식은 병합 작업 중에 필요에 따라 더미 실행을 에뮬레이트하는 것이다.^[4]

"최적" 분포 알고리즘은 런 수를 미리 알아야 한다.그렇지 않으면, 런 수를 미리 알 수 없는 더 일반적인 경우, "최적 분포 알고리즘에 가까운" 분포 알고리즘이 사용된다.일부 배포 알고리즘에는 실행 재배치가 포함된다.^[5]런 수가 미리 알려진 경우 병합 단계를 시작하기 전에 부분 분포만 있으면 된다.예를 들어 File_1에서 n run으로 시작하는 3개의 파일 케이스를 생각해 보십시오.F_i = F_i−1 + F를_i−2 ih 피보나치 숫자로 정의하십시오.n = F인_i 경우 F_i−2 run을 File_2로 이동하여 F_i−1 run을 File_1에 남겨두면 완벽한 실행 분포가 된다.F_i < n < F_i+1>인 경우, n-F_i run을 File_2로, F-n_i+1 run을 File_3으로 이동시킨다.첫 번째 병합 반복은 File_1과 File_2에서 n-F_i 실행을 병합하여, n-F_i 병합 실행을 F-n_i+1 실행이 이미 File_3으로 이동한 것에 추가한다.File_1은 F_i−2 run이 남고, File_2는 비우고, File_3은 F_i−1 run으로 끝나 다시 한번 완벽한 run 배포가 된다.4개 이상의 파일의 경우 수학은 더 복잡하지만 개념은 같다.

비교 대 일반 병합 정렬

초기 배포 후, 4개의 파일을 사용하는 일반적인 병합 정렬은 전체 데이터셋의 4번 반복에서 16개의 단일 레코드 실행을 정렬하여, 초기 배포 후 데이터 집합을 정렬하기 위해 총 64개의 레코드를 이동시킨다.4개의 파일을 사용하는 다상 병합 정렬은 4번 반복으로 17개의 단일 레코드 실행을 정렬하지만, 각 반복은 데이터 집합의 일부만 이동하므로, 초기 배포 후 데이터 집합을 정렬하기 위해 총 48개의 레코드만 이동한다.이 경우 일반 병합 정렬 계수는 2.0인 반면, 다상 종합 계수는 ≈2.73이다.

감쇠 계수가 분류 성과와 어떤 관련이 있는지 설명하기 위해 감쇠 계수 방정식은 다음과 같다.

recovery_options = exp(number_of_number)*log(number_of_count)/run_move_count = number_of_count * log(number_of_f)/log(remission_count) run_move_count = number_of_rement_rement(number_count)

위의 예제에 런 수 이동 방정식 사용:

일반 병합 정렬 → $16\times \log _{2}(16)=64$ $16\times \log _{2}(16)=64$ $16\times \log _{2}(16)=64$ 2 $16\times \log _{2}(16)=64$ ( $16\times \log _{2}(16)=64$ ) = $16\times \log _{2}(16)=64$ {\ $displaystyle 16\log \log _{2}(16)=64$
다상 병합 정렬 → $17\times \log _{2.73}(17)=48$ $17\times \log _{2.73}(17)=48$ $17\times \log _{2.73}(17)=48$ $17\times \log _{2.73}(17)=48$ ⁡ $17\times \log _{2.73}(17)=48$ ( $17\times \log _{2.73}(17)=48$ ) $17\times \log _{2.73}(17)=48$ = $17\times \log _{2.73}(17)=48$ $17\\\log _{2.73}(17)=48$ .

다음은 파일 수별로 나열한 다상 및 일반 병합에 대한 효과적인 감소 요인의 표로서, 실제 수백만 개의 레코드를 기반으로 한다.이 표는 다상 병합 정렬의 그림 3과 그림 4에 표시된 데이터 집합 이동 테이블당 감소율에 대략 해당한다.pdf

# 파일 이상적인 크기 데이터 3.73 1.94 1.41 (sqrt 2) 4.63 2.68 2.00 5.58 3.20 2.45 (sqrt 6) 6.56 3.56 3.56 3.00 7.55 3.56 3.46 (sqrt 12) 8의 이상 크기 데이터 일반적 감소 계수에 대한 데이터 반복당 평균 데이터 비율.54 3.95 4.00 9.53 4.07 4.47 (sqrt 20) 10 .53 4.15 5.00 11.53 4.22 5.48 (sqrt 30) 12 .53 6.28 6.00 32 .53 4.87 16.00

일반적으로 다상 병합 정렬은 파일이 8개 미만일 때 일반 병합 정렬보다 좋은 반면 일반 병합 정렬은 8개 이상일 때 더 좋아지기 시작한다.^[6]^[7]

참조

^ ^a ^b 도날드 크누스, 컴퓨터 프로그래밍의 기술 제3권 애디슨 웨슬리, 1973년 알고리즘 5.4.2D
^ "Archived copy". Archived from the original on 2012-11-22. Retrieved 2010-01-31.{{cite web}}: CS1 maint: 타이틀로 보관된 사본(링크)
^ "External sorting". Archived from the original on 2016-01-28. Retrieved 2016-01-22.
^ https://www.fq.math.ca/Scanned/8-1/lynch.pdf^{[bare URL PDF]}
^ http://i.stanford.edu/pub/cstr/reports/cs/tr/76/543/CS-TR-76-543.pdf^{[bare URL PDF]}
^ "Advanced Programming I Lecture Notes".
^ http://www.mif.vu.lt/~algis/dsax/DsSort.pdf^{[bare URL PDF]}

추가 읽기

Bradley, James (1982), File and Data Base Techniques, Holt, Rinehart and Winston, ISBN 0-03-058673-9
Reynolds, Samuel W. (August 1961), "A generalized polyphase merge algorithm", Communications of the ACM, New York, NY: ACM, 4 (8): 347–349, doi:10.1145/366678.366689, S2CID 28416100
Sedgewick, Robert (1983), Algorithms, Addison-Wesley, pp. 163–165, ISBN 0-201-06672-6

외부 링크

[Knuth1973-1] 도날드 크누스, 컴퓨터 프로그래밍의 기술 제3권 애디슨 웨슬리, 1973년 알고리즘 5.4.2D

[2] "Archived copy". Archived from the original on 2012-11-22. Retrieved 2010-01-31.{{cite web}}: CS1 maint: 타이틀로 보관된 사본(링크)

[3] "External sorting". Archived from the original on 2016-01-28. Retrieved 2016-01-22.

[4] ttps://www.fq.math.ca/Scanned/8-1/lynch.pdf^{[bare URL PDF]}

[5] ttp://i.stanford.edu/pub/cstr/reports/cs/tr/76/543/CS-TR-76-543.pdf^{[bare URL PDF]}

[6] "Advanced Programming I Lecture Notes".

[7] ttp://www.mif.vu.lt/~algis/dsax/DsSort.pdf^{[bare URL PDF]}

[3]

[1]

[4]

[5]

[6]

[7]

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

Search