제 7 장 정렬

Size: px

Start display at page:

Download "제 7 장 정렬"

우석 추
5 years ago
Views:

3 탐색 (2) template <class E, class K> int SeqSearch(E *a, const int n, const K& k) {// a[1:n] 을왼쪽에서오른쪽으로탐색한다. // a[i] 의키값이 k 와같은가장작은 i 를반환한다. // 그런 i 가없으면, 0 을반환한다. int i; for(i = 1; i <= n && a[i]!= k; i++); if(i>n) return 0; return i; } 순차탐색 n 개의레코드를가진리스트를탐색하기위해 O(n) 의시간이걸린다. 성공적인탐색을위한평균키비교횟수 (1 i n) ( n i 1) / n ( n 1) / 2 Copyright 2007 DBLAB, Seoul National University 3

4 탐색 (3) 이원탐색 (Binary Search) n 개의레코드를가진리스트를탐색하기위해 O(log n) 시간이걸림. ( 순차탐색보다빠르다 ) SeqSearch 코드를이원탐색에맞게수정 for 조건부분을 i<=n && a[i] < k 로변경 조건 i>n 을 i>n a[i]!= k 로함께변경 순차나이원탐색방법은실제로사람이사용하는탐색방법과대응되지않는다. Copyright 2007 DBLAB, Seoul National University 4

6 두개의레코드리스트의비교 미국국세청 (IRS) 에서고용주와피고용자에게개별적으로받은신고서들을비교하여모순점이있는지를검증하려함 IRS 에서받는신고서들 고용주는피고용자에게얼마를지급하였다고신고 피고용자는고용주로부터얼마를지급받았다고신고 고용주와피고용자에관련된두개의레코드리스트가생겨남 IRS 에도착되는신고서는임의순서대로접수 리스트의레코드역시임의순서대로배열되어있다고가정 키는피고용자의사회보장번호 ( 가정 ) (1) 고용주리스트에있는키와대응디는레코드가피고용자리스트에없으면메시지를피고용자에게보냄 (2) (1) 과반대인경우메시지를고용주에게보냄 (3) 같은키를가진두레코드사이에모순점이없으면이결과에대한메시지를출력 Copyright 2007 DBLAB, Seoul National University 6

7 순차탐색으로두리스트검증 함수 Verify1 두개의비정렬리스트를직접비교해서검증문제해결 복잡도 : O(mn) (n, m 은각각고용자, 피고용자리스트의레코드수 ) void Verify1(Element *l1, Element *l2, const int n, const int m) {// 길이가 n 과 m 인비정렬리스트 l1 과 l2 를비교한다. bool *marked = new bool[m+1]; fill(marked+1, marked+m+1, false); } for(i=1; i<=n; i++) { int j = SeqSearch(l2, m, l1[i]); if(j==0) cout << l1[i] << not in l2 << endl; // (1) 을만족 else { if(!compare(l1[i],l2[j]) // (3) 을만족 cout << Discrepancy in << l1[i] << endl; marked[j] = true; // l2[j] 를검사한것으로표시 } } for(i=1; i<=m; i++) if(!marked[i]) cout << i2[i] << not in l1. << endl; // (2) 를만족 delete [] marked; Copyright 2007 DBLAB, Seoul National University 7

8 두리스트의빠른검증 함수 Verify2 두리스트를먼저정렬시킨다음비교 복잡도 : O(t sort (n) + t sort (m) + n + m) t sort (n): n 개의레코드를가진리스트를정렬하는데걸리는시간 연산시간 : O(max(nlogn, mlogm)) n 개의레코드를 O(nlogn) 시간에정렬할수있으므로 void Verify2(Element *l1, Element *;2, const int n, const int m) {// Verify1과같은작업을수행한다. 여기서는 l1과 l2를먼저정렬한다. Sort(l1, n); Sort(l2, m); // 키를오름차순으로정렬 int i = 1, j=1; while((i<=n) && (j<=m)) if(l[i] < l[j]) { cout << l1[i] << not in l2 << endl; i++; } else if(l[i]>l[j]) { cout << l2[j] << not in l1 << endl; j++; } else { // 같은키들 if(!compare(l1[i],l2[j])) cout << Discrepancy in << l1[i] << endl; i++; j++; } if(i<=n) OutputRest(l1, i, n, 1); // l1의레코드 i부터 n까지출력 else if(j<=m) OutputRest(l2,j,m,2); // l2의레코드 j부터 m까지출력 } Copyright 2007 DBLAB, Seoul National University 8

9 정렬의필요성 정렬의두가지중요한사용법 (1) 탐색에서보조로사용 (2) 리스트의엔트리를비교하는방법으로사용 정렬방법 (1) 내부방법 (internal methods) 정렬할리스트가작아서전체적인정렬이메인메모리상에서실행될수있을때사용 (2) 외부방법 (external methods) 큰리스트에사용 Copyright 2007 DBLAB, Seoul National University 9

10 삽입정렬 (1) 새로운레코드를 i 개의정렬된레코드리스트에끼워넣어크기가 i+1 인정렬된결과레코드리스트를만든다. template <class T> void Insert(const T& e, T *a, int i) {// e 를정렬된리스트 a[1:i] 에삽입하여결과 // 리스트 a[1:i+1] 도정렬되게한다. // 배열 a 는적어도 i+2 원소를포함할공간을가지고있어야한다. a[0] = e; while(e <a[i]) { a[i+1] = a[i]; i--; } a[i+1] = e; } 정렬된리스트로삽입 Copyright 2007 DBLAB, Seoul National University 10

11 삽입정렬 (2) template <class T> void InsertionSort(T* a, const int n) {// a[1:n] 을비감소순으로정렬 for(int j = 2; j <= n; j++) { T temp = a[j]; Insert(temp, a, j-1); } } Insert(e, a, i) 는최악의경우삽입전 i+1 번비교해야함 Insert 의복잡도 : O(i) InsertionSort 의복잡도 삽입정렬 i = j-1 = 1,2,...,n-1 일때 Insert 를호출 n 1 i 1 복잡도 : O( ( i 1) ) = O(n 2 ) Copyright 2007 DBLAB, Seoul National University 11

15 퀵정렬 (1) 평균성능이가장좋은정렬방법 퀵정렬 (Quick Sort) 단계 (1) 정렬할레코드중피벗 (pivot: 중추 ) 레코드를선택 (2) 정렬할레코드들을다시정돈 피벗의왼쪽 : 피벗의키보다작거나같은레코드들을위치시킴 피벗의오른쪽 : 피벗의키보다크거나같은레코드들을위치시킴 (3) 퀵정렬을순환적으로사용 피벗의왼쪽과오른쪽의레코드들은서로독립적으로정렬된다 Copyright 2007 DBLAB, Seoul National University 15

16 퀵정렬 (2) 키 (26, 5, 37, 1, 61, 11, 59, 15, 48, 19) 를가진 10 개의레코드로된리스트를퀵정렬을사용하여정렬 R 1 R 2 R 3 R 4 R 5 R 6 R 7 R 8 R 9 R 10 left right [ ] 1 10 [ ] 26 [ ] 1 5 [ 1 5] 11 [19 15] 26 [ [19 15] 26 [ ] [ ] [48 37] 59 [61] [61] QuickSort 를호출할때마다의리스트상태대괄호는계속해서정렬할서브리스트를나타냄 Copyright 2007 DBLAB, Seoul National University 16

17 퀵정렬 (3) QuickSort 의분석 최악의경우복잡도 : O(n 2 ) 한레코드의위치가정확히정해질때마다그레코드의왼쪽과오른쪽의서브리스트크기가같을경우 크기가 n/2인두개의서브리스트를정렬하는작업과같다 크기가 n인리스트에서한레코드를위치시키는데필요한시간 : O(n) T(n) cn + 2T(n/2) 어떤상수 c에대해서 cn + 2(cn/2 + 2T(n/4)) 2cn + 4T(n/4)... cnlog 2 n + nt(1) = O(nlog 2 n) 평균연산시간 : O(nlogn) Copyright 2007 DBLAB, Seoul National University 17

18 퀵정렬 (4) 보조정리 7.1 T avg (n) 을함수 QuickSort 가 n 개의레코드를가진리스트를정렬하는데필요한예상시간이라하자그러면 n 2 에대해 T avg (n) knlog e n 을만족시키는상수 k 가존재한다. ( 증명 ) QuickSort(list, 1, n) 호출시, 피벗이 j 위치에놓이게됨 크기가각각 j-1, n-j인두개의서브리스트를정렬하는문제가됨 예상시간 : T avg (j-1) + T avg (n-j) j는 1에서부터 n까지의범위에서똑같은확률로임의의값을취하므로다음과같은식을얻을수있다. Copyright 2007 DBLAB, Seoul National University 18

19 퀵정렬 (5) ( 증명 ) 계속 어떤상수 b에대하여 T avg (0) b와 T avg (1) b 라고가정이제, n 2이고 k=2(b+c) 인경우, T avg (n) knlog e n임을증명 귀납기초 : n=2인경우 (7.1) 식에의해 Tavg(2) 2c+2b knloge2 귀납가정 : 1 n < m에대해 Tavg(n) knlogen라고가정 귀납단계 : 식 (7.1) 과귀납가정에의해 jlog e j 가 j 에대한증가함수이므로식 (7.2) 는다음과같이된다. Copyright 2007 DBLAB, Seoul National University 19

20 퀵정렬 (6) 퀵정렬과스택공간 퀵정렬은순환 (recursion) 을구현하기위해스택공간필요 리스트가균등하게나뉘는경우 최대순환깊이는 log n 이되어스택공간으로 O(log n) 필요 최악의경우 순환의각단계에서, 크기가 n-1 인왼쪽서브리스트와크기가 0 인오른쪽서브리스트로리스트가나뉘는경우 순환깊이는 n 이되어스택공간으로 O(n) 필요 보다작은크기의서브리스트를먼저정렬하여스택공간을점근적으로감소시킬수있다. Copyright 2007 DBLAB, Seoul National University 20

21 퀵정렬 (7) 세 - 값의 - 메디안을사용한퀵정렬 (Quick Sort using a median-of-three) 피벗으로현재서브리스트에있는첫번째, 중앙, 마지막키중에서메디안을사용 pivot = median{k left, K (left+right)/2, K right } Copyright 2007 DBLAB, Seoul National University 21

22 얼마나빠르게정렬할수있는가? (1) 키에대한비교와교환연산만이허용된다는제약하에가장좋은정렬시간은 O(nlogn) 이라는정리를증명 Yes K 1 K 2 [1,2,3] No [1,2,3] K 2 K 3 K 1 K 3 [2,1,3] Yes No Yes No [1,2,3] stop K 1 K 3 [1,3,2] [2,1,3] stop K 2 K 3 [2,3,1] Yes No Yes No [1,3,2] stop stop [3,1,2] [2,3,1] stop stop [3,2,1] 삽입정렬에대한결정트리 결정트리 (decision tree) : 각노드가하나의키비교연산을나타내고간선은비교결과를나타내는트리 Copyright 2007 DBLAB, Seoul National University 22

23 얼마나빠르게정렬할수있는가? (2) 정리 7.1: n개의서로다른원소들을정렬하는결정트리의높이는적어도 log 2 (n!)+1이된다. 증명 : n개의원소정렬시 n! 개의서로다른결과가가능 정렬을위한결정트리는최소 n! 개의리프노드를가져야함 결정트리의높이는적어도 log 2 (n!)+1 계 : 비교만으로정렬하는알고리즘은최악의경우 Ω(nlogn) 연산시간을가짐 증명 : n! 개의리프노드를갖는모든결정트리는길이가 c n log 2 n인경로가존재함을보여야함 (c는상수 ) 정리에의해결정트리에는길이가 log 2 n! 인경로가있음. n! = n(n-1)(n-2),, (3)(2)(1) (n/2) n/2 log 2 n! (n/2)log 2 (n/2) = Ω(nlogn) Copyright 2007 DBLAB, Seoul National University 23

24 합병정렬 (1) 합병 (Merging) 두개의정렬된리스트를하나의정렬된리스트로합병 template <class T> void Merge(T *initlist, T *mergedlist, const int l, const int m, const int n) { // initlist[1:m] 과 initlist[m+1:n] 는정렬된리스트. // 이들은정렬된리스트 mergedlist[1:n] 으로합병된다. for(int i1 = l, iresult = l, i2 = m+1; //i1, i2 와 iresult 는리스트위치 i1 <= m && i2 <= n; // 어떤입력리스트도소진되지않음 iresult++) if(initlist[i1] <= initlist[i2]) { mergedlist[iresult] = initlist[i1]]; i1++; } else{ mergedlist[iresult] = initlist[i2]; i2++; } // 첫번째리스트의나머지레코드 ( 있다면 ) 복사 copy(initlist + i1, initlist + m + 1, mergedlist + iresult); } // 두번째리스트의나머지레코드 ( 있다면 ) 복사 copy(initlist + i2.initlist + n _1, mergedlist + iresult); 합병시간 : O(n-l+1) n-l+1 : 합병될레코드수 Copyright 2007 DBLAB, Seoul National University 24

25 합병정렬 (2) 반복합병정렬 (Iterative Merge Sort) 입력리스트를길이가 1 인 n 개의정렬된서브리스트로간주 반복합병정렬단계 첫번째합병단계 : 리스트들을쌍으로합병하여크기가 2 인 n/2 개의리스트를얻는다. n 이홀수이면리스트하나는크기가 1 두번째합병단계 : n/2 개의리스트를다시쌍으로합병하여 n/4 개의리스트를얻는다. 합병단계는하나의서브리스트가남을때까지계속된다. 한번합병할때마다서브리스트의수는반으로줄어든다. Copyright 2007 DBLAB, Seoul National University 25

27 합병정렬 (4) 합병정렬은여러개의합병단계 (pass) 로구현된다. template <class T> void MergePass(T *initlist, T *resultlist, const int n, const int s) { // 길이가 s 인서브리스트의인접쌍들이 // initlist 에서부터 resultlist 로합병된다. n 은 initlist 에있는레코드수이다. for(int i = 1; // i 는합병되는리스트의첫번째리스트의첫번째위치 i <= n-2*s+1; // 길이가 s 인두서브리스트를위해원소들이충분한지? i+= 2*s) Merge(initList, resultlist, i, i+s-1, i+2*s-1); } // 2*s 보다작은나머지리스트를합병 if((i+s-1)<n) Merge(initList, resultlist, i, i+s-1, n); else copy(initlist+i, initlist+n+1, resultlist+i); 합병패스 Copyright 2007 DBLAB, Seoul National University 27

28 합병정렬 (5) template <class T> void MergeSort(T *a, const int n) { // a[1:n] 을비감소순으로정렬한다. T *templist = new T[n+1]; // l 은현재합병되고있는서브리스트의길이이다. for(int l=1; l<n; l*=2) { MergePass(a, templist, n, l); l *= 2; MergePass(tempList, a, n, l); // list 와 templist 의역할을교환 } delete [] templist; } MergeSort 분석 i번째패스 : 크기가 2 i-1 인리스트를합병 총 log 2n 단계가데이타에적용된다. 합병의각단계에걸리는시간 : O(n) 총연산시간 : O(nlogn) Copyright 2007 DBLAB, Seoul National University 28

31 합병정렬 (7) 순환적합병정렬의서브리스트분할 두개의서브리스트를만든다 left ~ ( left right) / 2, ( left right) / 2 +1~ right 정수배열 link[1:n] 을사용 함수 Merge 가사용될때일어나는레코드복사를제거하기위하여정수포인터를각레코드에연관시키기위함 list[i] - 정렬된서브리스트에서레코드 i 다음에있는레코드 이배열의사용으로레코드복사는링크변경으로대체되고정렬함수의실행시간은레코드크기 s 에독립적이됨 필요한추가공간 : O(n) 반복적합병정렬은 O(snlogn) 시간과 O(sn) 추가공간필요 최종체인이결정하는정렬순서로레코드들을물리적으로재정돈해야하는후처리필요 Copyright 2007 DBLAB, Seoul National University 31

32 합병정렬 (8) 순환합병정렬구현 template <class T> Int rmergesort(t* a, int* link, const int left, const int right) {// 정렬할리스트는 a[left:right]. 초기에 link[i] 는모든 i 에대해 0 이다. // rmergesort 는정렬된체인의첫번째원소의인덱스를반환한다. if(left >= right) return left; int mid = (left + right)/2; return ListMerge(a, link, rmergesort(a, link, left, mid), // 왼쪽반을정렬 rmergesort(a, link, mid+1, right)); // 오른쪽반을정렬 } rmergesort 의분석 합병정렬의순환버전 안정적 연산시간 : O(nlogn) 순환합병정렬 Copyright 2007 DBLAB, Seoul National University 32

34 히프정렬 (1) 합병정렬의문제점 정렬한레코드수에비례하여저장공간이추가로필요 히프정렬 (heap sort) 일정한양의저장공간만추가로필요 최악의경우연산시간과평균연산시간 : O(nlogn) O(n) 의추가저장공간을사용하는합병정렬보단약간느리지만 O(1) 의추가저장공간을사용하는합병정렬보다빠름 최대 - 히프구조사용 최대 - 히프와연관된삭제, 삽입함수 : O(nlogn) 정렬방법 Adjust 함수사용 최대히프를재조정 Copyright 2007 DBLAB, Seoul National University 34

35 히프정렬 (2) Adjust 함수 왼쪽및오른쪽서브트리가모두히프인이진트리에서시작하여이진트리전체가최대히프가되도록재조정 연산시간 : O(d) (d 는트리의깊이 ) template <class T> void Adjust (T *a, const int root, const int n) { // 루트 root 를가진이진트리를히프성질을만족하도록조정한다. } // root 의왼쪽과오른쪽서브트리는히프성질을이미만족한다. // 어떤노드도 n 보다큰인덱스를갖지않는다. T e= a[root]; //e 에대한적절한위치를탐색 for(int j=2*root; j<=n; j*=2) { } if(j<n &&.a[j] < a[j+1]) j++; // j 는부모의최대자식 if(e >= a[j]) break; // e 는 j 의부모로삽입 a[j/2]= a[j]; // j 번째레코드를트리위로이동 a[j/2]=e; 최대히프의조정 Copyright 2007 DBLAB, Seoul National University 35

36 히프정렬 (3) template <class T> void HeapSort(T *a, const int n) {// a[1:n] 을비감소순으로정렬한다. for(int i=n/2; i>=1; i--) // 히프로조정 Adjust(a,i,n); } for(i=n-1; i>=1;i--) // 정렬 { swap(a[1], a[i+1]); // 현히프의처음과마지막을교환 Adjust(a, 1, i); // 히프로조정 } 정렬과정 Adjust를반복적으로호출 최대히프구조를만든다. 히프의첫번째레코드와마지막레코드를교환한다. 최대키를가진레코드가정렬된배열의정확한위치에자리잡게됨 히프의크기를줄인후히프를재조정한다. 전체연산시간 : O(nlogn) Copyright 2007 DBLAB, Seoul National University 36

37 히프정렬 (4) 이진트리로변환된배열 입력리스트 : (26, 5, 77, 1, 61, 11, 59, 15, 48, 19) [1] 26 [1] 77 [2] 5 [3] 77 [2] 61 [3] 59 [4] 1 [5] [4] 48 [5] [6] [7] [6] [7] [8] [9] [10] [8] [9] [10] (a) 입력리스트를이진트리로변환한모습 (b) 초기히프형태로구성한것 (HeapSort 코드의첫번째 for 루프를 거친후의최대히프모습 ) Copyright 2007 DBLAB, Seoul National University 37

38 히프정렬 (5) [1] 61 [1] 59 [2] 48 [3] 59 [2] 48 [3] 26 [4] 15 [5] [4] 15 [5] [6] [7] [6] [7] 5 1 [8] [9] (a) 히프크기 =9 Sorted = [77] 5 [8] (b) 히프크기 =8 Sorted = [61,77] [1] 48 [1] 26 [2] 19 [3] 26 [2] 19 [3] 11 [4] 15 [5] [4] 15 [5] 5 1 (c) 히프크기 =7 [6] [7] (d) 히프크기 =6 [6] Sorted = [59,61,77] Sorted = [48,59,61,77] Copyright 2007 DBLAB, Seoul National University 38

39 히프정렬 (6) [1] 19 [1] 15 [2] 15 [3] 11 [2] 5 [3] [4] [5] (e) 히프크기 =5 Sorted = [26,48,59,61,77] 1 [4] (f) 히프크기 =5 Sorted = [19,26,48,59,61,77] [1] (g) 히프크기 =3 Sorted = [15,19,26,48,59,61,77] [2] [3] Copyright 2007 DBLAB, Seoul National University 39

40 여러키에의한정렬 (1) K 1,K 2,...,K t (K 1 은최대유효키, K t 는최소유효키 ) 의여러개의키를갖는레코드의정렬 모든레코드쌍 i, j 에대하여 t 1 i<j, ( Ki,..., Ki ) ( K j,..., K 키 K 1,...,K t 로정렬된것 1 t j ) 이성립하면레코드 R 1,...,R n 의리스트는 카드뭉치를정렬하는문제 두개의키 ( 무늬, 숫자 ) 에대한정렬문제 K 1 [ 무늬 ] : < < < K 2 [ 숫자 ] : 2<3<4<...<10<J<Q<K<A 정렬된카드뭉치 2,...,A,...,2,...,A Copyright 2007 DBLAB, Seoul National University 40

41 여러키에의한정렬 (2) MSD(most-significant-digit-first) 정렬 최대유효숫자우선정렬 먼저최대유효키 K 1 으로정렬 K 1 에대해같은값을가지는여러레코드파일 (pile) 들이만들어짐 각파일에대해독립적으로 K 2 로정렬 K 1,K 2 에대해같은값을가지는서브파일 (sub pile) 들이만들어짐 각서브파일에대해서는 K3 로정렬 최종적으로이렇게얻어진파일들을합친다. LSD(least-significant-digit-first) 정렬 최소유효숫자우선정렬 LSD 가 MSD 보다더단순 생성된파일과서브파일을독립적으로정렬할필요가없으므로 Copyright 2007 DBLAB, Seoul National University 41

42 여러키에의한정렬 (3) 기수 (radix) 정렬 어떤기수 r 을이용하여정렬키를몇개의숫자로분해 r = 10 : 키를십진수로분할 r = 2 : 키를이진수로분할 기수 -r 정렬에서는 r 개의빈 (bin) 이필요 (why?) 정렬되어야하는레코드가 R 1,...,R n 일때, 레코드의키는기수 -r 을이용하여분할 0~(r-1) 사이의 d 개의숫자를가진키가된다. 각빈의레코드는빈의첫레코드를가리키는포인터와마지막레코드를가리키는포인터를통해체인으로연결되며, 체인은큐처럼동작 Copyright 2007 DBLAB, Seoul National University 42

44 여러키에의한정렬 (5) 기수정렬의예 범위가 [0, 999] 인십진수를정렬 (d=3, r=10) a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] a[10] (a) 초기입력 e[0] e[1] e[2] e[3] e[4] e[5] e[6] e[7] e[8] e[9] f[0] f[1] f[2] f[3] f[4] f[5] f[6] f[7] f[8] f[9] (b) 첫번째 - 패스큐들 (First-pass queues) 과결과체인 Copyright 2007 DBLAB, Seoul National University 44

45 여러키에의한정렬 (6) e[0] e[1] e[2] e[3] e[4] e[5] e[6] e[7] e[8] e[9] f[0] f[1] f[2] f[3] f[4] f[5] f[6] f[7] f[8] f[9] (c) 두번째 - 패스큐들 (Second-pass queues) 과결과체인 Copyright 2007 DBLAB, Seoul National University 45

46 여러키에의한정렬 (7) e[0] e[1] e[2] e[3] e[4] e[5] e[6] e[7] e[8] e[9] f[0] f[1] f[2] f[3] f[4] f[5] f[6] f[7] f[8] f[9] (d) 세번째 - 패스큐들 (Third-pass queues) 과결과체인 Copyright 2007 DBLAB, Seoul National University 46

47 리스트정렬 (1) 많은레코드로된리스트를정렬할때는데이타의이동을최소화하도록해야함 합병정렬, 삽입정렬 순차리스트보다는연결리스트에동작하도록변경 추가적링크필요 물리적재배치대신링크필드만수정 반드시원하는정렬순서대로레코드를물리적으로재배치해야할경우 연결리스트정렬을먼저수행 리스트에명세된순서에따라레코드들을물리적으로재배치 재배치는추가공간을사용하여선형시간내에수행가능 Copyright 2007 DBLAB, Seoul National University 47

48 리스트정렬 (2) List 1 의분석 리스트에 n 개의레코드가있고, 각레코드가 m 워드로이루어져있을때 전체연산시간 : O(mn) 체인 first 를이중연결리스트로변환하는데 O(n) 시간 한번바꾸는데드는비용 ( 레코드의이동 ) : O(m) 최악의경우 : 3(n-1) 의레코드이동이일어남 R 1 <R 2 <...<R n, R 1 >R n 인경우 Copyright 2007 DBLAB, Seoul National University 48

49 리스트정렬 (3) 정렬된연결리스트의예 입력리스트 : (26, 5, 77, 1, 61, 11, 59, 15, 48, 19) i key linka R 1 R 2 R 3 R 4 R 5 R 6 R 7 R 8 R 9 R (a) 리스트정렬을한연결리스트, first=4 i key linka linkb R 1 R 2 R 3 R 4 R 5 R 6 R 7 R 8 R 9 R (b) 역방향링크를만든, (a) 에대응되는이중연결리스트, first=4 Copyright 2007 DBLAB, Seoul National University 49

50 리스트정렬 (4) List1 의예제 (1) i key linka linkb i key linka linkb R 1 R 2 R 3 R 4 R 5 R 6 R 7 R 8 R 9 R (a) List1 의 for 루프의첫번째반복후의구성, first=2 R 1 R 2 R 3 R 4 R 5 R 6 R 7 R 8 R 9 R (b) 두번째반복후의구성, first=6 Copyright 2007 DBLAB, Seoul National University 50

51 리스트정렬 (5) List1 의예제 (2) i key linka linkb R 1 R 2 R 3 R 4 R 5 R 6 R 7 R 8 R 9 R (c) 세번째반복후의구성, first=8 i key linka linkb R 1 R 2 R 3 R 4 R 5 R 6 R 7 R 8 R 9 R (d) 네번째반복후의구성, first=10 Copyright 2007 DBLAB, Seoul National University 51

52 리스트정렬 (6) 하나의링크필드만사용한레코드재배치 template <class T> void List2(T *a, int *link, const int n, int first) {// 두번째링크필드 linkb 가없는것만빼고 List1 과똑같다. for(int i=1; i<n; i++) {// i 번째위치에놓을정확한레코드를찾는다. 이레코드의인덱스는 i 이고, // 위치 1,2,...,i-1 인레코드는이미정확하게자리를잡고있다. while(first<i) first=link[first]; int q=link[first]; // a[q] 는정렬된순서에서다음레코드가된다. if(first!=i) {// a[first] 는 i 번째작은키이다. 레코드를 i 번째위치로이동한다. // 또한 a[i] 의새로운위치로링크를설정한다. swap(a[i], a[first]); link[first] = link[i]); link[i]=first; } first=q; } } M.D.MacLaren 이제시한방법으로 List1 을수정 링크필드를추가로필요로하지않음 first 가항상 i 보다크거나같아야함 Copyright 2007 DBLAB, Seoul National University 52

53 리스트정렬 (7) List2의예제 (1) 입력리스트 : (26, 5, 77, 1, 61, 11, 59, 15, 48, 19) 리스트정렬후그림 7.10(a) 와같은배치를얻음 i R 1 R 2 R 3 R 4 R 5 R 6 R 7 R 8 R 9 R 10 key link (a) List2 의 for 루프의첫번째반복후의구성, first=2 i R 1 R 2 R 3 R 4 R 5 R 6 R 7 R 8 R 9 R 10 key link (b) 두번째반복후의구성, first=6 i R 1 R 2 R 3 R 4 R 5 R 6 R 7 R 8 R 9 R 10 key link (c) 세번째반복후의구성, first=8 Copyright 2007 DBLAB, Seoul National University 53

54 리스트정렬 (8) List2 의예제 (2) i key link R 1 R 2 R 3 R 4 R 5 R 6 R 7 R 8 R 9 R List2 의분석 (d) 네번째반복후의구성, first=10 i R 1 R 2 R 3 R 4 R 5 R 6 R 7 R 8 R 9 R 10 key link (e) 다섯번째반복후의구성, first=1 레코드이동순서 : List1과동일 최악의경우 3(n-1) 의레코드이동 총비용 : O(nm) while 루프의전체연산시간 : O(n) List2 가 List1 보다공간과시간적인면에서우수 두레코드교환시 List1 이더많은일을해야함 Copyright 2007 DBLAB, Seoul National University 54

55 테이블정렬 (1) 리스트정렬기법은퀵정렬이나히프정렬에는적당하지않음 히프정렬에서는히프를순차적으로표현하는것이핵심 이러한정렬방법을위해 한레코드에대응하는한엔트리로구성된보조테이블 t를유지 테이블의엔트리는레코드의간접참조를할수있게함 테이블정렬 정렬시작시 : t[i]=i, 1 i n 정렬함수가 a[i] 와 a[j] 를교환해야한다면테이블의엔트리 t[i] 와 t[j] 만교환되게함 정렬끝나면 : a[t[1]] 은키가가장작은레코드 a[t[n]] 은키가가장큰레코드 정렬된레코드의순열 : a[t[1]], a[t[2]],...,a[t[n]] t 에나타난순열에따라레코드를물리적으로재배치해야될경우도있다. Copyright 2007 DBLAB, Seoul National University 55

56 테이블정렬 (2) 정렬전의보조테이블 t R 1 R 2 R 3 R 4 R 정렬이후의테이블 t 순열 t[0],t[1],...,t[n-1] 에대응하는레코드들을재배치하는함수 모든순열은분리된사이클로만들어짐 원소 i 에대한사이클 : i,t[i],t 2 [i],...,t k [i] (t j [i]=t[t j-1 [i]],t 0 [i]=1,t k [i]=i) 위의그림의순열 t는 R 1 과 R 5 를포함하는사이클과 R 4,R 3,R 2 를포함하는사이클을가짐 Copyright 2007 DBLAB, Seoul National University 56

57 테이블정렬 (3) template <class T> void Table(T *a, const int n, int *t) {// a[1:n] 을리스트 a[t[1]],...,a[t[n]], n 1 에대응되도록재배치한다. for(int i=1;i<n;i++) if(t[i]!=i) { // i 에서시작하는사이클이있다. T p=a[i]; int j=i; do { int k=t[j]; a[j]=a[k]; t[j]=j; j=k; } while(t[j]!=i); a[j]=p; //j 는레코드 p 를위한위치 t[j]=j; } } Table 함수 - 순열의사이클분해를이용 전체연산시간 : O(mn) Copyright 2007 DBLAB, Seoul National University 57

59 내부정렬요약 (1) 내부정렬비교 삽입정렬 : 리스트가부분적으로정렬되어있을때좋음 작은 n에대해가장좋은정렬방법 합병정렬 : 최악의경우에가장좋은방법히프정렬에비해더많은공간을필요로함 퀵정렬 : 평균성능이가장좋음 / 최악의경우 : O(n 2 ) 기수정렬 : 성능이키의크기와 r의선택에영향을받음 방법 최악의경우 평균적인경우 삽입정렬 n 2 n 2 히프정렬 nlogn nlogn 합병정렬 nlogn nlogn 퀵정렬 n 2 nlogn 정렬방법들의비교 Copyright 2007 DBLAB, Seoul National University 59

61 내부정렬요약 (3) 평균시간 ( 밀리초 ) 의그래프 퀵정렬이적절히큰 n에대해다른정렬방법보다성능이우수 50과 100 사이에삽입과퀵정렬이분리하는점 정확한분리점을 nbreak라할때 n<nbreak일때삽입정렬이가장좋은정렬방법 n>nbreak일때퀵정렬이가장좋은정렬방법 최악의경우 n>c에대해합병정렬이가장좋게보여짐 (c는어떤상수 ) n c 에대해서는삽입정렬이최악의경우가장좋다 Copyright 2007 DBLAB, Seoul National University 61

62 외부정렬 (1) 정렬하려는리스트전체가컴퓨터의메인메모리에모두올라갈수없다면내부정렬은사용할수없음 블록 (block) 한번에디스크로부터읽거나디스크에쓸수있는데이타의단위, 여러개의레코드들로구성됨 판독 / 기록시간에영향을미치는세가지요소 (1) 탐구시간 (Seek time) : 판독 / 기록헤드가디스크상의원하는실린더로이동하는데걸리는시간. 헤드가가로질러야하는실린더수에따라결정됨 (2) 회전지연시간 (Latency time) : 트랙의해당섹트가판독 / 기록헤드밑으로회전해올때까지걸리는시간 (3) 전송시간 (Transmission time) : 디스크로또는디스크로부터데이타블록을전송하는데걸리는시간 Copyright 2007 DBLAB, Seoul National University 62

63 외부정렬 (2) 합병정렬 외부저장장치에서정렬을할때, 가장널리알려진방법 : 합병정렬 (merge sort) 1 단계 2 단계 입력리스트의여러세그먼트들을좋은내부정렬방법으로정렬. 이정렬된세그먼트들을런 (run) 이라함. 런이생성되면외부저장장치에기록됨 1 단계에서만들어진런들을하나의런이될때까지합병트리형식을따라합병함 Copyright 2007 DBLAB, Seoul National University 63

64 외부정렬 (3) 최대 750 개의레코드만정렬할수있는내부메모리를가지고있는컴퓨터를이용하여 4500 개의레코드로된리스트를정렬 입력리스트는디스크에저장되어있고 250 레코드의블록길이를가지고있음 작업공간으로사용할또다른디스크를갖고있음 (1) 내부적으로한번에 3 개의블록 (750 개의레코드 ) 을 정렬해서여섯개의런 R1-R6 을만들고, 이런들을작업 디스크에수록 run 1 run 2 run 3 run 4 run 5 run 내부정렬후얻어진블록화된런 ( 한런당세블록 ) Copyright 2007 DBLAB, Seoul National University 64

65 외부정렬 (4) (2) 런들을합병 내부메모리에 250개의레코드를수용할수있는 3개의블록을마련 2개의블록은입력버퍼로쓰고하나는출력버퍼로씀 입력버퍼로각런으로부터블록하나씩읽어들임 런의블록들은입력버퍼에서출력버퍼로합병 출력버퍼가다차면디스크에기록됨 입력버퍼가공백이되면같은런에서다음블록을읽어들여다시채움 run 1 run 2 run 3 run 4 run 5 run 6 6 개런의합병 Copyright 2007 DBLAB, Seoul National University 65

66 외부정렬 (5) - 복잡도분석 표기법 t s = 최대탐구시간 t l = 최대회전지연시간 t rw = 250 개의레코드로구성된한블록을읽거나쓰는데걸리는시간 t IO = 한블록을입력또는출력하는데걸리는시간 = t s + t l + t rw t IS = 750 개의레코드를내부적으로정렬하는시간 nt m = 입력버퍼에서출력버퍼로 n 개의레코드를합병하는데걸리는시간 연산 시간 (1) 18 블록의입력판독 : 18t IO 36t IO +6t IS 내부정렬 : 6t IS 18 블록기록 : 18t IO (2) 1-6 런을쌍으로합병 36t IO +4500t m (3) 두개의 1500 레코드로된 24t IO +3000t m 런을합병 (12 블록 ) (4) 3000 레코드의런과 t IO +4500t m 레코드의런을합병 전체시간 디스크정렬예제에대한계산시간 132t IO t m + 6t IS Copyright 2007 DBLAB, Seoul National University 66

69 외부정렬 (8) 병렬연산을위한버퍼관리 k 개의런이 k- 원합병에의해한꺼번에합병되기위해 k개의입력버퍼와 1개의출력버퍼필요할것 입출력과내부합병을병렬로처리하기엔불충분 두개의출력버퍼가있으면해결됨 하나가출력되는동안다른하나에레코드들이합병됨 입력시간의지연은 2k 개의입력버퍼를사용하면해결됨 단순히한개의런에두개의버퍼를배당하는것은문제의해결방법이아님 Copyright 2007 DBLAB, Seoul National University 69

70 외부정렬 (9) 고정버퍼할당의불충분의예 (1) 2- 원합병을 4 개의입력버퍼 in[i](0 i<3), 2 개의출력버퍼 ou[0], ou[1] 을이용해서수행 각버퍼에는두개의레코드를담을수있음 ou[0] ou[1] ou[0] ou[1] ou[0] ou[1] in[0] in[1] in[0] in[1] in[0] in[1] in[2] in[3] in[2] in[3] in[2] in[3] (a) ou[0] 으로합병 (b) ou[0] 출력 (c) ou[1] 출력 in[2] 에입력 ou[1] 으로합병 ou[0] 으로합병 in[3] 에입력 in[0] 에입력 Copyright 2007 DBLAB, Seoul National University 70

71 외부정렬 (10) 고정버퍼할당의불충분의예 (2) ou[0] ou[1] ou[0] ou[1] ou[0] ou[1] in[0] in[1] in[0] in[1] in[0] in[1] in[2] in[3] in[2] in[3] in[2] in[3] (d) ou[0] 출력 ou[1] 으로합병 in[1] 에입력 (e) ou[1] 출력 ou[0] 으로합병 in[2] 에입력 (f) 런당두고정버퍼할당이연속적병렬연산에불충분함을보여주는예 버퍼들을필요에따라어떤런에도할당할수있도록해야함 Copyright 2007 DBLAB, Seoul National University 71

72 외부정렬 (11) 버퍼할당방법 각런의레코드를가지는입력버퍼가최소하나가늘존재 남아있는버퍼는우선순위에따라할당하여채워짐 k-원합병알고리즘에의해입력버퍼에있는레코드들이가장먼저소모되는런이다음버퍼로채워지는런임 가장작은키를가진런의버퍼가먼저소모됨 키가똑같을때는더작은인덱스의런을우선함 같은런으로부터입력되는모든버퍼레코드는큐로처리 컴퓨터병렬처리능력에대한가정 (1) 디스크드라이브는두개, 입출력채널은동시에각디스크에대해판독 / 기록가능 (2) I/O 장치와메모리블록사이에데이타전송중이면 CPU는동일한구역의메모리블록을참조못함 (3) 입출력버퍼는모두같은크기 Copyright 2007 DBLAB, Seoul National University 72

73 외부정렬 (12) 부동버퍼를이용한 k- 원합병 (1) /* 버퍼링알고리즘의단계 */ 단계 1: k 개의런각각으로부터첫번째블록을입력하여하나의데이타블록으로된 k 개의연결큐를설정한다. 나머지 k 개의입력블록들을자유입력블록들의연결스택에넣는다. ou 를 0 으로설정한다. 단계 2: lastkey[i] 를런 i 로부터마지막입력키라고하고, lastkey 가최소값인런을 nextrun 이라고하자. 만일 lastkey[nextrun] + 이면 nextrun 런으로부터다음블록을입력하기시작한다. 단계 3: 함수 Kwaymerge 를사용하여 k 개의입력큐로부터출력버퍼 ou 로레코드를합병한다. 출력버퍼가가득차거나키값이 + 인레코드가 ou 에나타날때까지합병을계속한다. 합병을수행하는동안, 출력버퍼가가득차기전이나 + 가 ou 에합병되기전에입력버퍼가비게되면, Kwaymerge 는같은큐의다음버퍼로진행하고빈버퍼는빈버퍼스택에반환한다. 그러나만약출력버퍼가가득차는것과동시에입력버퍼가비게되거나혹은 + 가 ou 에합병되는것과동시에입력버퍼가비게되면, 빈버퍼는큐에남게되고 Kwaymerge 는큐의다음버퍼로진행하지않는다. 대신에합병은중단된다. 단계 4: 디스크입출력이진행중이면완료되기를기다린다. 단계 5: 입력버퍼가읽혀졌으면해당런의큐에넣는다. lastkey[nextrun] 이최소로되는 nextrun 을결정하여다음에읽어야하는런을결정. 단계 6: lastkey[nextrun] + 이면 nextrun 런으로부터자유입력버퍼로읽기시작한다. 단계 7: 출력버퍼 ou 의쓰기를시작한다. ou 를 1-ou 로설정한다. 단계 8: 키값이 + 인레코드가출력버퍼로합병되지않았으면단계 3 으로간다. 그렇지않으면진행중인쓰기작업이완료되기를기다린후끝낸다. Copyright 2007 DBLAB, Seoul National University 73

74 외부정렬 (12) 부동버퍼를이용한 k- 원합병 (2) (1) k 가클경우, 먼저소모되는큐를결정하는데는 last[i](1 i<k) 에대해패자트리를만듦으로써 log 2 k 번의비교가가능 (2) k 가클경우, 함수 Kwaymerge 는패자트리를사용 (3) 처음 k 개블록의입력과마지막블록의출력을제외하고는모두 입출력이연산과동시에행해진다. (4) 알고리즘은모든블록의크기가같다고가정한다. 단계 6 에서다음블록을읽기시작할때는사용가능한버퍼가항상존재 단계 3 에서 k 원합병을할동안에큐에있는다음블록은그것이필요할때까지이미얽혀져있음 Copyright 2007 DBLAB, Seoul National University 74

76 외부정렬 (14) - 버퍼링 (Buffering) 의예 Line 앞의예에서입력버퍼큐의상태, 다음블록이읽혀지고있는런, 버퍼링알고리즘의 3 단계 ~8 단계까지루프의반복이시작될때마다출력되는출력버퍼의상태 Next Block Queue Run0 Run1 Line Run2 Output From no output Run Run Run Run Run Run 2 7 M Run 1 8 M Run 2 9 M M Run 1 10 M M M no next 11 M 70 M 11 M no next 12 M 12 M 70 M Copyright 2007 DBLAB, Seoul National University 76

77 외부정렬 (15) - 런의생성 패자트리 (a tree of losers) 를이용 한꺼번에내부메모리에저장할수있는레코드개수보다더긴런의생성이가능 Walters, Painter,Zalk 에의해고안된런생성알고리즘 평균적으로두배길이의런을생성 병렬적인입출력및내부처리도가능 패자트리를이용 < 사용되는변수와그의미 > r[i], 0 i<k... 토너먼트트리에있는 k 개의레코드 l[i], 1 i<k... 노드 i 에서일어난토너먼트의패자 l[0]... 토너먼트의승자 m[i], 0 i<k... r[i] 가속한런번호 rc... 현재런의런번호 q... 모든토너먼트의승자 rq... r[q] 의런번호 rmax... 생성될런의개수 lastrec... 출력되는마지막레코드의키값 MAXREC... 허용된최대키값을가진레코드 Copyright 2007 DBLAB, Seoul National University 77

79 외부정렬 (17) - 런의최적합병 (1) 여러런들이상이한크기를갖는경우 (ex) 길이가각각 2,4,5,15인네개의런 2 원합병기법을이용하여합병하는두가지방법 : 외부노드 : 내부노드 (a) 15 (b) (a) 의외부경로길이 : 43 (b) 의외부경로길이 : 52 (a) (b) 어떤레코드는한번만합병, 어떤레코드는최대 3 번까지합병 각레코드는정확히두번씩합병 완전합병패스를모든데이타에대해반복적으로수행하는전략 합병횟수는루트로부터해당외부노드까지의거리에의해결정됨 외부경로길이 (weighted external path length) 런길이와루트에서해당외부노드까지의거리를곱한결과를모두합산하여구함 - 최소가중외부경로길이를갖도록하는것이좋다 Copyright 2007 DBLAB, Seoul National University 79

80 외부정렬 (17) - 런의최적합병 (2) 메시지 M 1,..., M n+1 을위한최적의코드집합을구할때 코드 : 이진스트링, 해당메시지를전달하는데사용 받는쪽에서해독트리를이용하여코드를해독 해독트리 (decode tree) 이진트리, 외부노드는메시지를나타냄 코드단어의이진비트는해독트리의각단계에서필요로하는분기결정 (e.x 왼쪽분기 0, 오른쪽분기 1) M 1 M 2 M 3 코드단어를해독하는비용 코드의비트수에비례 비트수 : 루트노드에서부터해당외부노드까지의거리에해당 M i 가전송되는상대적빈도가 q i 일때예상해독시간 : M 4 1 Huffman 코드 M 1 : 000 M 2 : 001 M 3 : 01 M 4 : 1 d : 루트로부터메시지 M i 에대한외부노드까지의거리 코드단어를최소가중외부경로길이를가진해독트리가되도록선정하면최소화됨 Copyright 2007 DBLAB, Seoul National University 80 1 i n 1 q i d i

81 외부정렬 (18) 최소가중외부경로길이를가진이진트리찾기 D. Huffman 이제시 template <class T> void Huffman(MinHeap<Treenode<T>*>heap, int n) { // heap 는위에서설명한대로초기에 n 개의단일정점이진트리로구성된최소히프이다. for(int i = 0; i < n-1; i++) {// 두최소가중트리를결합 TreeNode<T> *first = heap.pop(); TreeNode<T> *second = heap.pop(); TreeNode<T> *bt = new BinaryTreeNode<T>(first, second, first.data+second.data); heap.push(bt); } } Huffman 의분석 주된루프는 n-1 번수행됨 Pop 과 Push 에대한호출 : O(log n) 점근적연산시간 : O(nlogn) Copyright 2007 DBLAB, Seoul National University 81

82 외부정렬 (19) - Huffman 트리구축의예 가중치 : q 1 =2, q 2 =3, q 3 =5, q 5 =7, q 6 =9, q 7 =13 이트리의가중외부경로길이 : 2*4 + 3*4 + 5*3 + 13*2 + 7*2 + 9*2 = 93 비교해보면, 최선의완전이진트리의가중치경로길이는 (a) 2 3 (c) 23 (b) (d) (e) Copyright 2007 DBLAB, Seoul National University 82

Microsoft PowerPoint - 알고리즘_5주차_1차시.pptx

Microsoft PowerPoint - 알고리즘_5주차_1차시.pptx Basic Idea of External Sorting run 1 run 2 run 3 run 4 run 5 run 6 750 records 750 records 750 records 750 records 750 records 750 records run 1 run 2 run 3 1500 records 1500 records 1500 records run 1