5. 의정렬 / 합병 v 정렬 / 합병의개요 u 정렬 (sorting) 내부정렬 (internal sorting) 데이타가적어서메인메모리내에모두저장시켜정렬가능할때 레코드판독, 기록에걸리는시간이문제되지않는다. 외부정렬 (external sorting) 데이타가많아서메인메모리의용량을초과하여보조저장장치에저장된을정렬할때 레코드판독, 기록에걸리는시간이중요 정렬 / 합병 (sort/merge) 런 (run) : 하나의을여러개로분할하여내부정렬기법으로정렬시킨서브 (subfile) 런들을합병 (merge) 하여원하는하나의정렬된로만든다.
시작논리서브 에서처음키 를 합병의기본서브 에서논리처음키 을 읽어라읽어라 서브 의 EOF 에도착했는가? YES 서브 의 EOF 에도착했는가? YES 끝 NO YES 서브 의 EOF 에도착했는가? 서브 의레코드를정렬된에출력하라 서브 의레코드를정렬된수록하라 YES 키 < 키 NO 서브 에서다음키 를읽어라 서브 에서다음키 을읽어라 서브 의레코드를합병에수록하라 서브 의레코드를합병에수록하라 서브 에서다음키 을읽어라 서브 에서다음키 를읽어라 정렬 / 합병단계 정렬단계 (sort phase) 정렬할의레코드들을지정된길이의서브로분할해서정렬하여런 (run) 을만들어입력로분배하는단계. 정렬 합병단계 (merge phase) 정렬된런들을합병해서보다큰런으로만들고, 이것들을다시입력로재분배하여합병하는방식으로모든레코드들이하나의런에포함되도록만드는단계. 합병
정렬단계 u 런생성방법 내부정렬 (internal sort) 대체선택 (replacement selection) 자연선택 (natural selection) u 입력 ( 레코드키값 ) 의예 09 9 68 5 60 8 8 7 6 9 55 98 78 76 0 5 86 0 7 6 9 99 7 9 6 80 7 8 89 50 6 6 67 9 8 5 59 0 8 76 6 85 5 () 내부정렬 (internal sort) u u 런생성방법. 을 n레코드씩분할. 분할된레코드들을내부정렬기법으로정렬런생성결과 마지막런을제외하고모두길이가동일 n=5인경우 런 : 5 9 68 09 런 : 8 8 7 60 런 : 6 9 55 98 런 : 5 0 76 78 86 런 5 : 0 7 6 9 99 런 6 : 6 9 7 런 7 : 8 7 80 89 런 8 : 6 6 50 67 9 런 9 : 5 8 런 0 : 0 6 8 59 76 런 : 85 6
() 대체선택 (replacement selection) u 런생성방법. 입력에서버퍼에 m개의레코드를판독하고첫번째런생성을시작. 버퍼로부터키값이가장작은레코드를선정해서출력. 입력에서다음레코드를판독해출력된레코드와대체 if ( 입력레코드의키값 < 출력된레코드의키값 ) then 레코드에 동결 (frozen) 로표시 동결된레코드는단계 의선정작업대상에서제외 동결되지않은레코드가있으면단계 부터실행. 동결된레코드들을모두해제하고단계 로돌아가새로운런을생성 u 특징 내부정렬과달리입력의일부정렬된레코드들의순서를이용 내부정렬을이용한경우보다런의길이가길다. 런의평균예상길이 : m 7 () 대체선택 (replacement selection) u 런생성결과 (m=5) 런 : 5 9 60 68 09 런 : 6 9 8 8 7 55 76 78 86 98 런 : 0 7 5 0 6 7 9 99 런 : 6 8 9 50 7 80 89 9 런 5 : 6 6 5 59 67 76 8 85 런 6 : 0 6 8 8
대체선택알고리즘 replacementselection() // 대체선택알고리즘 // m : 버퍼에들어가는레코드수 // Buffer[] : 버퍼-레코드배열 // written[] : 해당버퍼레코드가출력되었는지를나타내는플래그배열 // frozen[] : 해당버퍼레코드가동결되었는지를나타내는플래그배열 // lastkey : 마지막으로런에출력된레코드키값 // input : 입력 for (i 0; i < m; i++) written[i] true; i 0; readfrom(buffer[i], input); written[i] false; i i + ; } while (i < m &&!end-of-file(input) ); // 런들을생성 while (!end-of-file(input)) { // 새로운런을생성 for (i 0; i < m; i++) // 동결플래그초기화 if (!written[i]) frozen[i] false; 9 대체선택알고리즘 while (any unfrozen records remain) { // 레코드하나를런에출력 select smallest unfrozen record Buffer[s]; appendtorun(buffer[s]); lastkey Buffer[s].key; written[s] true; frozen[s] true; if (!end-of-file(input)) { readfrom(buffer[s], input); written[s] false; if (Buffer[s].key > lastkey) frozen[s] false; } } } // 버퍼에있는나머지레코드들을출력 appendtorun(unwritten Buffer[] records in ascending key order); end replacementselection() 0
() 자연선택 (natural selection) u 특징 동결된레코드들을버퍼에유지하지않고보조저장장치의저장소 (reservoir) 에별도저장 하나의런생성작업은저장소가꽉차거나입력의끝에도달할때까지계속 런을길게만들어런수를줄임으로써합병비용을줄임 u 런생성결과 ( 버퍼 버퍼크기 (m)=5, 저장소크기 (m) =5 =5) 런 : 5 7 9 60 68 09 런 : 6 9 8 8 0 55 6 76 78 86 9 98 99 런 : 0 6 7 9 5 50 67 7 7 80 89 9 런 : 8 6 6 5 59 76 8 85 런 5 : 0 6 8 자연선택알고리즘 naturalselection() // 자연선택알고리즘 // m, m' : 버퍼와저장소의크기 ( 레코드수 ) // Buffer[] : 버퍼-레코드배열 // written[] : 해당버퍼레코드가출력되었는지를나타내는플래그배열 // reservoir-count : 저장소에저장된레코드수 // spacefull : 저장소의만원을나타내는플래그 // lastkey : 마지막으로출력된레코드키값 // input : 입력 for ( i 0; i < m; i++) written[i] true; i 0; readfrom(buffer[i], input); written[i] false; i i + ; } while (i < m && (!end-of-file(input) ); reservoir-count 0; // 로부터레코드를읽어런에출력 // 런하나를생성 spacefull false; // 레코드하나를출력 select smallest unwritten record Buffer[s]; appendtorun(buffer[s]); lastkey Buffer[s].key; written[s] true;
자연선택알고리즘 if (!end-of-file(input)) { readfrom(buffer[s], input); if (Buffer[s].key lastkey) { written[s] false; } else { move Buffer[s] to reservoir; reservoir-count reservoir-count + ; if (reservoir-count = m') spacefull true; } } } while (written[s] &&!spacefull &&!end-of-file(input)); } while (!end-of-file(input) &&!spacefull); appendtorun(unwritten Buffer[] records in ascending key order); settrue(corresponding elements of written[]); // 다음런을생성하기위해버퍼정리 if (reservoir-count >0) { res-records min(reservoir-count, m); for (i 0; i < res-records; i++) { moveto(a record from reservoir, Buffer[i]); written[i] false; reservoir-count reservoir-count - ; } } if (Buffer[] not full &&!end-of-file(input)) { fillbuffer(with records from input); setfalse(corresponding elements of written[]); } } while (unwritten records exist in Buffer[]); end naturalselection() 런생성방법의비교 u 내부정렬 마지막런을제외하고모든런들의길이가같음 런의길이를예측할수있으므로합병알고리즘이간단 u 대체선택 내부정렬보다평균적으로훨씬긴런을생성 런의길이가길수록합병비용이적음 런의길이가일정치않아정렬 / 합병알고리즘이복잡 u 자연선택 앞의두방법보다더긴런을생성할수있음 저장소로의입출력이문제가됨 긴런생성에따른효율화가저장소전송비용보다이익이될수도있음
정렬 / 합병기법의차이 u 정렬 / 합병기법의차별화요소 적용하는내부정렬방식 내부정렬을위해할당된메인메모리의크기 정렬된런들의보조저장장치에서의저장분포 정렬 / 합병단계에서동시에처리할수있는런의수 u 이런요소에따라런의수와합병의패스 (pass) 수가결정 패스 (pass): 최종생성을위한반복적실행과정 u 정렬 / 합병기법의성능비교 정렬단계에서만들어지는런의수와합병의패스수비교 보조저장장치에대한상대적참조빈도수 (reference frequency) 전체레코드집합에대해수행되어야할정렬 / 합병의패스수비교 레코드들의판독 / 기록횟수 가능한런의길이를길게만들면합병해야될런의수는최소화 동시에합병할수있는런의수를늘리면합병의패스수는감소 입력런을보조저장장치에분산저장하면합병에필요한입출력뿐만아니라부수적인입출력연산도동반 5 합병단계 u 합병수행방법 m-원합병 (m-way merge) 균형합병 (balanced merge) 다단계합병 (polyphase merge) 계단식합병 (cascade merge) 6
v m-원합병 (m-way merge) u 특징 m개의입력을동시에처리하는합병 m개의입력로부터하나의출력을생성 총 m+개의을사용 입력수를합병의원수 (degree) 라함 많은입출력 : 한패스에합병이끝나지않으면런들을입력로다시분배하기위해복사와이동을해야함 이상적정렬 / 합병 : m개의런에 m개의입력을사용하여한번의 m-원합병으로완료 u -원합병의경우 한번의패스 : 합병된런의크기는 배, 런의수는반 N개의런으로분할된정렬위한패스수 : élog N ù 7 6 개의런에대한 -원합병 () 정렬단계 () 차합병 내부정렬 6000 레코드정렬된 6개의런을 개의입력로분배 000 레코드씩정렬된 6 개의런 런 5 00-5000 런 6 500-6000 () 차합병 런 00-000 런 00-000 런 -000 런 00-000 에있는 개의런을 개의입력로분배 차합병 런 (+) 런 (+) 런 (5+6) 런 (5+6) 런 (+) 런 (+) 차합병 런 (+++) 런 (5+6) () 차합병런 (+++) 런 (5+6) 차합병 ( 개의입력과 개의출력 ) 런 (++++5+6) 8
개의런에대한 -원합병 () 정렬단계 내부정렬 500 레코드씩정렬된 개의런 6000 레코드 정렬된 개의런을 개의입력로분배 () 차합병 런 런9... 런 런 런0... 런 차합병 런 (+) 런 (+)... 런 (+) 에있는 6 개의런을 개의입력로분배 () 차합병 런 (9+0) 런 (5+6) 런 (+) 런 (+++) 차합병 런 (5+6+7+8) 런 (9+0++) 런 (+) 런 (7+8) 런 (+) 에있는 개의런을 개의입력로분배 9 개의런에대한 -원합병 () 차합병 런 (+++) 런 (9+0++) 차합병 런 (++++5+6+7+8) 런 (9+0++) 런 (5+6+7+8) (5) 차합병 런 (++++5+6+7+8) 차합병 런 (+++... + +) 런 (9+0++) 0
6개의런에대한 -원합병 () 정렬단계 내부정렬 000레코드씩정렬된 6개의런 6000 레코드 정렬된 6 개의런을 개의입력로분배 () 차합병 런 런 런5 런 차합병 런 (++) 런 (+5+6) 런 6 런 에있는런을 개의입력로분배 ( 이경우에는 개의만사용됨 ) () 차합병런 (++) 런 (+5+6) 차합병 런 (++..+6) ( 개의입력과 개의출력 ) m-원합병알고리즘 mwaymerge() // m-원합병알고리즘 // m : 입력의수 // FILE[] : 배열 // outfilenum : 출력을포함하는배열의인덱스 // r : 현단계에서합병되지않고입력에남아있는런수 // runcount : 현단계에서생성된런의수 // 합병단계 openfile(file[],..., FILE[m]); // for reading openfile(file[m+]); // for writing runcount 0; mergeruns(file[],..., FILE[m] FILE[m+]); runcount runcount + ; } while (!end-of-file on any one input file); // 합병되지않고입력에남아있는런수의계산및 // 다음단계의출력선택 r 0; for (i m; i ; i--) { if (!end-of-file(file[i])) r r + ; else outfilenum i; } runcount runcount + r;
// 을배열에재할당 FILE[],..., FILE[m+] FILE[],..., FILE[outfilenum-], FILE[outfilenum+],..., FILE[m+],..., FILE[outfilenum]; closefile(file[],..., FILE[m]); // 런들의분산단계 openfile(file[m]); // for reading openfile(file[],..., FILE[m-]); // for writing // FILE[],..., FILE[m] 내의런수의차이가 이하가되도록 // runcount/m, runcount/m -, runcount/m - 개씩의런들을배분 i 0; k m * runcount/m - runcount; i i + ; if (k = 0) { if (end-of-file(file[i])) move( runcount/m runs, from FILE[m] to FILE[i]); else move (( runcount/m - ) runs, from FILE[m] to FILE[i]); } else { k k - ; if (end-of-file(file[i])) move(( runcount/m - ) runs, from FILE[m] to FILE[i]); else move (( runcount/m - ) runs, from FILE[m] to FILE[i]); } } while (i m-); } while (runcount ); // 정렬된최종목표은 FILE[m] end mwaymerge() 선택트리 (selection tree) () u m개의런을하나의큰런으로정렬 m개의런 ( 레코드 ) 중가장작은키값의레코드를계속선택, 출력 간단한방법 : m-번비교 선택트리 : 비교횟수를줄일수있음 u 선택트리의종류 승자트리 (winner tree) 패자트리 (loser tree)
선택트리 () u 승자트리 (winner tree) 특징 완전이진트리 각단말노드는각런의최소키값원소를나타냄 내부노드는그의두자식중에서가장작은키값을가진원소를나타냄 런이 8개 (k=8) 인경우승자트리예 [] 7 [] 7 9 [] [] [5] [6] [7] 0 7 9 8 [8] [9] [0] [] [] [] [] [5] 0 7 9 0 50 8 6 8 8 6 0 8 0 5 59 9 런 런 런 런 런 5 런 6 런 7 런 8 5 선택트리 () 승자트리구축과정 가장작은키값을가진원소가승자로올라가는토너먼트경기로표현 트리의각내부노드 : 두자식노드원소의토너먼트승자 루트노드 : 전체토너먼트승자, 즉트리에서가장작은키값가진원소 승자트리의표현 승자트리는완전이원트리이기때문에순차표현이유리 인덱스값이 i 인노드의두자식인덱스는 i 와 i+ 합병의진행 루트가결정되는대로순서순차에출력 ( 여기선 7) 다음원소즉키값이 인원소가승자트리로들어감 승자트리를다시재구성 노드 에서부터루트까지의경로를따라가면서형제노드간토너먼트진행 6
선택트리 () 다시만들어진승자트리의예 [] 9 [] 0 [] 9 [] [5] [6] [7] 0 9 8 [8] [9] [0] [] [] [] [] [5] 0 9 0 50 8 6 8 런 8 런 런 6 0 런 0 런 5 8 런6 5 59 런 7 9 런 8 이런방식으로순서순차구축을계속함 7 선택트리 (5) u 패자트리 (loser tree) 루트위에 0 번노드가추가된완전이원트리 성질 () 단말노드 : 각런의최소키값을가진원소 () 내부노드 : 토너먼트의승자대신패자원소 () 루트 ( 번노드 ) : 결승토너먼트의패자 () 0 번노드 : 전체승자 ( 루트위에별도로위치 ) 8
선택트리 (6) 런이 8 개 (k=8) 인패자트리의예 [0] 7 출력 [] 9 [] 0 [] 8 [] [5] [6] [7] 0 50 [8] [9] [0] [] [] [] [] [5] 0 7 9 0 50 8 6 8 런 8 런 런 6 0 런 0 런 5 8 런 6 5 59 런 7 9 런 8 9 선택트리 (7) 패자트리구축과정 단말노드 : 각런의최소키값원소 내부노드 두자식노드들이부모노드에서토너먼트경기를수행 패자는부모노드에남음 승자는그위부모노드로올라가서다시토너먼트경기를계속 번루트노드 마찬가지로패자는 번루트노드에남음 승자는전체토너먼트의승자로서 0 번노드로올라가순서순차에출력됨 합병의진행 출력된원소가속한런 의다음원소, 즉키값이 인원소를패자트리노드 에삽입 패자트리를다시재구성 토너먼트는노드 에서부터루트노드 까지의경로를따라경기를진행 다만경기는형제노드대신형식상부모노드와경기를함 0
v 균형합병 (balanced merge) M- 원합병의단점 : 의재분배에많은 I/O 필요 u 균형합병 출력할때, 미리다음단계에사용할입력로재분배즉, 출력을다음단계의입력로직접사용 m- 원자연합병 : m + 개의필요 m- 원균형합병 : m 개의필요 (m 입력, m 출력 ) u 각합병단계후 런의총수는합병차수로나눈만큼감소 런의길이는합병차수의두배씩증가 O(log m N), N : 초기런의수 개의런에대한 -원균형합병 () 정렬단계 6000 레코드 내부정렬 000 레코드씩정렬된 6 개의런 생성된 개의런을 개의에분배 () 차합병 런 런 9... 런 차합병 런 (+) 런 (5+6) 런 (9+0) 런 런 0... 런 런 (+) 런 (7+8) 런 (+) () 차합병 런 (+) 런 (5+6) 런 (9+0) 차합병 런 (+++) 런 (9+0++) 런 (+) 런 (7+8) 런 (+) 런 (5+6+7+8)
개의런에대한 -원균형합병 () 차합병 런 (+++) 런 (9+0++) 런 (++++5+6+7+8) 차합병 런 (5+6+7+8) 런 (9+0++) (5) 차합병 런 (++++5+6+7+8) 차합병 런 (+++... +) 런 (9+0++) 주의런 () 은 번판독 / 기록되었음. m-원균형합병알고리즘 balancedmerge() // m-원균형합병알고리즘 // m : 입력수 ( 모두 m개의사용 ) // FILE[] : 배열 // input-set-first : 현단계에서입력과출력세트를구분하기위한플래그 // base : 출력세트의첫번째번호 // outfilenum : 현단계의출력번호 // runcount : 현단계에서생성된런의수 input-set-first false; if (input-set-first) { input-set-first false; openfile(file[],..., FILE[m]); // for reading; openfile(file[m+],...,file[m]); // for writing; base m + ; } else { input-set-first true; openfile(file[],..., FILE[m]); // for writing; openfile(file[m+],...,file[m]); // for reading; base ; }
m-원균형합병알고리즘 // 합병단계의수행 outfilenum 0; runcount 0; mergerun(input files FILE[base+outfilenum]); runcount runcount + ; outfilenum (outfilenum + ) % m; } while (!end-of-file on all input files); rewind(input files and output files); } while (runcount ); // input-set-first 가 true 면최종정렬은 m+, // false 면최종정렬은 end balancedmerge() 5 v 다단계합병 (Polyphase Merge) u m-원균형합병기법 m개의이필요 (m개입력, m개출력 ) 단점 : 하나의합병된런이생성되는동안 m- 개의파일은항상유휴상태 u m-원다단계합병 (m-way polyphase merge) 유휴문제와런의단순복사문제를개선 m 개의입력과 개의출력을사용 입 / 출력수가같지않음 : " 불균형 " 합병 초기입력에대한런의 불균등 분배가복잡 u 각합병단계 (pass) 입력의어느하나가이될때까지만런들을합병 이된입력은다음합병단계의출력이됨 6
-원다단계합병의예 50 0 95 5 00 0 50 0 0 60 70 0 0 0 80 : 50 95 0 0 0 50 0 80 0 : 0 80 0 : 5 0 00 60 70 0 : : : 5 0 50 95 00 0 0 60 70 0 0 50 (a) 정렬단계결과 (b) 차합병결과 : : 5 0 0 0 50 60 70 80 95 00 0 0 0 0 50 : 5 0 0 50 80 95 00 0 0 : : 0 60 70 0 0 50 : (c) 차합병결과 (d) 차합병결과 7 -원다단계합병에서런수의변화 u 각합병단계마다하나의입력만이됨 정렬단계 차합병 차합병 차합병 런합계 0 0 0 0 0 5 8
초기생성할런수의결정방법 u -원다단계합병을위한런수 (m m = ) [,, ],, 5, 9, 7,, u 차 (m=) 피보나치 (Fibonacci) 수열 T i = T i - + T i - + T i -, i > T i =, i u m차피보나치수열 T i =, i m i Ti = å - Tk, i > k = i - m m 9 완전피보나치런분배방법 (m m = ) u 원으로표시된수를다음단계의다른에합산시킴 차 차 차 차 7 6 런수 5 9 7 0
완전피보나치분배 u m-원다단계합병을위한초기의런수를 m차피보나치수열의한항이되는수가되도록생성 u 이런들을피보나치분배방법에따라분배 u 완전피보나치분배의장점 합병단계에서마지막패스를제외하고는각패스가끝날때항상하나의입력만이됨 합병을위한각패스에서입력수는항상 m 이됨 마지막패스에서는입력이모두동시에이되면서모든런들이출력에하나의런으로만들어짐 합병단계에서패스수가줄어듬 -원다단계합병 정렬단계 6000 레코드 내부정렬 차합병 7개의런 6개의런 개의런 차합병 개의런 런, 런 6, 런 7, 런 0, 런, 런, 런 런, 런, 런, 런 5, 런 6, 런 7 런, 런 5, 런 8, 런 9 은이됨 차합병 개의런 개의런 개의런 차합병 개의런 개의런 개의런 차합병 차합병 개의런 차합병 개의런 개의런 개의런 차합병 개의런 개의런 는이됨은이됨 는이됨
각합병단계에서당런수의변화 런합계 정렬단계 차합병 차합병 차합병 차합병 7 0 6 0 0 0 0 0 0 7 9 5 u 초기런에대한완전피보나치분배방법의역순 -원다단계합병의예 50 0 95 5 00 0 50 0 0 60 70 0 0 0 80 : 50 95 0 : : 5 0 00 60 70 0 : 60 70 0 : 0 0 50 0 80 0 : 0 80 0 : : 5 0 0 50 95 00 0 0 50 (a) 정렬단계결과 (b) 차합병결과 : : : : 5 0 0 0 50 60 70 80 95 00 0 0 0 0 50 (c) 차합병결과
m-원다단계합병알고리즘 polyphasemerge() // m-원다단계합병알고리즘 // m : 입력의수 // FILE[] : 배열 // 입력에는피보나치분배방법으로런들이분배되었다고가정 // 준비 for (i ; i m; i++) openfile(file[i]); // for reading; openfile(file[m+]); // for writing; // 합병단계 mergerun(file[],..., FILE[m] FILE[m+]); } while (!end-of-file(file[m])); rewind(file[m] and FILE[m+]); closefile(file[m] and FILE[m+]); openfile(file[m+]); // for reading openfile(file[m]); // for writing // 을배열에재할당 FILE[], FILE[],..., FILE[m+] FILE[m+], FILE[],..., FILE[m]; } while (!end-of-file on all files on FILE[],..., FILE[m]); // 정렬된최종목표은 FILE[] end polyphasemerge() 5 v 계단식합병 (Cascade Merge) 정렬 / 합병과정에서런들의복사작업을줄이려는불균형합병의또다른형태 u m-원계단식합병 (m-way cascade merge) 초기런생성과런의분배가중요 ( 완전피보나치분배 ) 합병을위한입력수가 m개에서시작하여 m-, m-,, 로줄어들어마지막 개로될때한주기가끝남 합병단계 m개의입력로부터 m개의런을하나의런으로합병하여출력로생성 입력하나가이되면이이새로운출력로되고이전의출력은대기 나머지입력들은이새로운출력로합병된런을생성 개의입력을합병하는단계가되면합병의한주기가종료 한주기에각레코드는한번씩만처리 6
-원계단식합병 50 0 95 5 00 0 50 0 0 60 70 0 0 0 80 : 50 0 95 : : 5 0 00 60 70 0 : 60 70 0 : 0 0 50 0 80 0 : 0 80 0 : : 5 0 0 50 95 00 0 0 50 (a) 정렬단계결과 (b) 합병 주기 차합병결과 : 0 60 70 80 0 0 : : : 5 0 0 0 50 60 70 80 95 00 0 0 0 0 50 : : : 5 0 0 50 95 00 0 0 50 : (c) 합병 주기 차합병결과 (d) 합병 주기 차합병결과 7 -원계단식합병 합병 주기 7개의런 주기 6개의런 패스 개의런 개의런 은 는대기 합병 주기 합병 주기 개의런 개의런 개의런 개의런 주기패스 개의런 주기패스 개의런 개의런 개의런 개의런 주기패스 개의런 개의런 주기 개의런 패스 개의런 개의런 과 는 는 은대기 은 는대기 은 은대기 은대기 합병 주기 개의런 개의런 주기패스 개의런 는 8
m-원계단식합병알고리즘 cascademerge() // m-원계단식합병알고리즘 // m : 입력의수 // FILE[] : 배열 // 입력에는완전피보나치분배에따라런들이분배되어있다고가정 // 의준비 for (i ; i m; i++) openfile(file[i]); // for reading; openfile(file[m+]); // for writing; // 합병단계 i 0; i i + ; mergeruns(file[],..., FILE[m-i+] FILE[m-i+]); } while (!end-of-file(file[m-i+])); rewind(file[m-i+] and FILE[m-i+]); closefile(file[m-i+] and FILE[m-i+]); // 하나이상의이비었을경우해당단계를생략함 empty-file true; k ; 9 m-원계단식합병알고리즘 while (empty-file && i < m-) { if (end-of-file(file[m-i+-k])) { i i + ; k k + ; rewind(file[m-i+-k]); closefile(file[m-i+-k]); } else empty-file false; } // 다음단계의출력준비 openfile(file[m-i+]); // for writing } while (i m-); // 을런수의내림차순으로정렬한후배열에재할당 reallocatefiles(file[],..., FILE[m+], run count of FILE[] run count of FILE[]... run count of FILE[m+]); // 남은수의재조정 no-more-empty false; if (end-of-file(file[k])) m m - ; else no-more-empty true; } while (m &&!no-more-empty); } while (m ); // 최종정렬된목표은 FILE[] end cascademerge() 50
v 정렬 / 합병유틸리티 u 정렬 / 합병유틸리티 (utility) 를이용 범용의정렬 / 합병작업을지원 u 유틸리티의기능 () 하나또는그이상의정렬 () 둘또는그이상의합병 () 둘또는그이상의정렬과합병 u 정렬 / 합병패키지사용시명세내용 () 정렬 / 합병할의이름 () 정렬 / 합병의키필드의데이타타입, 길이, 위치 () 키필드들의순서 (major에서 minor 순으로 ) () 각키필드에적용할정렬순서 (ASC, 또는 DES) (5) 각키필드에적용될순서기준 (6) 정렬 / 합병결과를수록할출력의이름 5 패키지에서사용자명세사항 () 사용자가정의한정렬순서및기준 () 내부정렬단계에서사용할알고리즘 ( 예 : quicksort, heapsort) () 합병단계에서사용할알고리즘 ( 예 : 균형, 다단계, 계단식합병 ) () 사용전후에필요한동작 ( 예 : rewind, unload) (5) 합병단계에서입력레코드가올바른순서로되어있는가의검사 (6) 회복을위한체크포인트 (check point)/ 덤프레코드 (dump record) 를사용하는주기 (7) 예상입력레코드수 5
유틸리티를이용한정렬 / 합병의예 / / SORTNOW EXEC SORTMRG / / SORTIN DD DSN = name of input file,..., / / DISP = (OLD, KEEP) / / SORTOUT DD DSN = name of output file,..., / / DISP = (NEW, KEEP) / / SYSIN DD * / * SORT FIELDS=(,,CH,A,0,0,CH,D), FILEZ=E000 SORTMRG(input-filename, output-filename)... SORT, VAR = POLY FILE, INPUT = name(cu), OUTPUT = name(r) FIELD, DEPT(,,ASCII6), SALEDATE(0, 0, ASCII6) KEY, DEPT(A,ASCII6), SALEDATE(D, ASCII6) job control command 5 v 저장장치와정렬 / 합병 u 합병단계에서사용되는외부저장장치의물리적특성도정렬 / 합병시간에영향 u 순차접근만허용되는자기테이프의경우 각이서로다른릴에저장 테이프 rewind 시간이필요 u 임의접근이가능한디스크의경우 정렬 / 합병될들이하나의디스크에저장 디스크입 / 출력연산 ( 탐구시간 + 회전지연시간 ) 이테이프 ( 시작시간 + 정지시간 ) 보다더많은오버헤드를수반. 그러나테이프보다훨씬빠른데이타전송률로보상 탐구와회전지연에따른접근오버헤드감축방법 들을 개이상의디스크로분산시켜입 / 출력연산을병렬처리 의입 / 출력요구를병렬로처리하기위해서는디스크마다별도의디스크제어기가있어야됨 5