자료처리 () 006 년봄학기문양세강원대학교컴퓨터과학과 정렬 / 합병의개요 정렬의종류 : 내부정렬, 외부정렬 내부정렬 (internal sorting) 데이타가적어서메인메모리내에모두저장시켜정렬가능할때사용함 레코드의판독 (read) 및기록 (write) 에걸리는시간이문제가되지않음 외부정렬 (external sorting) 데이타가많아서메인메모리의용량을초과하여보조기억장치 ( 디스크, 테이프 ) 에저장된을정렬할때사용함 레코드판독및기록에걸리는시간이중요한요소임 정렬 / 합병 (sort/merge) 런 (run): 하나의을여러개의서브 (subfile) 로나누어내부정렬기법을사용하여정렬시킨 런을합병하여원하는하나의정렬된을만듦 Page
의정렬 / 합병 정렬단계 (sort phase) 정렬할의레코드들을지정된길이의서브로분할한후, 각각을정렬하여런 (run) 을만들고, 이를입력로분배하는단계 합병단계 (merge phase) 정렬된런들을합병해서보다큰런으로만들고, 이들런을다시입력로재분배하여합병하는방식으로, 최종적으로모든레코드들이하나의런에포함되도록만드는단계 Sub-file 8 5 5 6 sort 6 5 8 5 merge 5 8 6 5 Run Page 정렬단계 (Sort Phase) 런 (run) 의생성방법 ( 내의레코드들을여러개의런으로나누고, 키순서에따라정렬하는방법 ) 내부정렬 (internal sort) 대체선택 (replacement selection) ( skip) 자연선택 (natural selection) ( skip) 입력의예 0 68 5 60 8 8 6 55 8 8 6 0 5 86 0 6 6 80 8 8 50 6 6 6 8 5 5 0 8 6 6 85 Page
런생성 내부정렬 (Internal Sort) 런생성방법. 을 n개의레코드씩분할. 분할된레코드들을내부정렬기법 (bubble sort, quick sort, ) 으로정렬 런생성결과 제일마지막런을제외하고모두길이가동일함 가정 : 메인메모리는 5개의레코드를유지할수있음 런 : 5 68 0 런 : 8 8 60 런 : 6 55 8 런 : 5 0 6 8 86 런 5 : 0 6 런 6 : 6 런 : 8 80 8 런 8 : 6 6 50 6 런 : 5 8 런 0 : 0 6 8 5 6 런 : 85 Page 5 합병단계 합병수행방법 ( 여러개의런들을합병하여하나의정렬된런을만드는방법 ) m-원합병 (m-way merge) 균형합병 (balanced merge) 다단계합병 (polyphase merge) 계단식합병 (cascade merge) Page 6
m-원합병 (m-way Merge) 특징 m개의입력을동시에처리하는합병 ( 런은 m개이상 ) 입력 m개, 하나의출력 : 총 m+개의을사용 많은입출력한패스에합병이끝나지않으면, 런들을다시분배하기위해복사, 이동을통하여여러패스를거쳐서합병을수행해야함 이상적정렬 / 합병 : m개의런에 m개의입력사용하여한번의 m-원합병을적용 - 원합병인경우 첫번째패스 : 합병된런의크기는 배, 런의수는반 N 개의런으로분할된정렬위한패스수 : logn Page 6개의런에대한 -원합병 () 정렬단계 내부정렬 000 레코드씩정렬된 6 개의런 6000 레코드 () 차합병 정렬된 6 개의런을 개의에분배한다. 런 5 00-5000 런 6 500-6000 런 00-000 런 00-000 런 -000 런 00-000 차합병 런 (+) 런 (+) 런 (5+6) 에있는 개의런을 개의에분배한다. () 단계합병 런 (5+6) 런 (+) 런 (+) 차합병 런 (+++) 런 (5+6) (5) 단계합병 런 (+++) 런 (5+6) 차합병 런 (++++5+6) ( 개의입력과 개출력 ) Page 8
개의런에대한 -원합병 (/) () 정렬단계 6000 레코드 정렬된 개의런을 개의에분배한다. 내부정렬 500 레코드씩정렬된 개의런 () 차합병 런 런... 런 런 런0... 런 차합병 런 (+) 런 (+)... 런 (+) 에있는 6 개의된런을 개의에분배한다. () 차합병 런 (+0) 런 (5+6) 런 (+) 런 (+++) 차합병 런 (5+6++8) 런 (+0++) 런 (+) 런 (+8) 런 (+) 에있는 개의된런을 개의에분배한다. Page 개의런에대한 -원합병 (/) () 차합병 런 (+++) 런 (+0++) 차합병 런 (++++5+6++8) 런 (+0++) 런 (5+6++8) (5) 차합병 런 (++++5+6++8) 차합병 런 (+++... + +) 런 (+0++) Page 0 5
6개의런에대한 -원합병 () 정렬단계 6000 레코드 내부정렬 000 레코드씩정렬된 6 개의런 정렬된 6 개의런을 개의입력에분배한다. () 차합병 런 런 런5 런 차합병 런 (++) 런 (+5+6) 런 6 런 에있는런을 개의입력에분배한다.( 이경우에는 개의만사용됨 ) () 단계합병 런 (++) 런 (+5+6) 차합병 런 (++..+6) (개의입력과 개의출력 ) Page 선택트리 (Selection Tree) m 개의런을하나의큰런으로정렬 m개의런중에서가장작은키값의레코드를계속선택, 출력 간단한방법 : m-번비교 선택트리 : 비교횟수를줄일수있음 (m 개의런중에서가장작은값을선택하는효과적인방법 ) 선택트리의종류 승자트리 (winner tree) 패자트리 (loser tree) Page 6
승자트리 (Winner Tree) (/) 특징 완전이진트리 (Complete Binary Tree) 각단말노드는각런의최소키값의원소를나타냄 내부노드는그의두자식중에서가장작은키값을가진원소를나타냄 런이 8 개 (k = 8) 인경우승자트리의예 [] [] [] [] [5] [6] [] 0 8 Array Index [8] [] [0] [] [] [] [] [5] 0 0 50 8 6 8 런 8 런 런 6 0 8 0 런 5 5 런 5 런 6 런 Page 런 8 승자트리 (Winner Tree) (/) 승자트리구축과정 가장작은키값을가진원소가승자로올라가는토너먼트경기로표현 트리의각내부노드 : 두자식노드원소의토너먼트승자 루트노드 : 전체토너먼트승자, 즉트리에서가장작은키값가진원소 승자트리의표현 승자트리는완전이원트리이기때문에순차표현이유리 인덱스값이 i인노드의두자식인덱스는 i와 i+ (Array로표현이매우용이함 ) 합병의진행 루트가결정되는순서에따라순차적으로 ( 본예에서는) 다음원소, 즉키값이인원소가승자트리로들어감 (출력이후 이들어감 ) 승자트리를다시재구성 ( 예 : 노드 ( 키값) 에서부터루트까지의경로를따라가면서형제노드간토너먼트진행 ) Page
승자트리 (Winner Tree) (/) 승자트리의재구성예 ( 이출력된이후의변화 ) [] [] [] [] [] 0 [] [] [5] [6] [] 0 8 [] [5] [6] [] 0 8 [8] [] [0] [] [] [] [] [5] 0 0 50 8 [8] [] [0] [] [] [] [] [5] 0 0 50 8 6 8 런 8 런 런 6 0 0 8 5 5 6 8 8 6 0 0 8 런 런 5 런 6 런 런 8 런 런 런 런 런5 런6 5 5 런 런 8 상기와같은재구성을반복하면서합병을진행함 Page 5 패자트리 (Loser Tree) (/) 루트노드위에 0 번노드가추가된완전이진트리 특징 () 단말노드 : 각런의최소키값을가진원소 () 내부노드 : 토너먼트의승자대신패자원소 ( 다음슬라이드의예를보고이해할것 ) () 루트 (번노드): 결승토너먼트의패자 () 0번노드 : 전체승자 ( 루트위에별도로위치 ) Page 6 8
패자트리 (Loser Tree) (/) 패자트리의예 : 런이 8 개 (k = 8) 인경우의예 [0] 출력 [] [] 0 [] 8 [] [5] [6] [] 0 50 [8] [] [0] [] [] [] [] [5] 0 0 50 8 6 8 런 8 런 런 6 0 런 0 런 5 8 런 6 5 5 런 런 8 Page 패자트리 (Loser Tree) (/) 패자트리구축과정 단말노드 : 각런의최소키값원소 내부노드 두자식노드들이부모노드에서토너먼트경기를수행 패자는부모노드에남음 승자는그위부모노드로올라가서다시토너먼트경기를계속 번루트노드 마찬가지로패자는 번루트노드에남음 승자는전체토너먼트의승자로서 0 번노드로올라가순서에따라서출력됨 합병의진행 그림의예에서, 출력된원소 () 가속한런의다음원소, 즉키값이인원소를패자트리의노드 에삽입 패자트리를다시재구성 토너먼트는노드 에서부터루트노드 까지의경로를따라경기를진행 다만, 경기는형제노드대신형식상부모노드와경기를함 Page 8
패자트리 (Loser Tree) (/) 패자트리의재구성예 ( 이출력된이후의변화 ) [0] [0] 출력 출력 [] [] 0 [] 0 [] 8 [] [] 8 [] [5] [6] [] 0 50 [] [5] [6] [] 0 50 [8] [] [0] [] [] [] [] [5] 0 0 50 8 [8] [] [0] [] [] [] [] [5] 0 0 50 8 6 8 런 8 런 런 6 0 런 0 런 5 5 6 8 5 8 8 6 0 8 0 런 6 런 런 8 런 런 런 런 런 5 런 6 5 5 런 런 8 상기와같은재구성을반복하면서합병을진행함 Page 균형합병 (balanced merge) (/) 기본적인 m- 원합병의단점 : 합병과정에서의재분배 ( m) 로인한많은 I/O 발생 균형합병 출력할때, 미리다음단계에사용할입력로재분배즉, 출력을다음단계의입력로직접사용 m-원합병 : m + 개의필요 ( 입력 m개, 출력 개 ) m-원균형합병 : m 개의필요 ( 입력 m개, 출력 m개 ) 각합병단계후 런의총수는합병차수 (m) 로나눈만큼감소 ( 합병할때마다런의개수는감소 ) 런의길이는합병차수 (m) 의두배씩증가 ( 합병할때마다런의길이는증가 ) O(log m N), N = 초기런의개수 Page 0 0
균형합병 (balanced merge) (/) 개의런에대한 - 원균형합병 () 정렬단계 6000 레코드 내부정렬 000 레코드씩정렬된 6 개의런 생성된 개의런을 개의에분배한다. () 차합병런 런... 런 런 (+) 런 (5+6) 런 (+0) 차합병 런 런 0... 런 런 (+) 런 (+8) 런 (+) () 차합병런 (+) 런 (5+6) 런 (+0) 런 (+++) 런 (+0++) 차합병 런 (+) 런 (+8) 런 (+) 런 (5+6++8) Page 균형합병 (balanced merge) (/) 개의런에대한 - 원균형합병 ( 계속 ) () 차합병 런 (+++) 런 (+0++) 런 (++++5+6++8) 차합병 런 (5+6++8) 런 (+0++) (5) 차합병 런 (++++5+6++8) 차합병 런 (+++... +) 런 (+0++) Page
다단계합병 (polyphase merge) (/8) m- 원균형합병의고찰 m개의필요 (m개입력, m개출력 ) 단점 : ( 출력중에서 ) m- 개의은항상유휴상태 유휴문제의해결을위해, 런의단순복사연산을개선 m- 원다단계합병 m개의입력과 개의출력 ( 기본 m-원합병과동일 ) 입 / 출력수가같지않음 : 불균형 합병 초기입력에대한런의분배가복잡 각합병단계 (pass) 입력의어느하나가이될때까지런들을합병 이된입력이다음합병단계의출력이됨 Page 다단계합병 (polyphase merge) (/8) - 원다단계합병의예 50 0 5 5 00 0 50 0 0 60 0 0 0 0 80 : 50 5 0 0 0 50 0 80 0 : 0 80 0 : 5 0 00 60 0 0 : : : 5 0 50 5 00 0 0 60 0 0 0 50 (a) 정렬단계결과 (b) 차합병결과 : : 5 0 0 50 80 5 00 0 0 : 0 60 0 0 0 50 (c) 차합병결과 : 5 0 0 0 50 60 0 80 5 00 0 0 0 0 50 : : (d) 차합병결과 Page
다단계합병 (polyphase merge) (/8) - 원다단계합병에서런의개수변화 정렬단계 차합병 차합병 차합병 런합계 0 0 0 0 0 5 Page 5 다단계합병 (polyphase merge) (/8) 초기런의분배방법 : 피보나치수열? 런의개수변화 -원합병인경우 :,,,, 5, 8,, -원합병인경우 :,,,, 5,,,, 피보나치 (Fibonacci) 수열 (m = ) T i = T i- + T i- + T i-, i > T i =, i 피보나치수열 ( 일반형 ) T i =, i m i Ti = T k, i > m k = i m Page 6
다단계합병 (polyphase merge) (5/8) - 원다단계합병 정렬단계 6000 레코드 내부정렬 차합병 개의런 6개의런 개의런 차합병 개의런 차합병 개의런 개의런 개의런 차합병 개의런 개의런 개의런 차합병 Page 차합병 개의런 차합병 개의런 개의런 개의런 차합병 개의런 개의런 런, 런 6, 런, 런 0, 런, 런, 런 런, 런, 런, 런 5, 런 6, 런 런, 런 5, 런 8, 런 은이됨 는이됨 은이됨 는이됨 다단계합병 (polyphase merge) (6/8) 초기런의분배방법 (m =, 런의수 = ) 제 차제 차제 차제 차 6 합계 5 Page 8
다단계합병 (polyphase merge) (/8) 각합병단계에서당런수의변화 (m =, 수 = ) 단계시작 단계끝 단계끝 단계끝 단계끝 합계 0 6 0 0 0 0 0 0 5 Page 다단계합병 (polyphase merge) (8/8) - 원다단계합병의예 50 0 5 5 00 0 50 0 0 60 0 0 0 0 80 : 50 5 0 : : 5 0 00 60 0 0 : 60 0 0 : 0 0 50 0 80 0 : 0 80 0 : (a) 정렬단계결과 : 5 0 0 50 5 00 0 0 50 (b) 차합병결과 : : : 5 0 0 0 50 60 0 80 5 00 0 0 0 0 50 : (c) 차합병결과 Page 0 5
계단식합병 (cascade merge) (/) 정렬 / 합병과정에서런들의복사작업을줄이기위한불균형합병의또다른형태 m- 원계단식합병 (m-way cascade merge) 주기 : m, m-, m-,, 그리고마지막에 개의입력을사용 런생성단계 : ( 다단계합병과마찬가지로 ) 런의초기분배가중요 합병단계 m개의입력로부터 m개의런을하나의런으로합병하여출력로생성 처음이되는입력이새로운출력이됨 m- 개의입력이이새로운출력로합병 개의입력을합병하는단계가되면합병의한주기가종료 한주기에각레코드는한번씩처리 Page 계단식합병 (cascade merge) (/) - 원계단식합병의예 50 0 5 5 00 0 50 0 0 60 0 0 0 0 80 : 50 0 5 : : 5 0 00 60 0 0 : 60 0 0 : 0 0 50 0 80 0 : 0 80 0 : : 5 0 0 50 5 00 0 0 50 (a) 정렬단계결과 (b) 합병 주기 차합병결과 : 0 60 0 80 0 0 : : : 5 0 0 0 50 60 0 80 5 00 0 0 0 0 50 : : : 5 0 0 50 5 00 0 0 50 : (c) 합병 주기 차합병결과 (d) 합병 주기 차합병결과 Page 6
계단식합병 (cascade merge) (/) 계단식합병에서런수의변화 (m =, 런의수 = ) 합병 주기 개의런 주기 6개의런 패스 개의런 개의런 은 는대기 개의런 개의런 주기패스 개의런 는 은대기 합병 주기 개의런 주기 개의런 패스 개의런 개의런 은 는대기 개의런 개의런 주기패스 개의런 은 은대기 Page 계단식합병 (cascade merge) (/) 계단식합병에서런수의변화 ( 계속 ) 합병 주기 개의런 주기 개의런 패스 개의런 개의런 과 는 은대기 합병 주기 개의런 개의런 주기패스 개의런 는 Page