제 7 장 정렬.

Presentation on theme: "제 7 장 정렬."— Presentation transcript:

1 제 7 장 정렬

2 탐색 (1) 용어 정리 순차 탐색 (Sequential Search) 리스트 : 하나 이상의 필드로 된 레코드의 집합
키(Key) : 레코드를 구분하기 위해서 사용되는 필드 순차 탐색 (Sequential Search) 레코드 리스트를 왼편에서 오른편 또는 오른편에서 왼편으로 레코드를 검사하는 것

3 탐색 (2) n개의 레코드를 가진 리스트를 탐색하기 위해 O(n)의 시간이 걸린다. 성공적인 탐색을 위한 평균키 비교 횟수
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)의 시간이 걸린다. 성공적인 탐색을 위한 평균키 비교 횟수

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

5 탐색 (4) 보간법(interpolation)에 의한 탐색
리스트가 정렬되었을 때만 사용 가능 탐색의 성질은 리스트에 있는 키의 분포에 달려있음 리스트를 반복해서 탐색할 때 리스트를 정렬된 상태로 유지하는 것이 이롭다.

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

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;

8 두 리스트의 빠른 검증 함수 Verify2 두 리스트를 먼저 정렬시킨다음 비교
복잡도 : O(tsort(n) + tsort(m) + n + m) tsort(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까지 출력

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

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; 정렬된 리스트로 삽입

11 삽입 정렬 (2) Insert(e, a, i)는 최악의 경우 삽입 전 i+1번 비교해야 함 InsertionSort의 복잡도
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를 호출 복잡도 : O( ) = O(n2)

12 삽입 정렬 (3) 삽입 정렬의 최악의 예 입력 리스트가 역순이므로 새로운 레코드가 정렬된 부분에 삽입될 때마다 전체 정렬된 부분이 오른쪽으로 이동 j [1] [2] [3] [4] [5] _

13 삽입 정렬 (4) n = 5, 입력 키 순서가 2, 3, 4, 5, 1일 경우 j = 2, 3, 4에 대한 시간 : O(1)
j = 5에 대한 시간 : O(n) j [1] [2] [3] [4] [5] _

14 삽입 정렬 (5) 삽입 정렬의 변형 이원 삽입 정렬 연결 삽입 정렬
Insert(프로그램 7.4)에서 사용된 순차 탐색 기법 대신 이원 탐색을 사용 삽입 정렬에서 수행하는 비교 횟수를 줄인다 레코드 이동 횟수는 변하지 않음 연결 삽입 정렬 리스트의 원소들을 배열 대신 연결 리스트로 표현 링크 필드만 조정하면 되므로 레코드 이동 횟수가 0

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

16 퀵 정렬 (2) 키 (26, 5, 37, 1, 61, 11, 59, 15, 48, 19)를 가진 10개의 레코드로 된 리스트를 퀵 정렬을 사용하여 정렬 R1 R2 R3 R4 R5 R6 R7 R8 R9 R10 left right [26 5 37 1 61 11 59 15 48 19] 1 10 [11 5 19 1 15] 26 [59 61 48 37] 1 5 [ 1 5] 11 [19 15] 26 [59 61 48 37 1 2 1 5 11 [19 15] 26 [59 61 48 37] 4 5 1 5 11 15 19 26 [59 61 48 37] 7 10 1 5 11 15 19 26 [48 37] 59 [61] 7 8 1 5 11 15 19 26 37 48 59 [61] 10 10 1 5 11 15 19 26 37 48 59 61 QuickSort를 호출할 때마다의 리스트 상태 대괄호는 계속해서 정렬할 서브리스트를 나타냄

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

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

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

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

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

22 얼마나 빠르게 정렬할 수 있는가? (1) 키에 대한 비교와 교환 연산만이 허용된다는 제약 하에 가장 좋은 정렬 시간은 O(nlogn)이라는 정리를 증명 K1 ≤ K2 [1,2,3] Yes No [1,2,3] K2 ≤ K3 K1 ≤ K3 [2,1,3] Yes No Yes No [1,2,3] stop K1 ≤ K3 [1,3,2] [2,1,3] stop K2 ≤ K3 [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) : 각 노드가 하나의 키 비교 연산을 나타내고 간선은 비교 결과를 나타내는 트리

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

24 합병 정렬 (1) 합병(Merging) 두개의 정렬된 리스트를 하나의 정렬된 리스트로 합병 합병시간 : O(n-l+1)
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 : 합병될 레코드 수

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

26 합병 정렬 (3) 반복 합병 정렬의 예 입력 리스트 : (26, 5, 77, 1, 61, 11, 59, 15, 48, 19)
각 단계에서 합병되는 서브리스트를 합병 트리로 나타낸 것

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); } 합병 패스

28 합병 정렬 (5) MergeSort 분석 i번째 패스 : 크기가 2i-1인 리스트를 합병 총 단계가 데이타에 적용된다.
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번째 패스 : 크기가 2i-1인 리스트를 합병 총 단계가 데이타에 적용된다. 합병의 각 단계에 걸리는 시간 : O(n) 총 연산 시간 : O(nlogn)

29 합병 정렬 (6) 순환 합병 정렬 (Recursive Merge Sort) 정렬할 리스트를 거의 똑같이 두 개로 나눈다.
left 서브리스트와 right 서브리스트 서브리스트들은 순환적으로 정렬된다. 정렬된 서브리스트들은 합병된다.

30 합병 정렬 (7) 순환적 합병 정렬의 서브 리스트 분할
입력 리스트 : (26, 5, 77, 1, 61, 11, 59, 15, 49, 19) 26 5 77 1 61 11 59 15 48 19

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

32 합병 정렬 (8) 순환 합병 정렬 구현 rMergeSort의 분석 합병 정렬의 순환 버전 안정적 연산 시간 : O(nlogn)
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)

33 합병 정렬 (9) 합병 정렬의 변형 자연 합병 정렬 (Natural Merge Sort)
입력 리스트 내에 이미 존재하고 있는 순서를 고려 이미 정렬되어 있는 레코드의 서브리스트를 식별할 수 있도록 초기 패스를 만들어야 함 26 19 자연 합병 정렬

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

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; } 최대 히프의 조정

36 히프 정렬 (3) 정렬 과정 전체 연산 시간 : O(nlogn) Adjust를 반복적으로 호출  최대 히프 구조를 만든다.
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)

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

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

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

40 여러 키에 의한 정렬 (1) K1,K2,...,Kt(K1은 최대 유효 키, Kt는 최소 유효 키)의 여러 개의 키를 갖는 레코드의 정렬 모든 레코드 쌍 i, j에 대하여 i<j, 이 성립하면 레코드 R1,...,Rn의 리스트는 키 K1,...,Kt로 정렬된 것 카드 뭉치를 정렬하는 문제 두 개의 키 (무늬, 숫자)에 대한 정렬 문제 K1[무늬] : ♣ < ◆ < ♥ < ♠ K2[숫자] : 2<3<4<...<10<J<Q<K<A 정렬된 카드 뭉치  2♣,.....,A♣,......,2♠,...,A♠

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

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

43 여러 키에 의한 정렬 (4) RadixSort의 분석 : LSD 기수-r 방법을 표현 전체 연산 시간 : O(d(n+r))
d 패스를 처리하면서 각 패스의 연산 시간은 O(n+r)임 r의 선택을 달리하면 연산 시간이 달라진다.

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

45 여러 키에 의한 정렬 (6) e[0] e[1] e[2] e[3] e[4] e[5] e[6] e[7] e[8] e[9] 9
208 859 179 306 33 55 271 984 93 f[0] f[1] f[2] f[3] f[4] f[5] f[6] f[7] f[8] f[9] 306 208 9 33 55 859 271 179 984 93 (c) 두 번째-패스 큐들 (Second-pass queues) 과 결과 체인

46 여러 키에 의한 정렬 (7) e[0] e[1] e[2] e[3] e[4] e[5] e[6] e[7] e[8] e[9] 93
55 33 271 9 179 208 306 859 984 f[0] f[1] f[2] f[3] f[4] f[5] f[6] f[7] f[8] f[9] 9 33 55 93 179 208 271 306 859 984 (d) 세 번째-패스 큐들 (Third-pass queues) 과 결과 체인

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

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

49 리스트 정렬 (3) 정렬된 연결 리스트의 예 입력 리스트 : (26, 5, 77, 1, 61, 11, 59, 15, 48, 19) i R1 R2 R3 R4 R5 R6 R7 R8 R9 R10 key 26 5 77 1 61 11 59 15 48 19 linka 9 6 2 3 8 5 10 7 1 (a) 리스트 정렬을 한 연결 리스트, first=4 i R1 R2 R3 R4 R5 R6 R7 R8 R9 R10 key 26 5 77 1 61 11 59 15 48 19 linka 9 6 2 3 8 5 10 7 1 linkb 10 4 5 7 2 9 6 1 8 (b) 역방향 링크를 만든, (a)에 대응되는 이중 연결 리스트, first=4

50 리스트 정렬 (4) List1의 예제 (1) i R1 R2 R3 R4 R5 R6 R7 R8 R9 R10 key 1 5 77
26 61 11 59 15 48 19 linka 2 6 9 3 8 5 10 7 4 linkb 4 5 10 7 2 9 6 4 8 (a) List1의 for 루프의 첫 번째 반복 후의 구성, first=2 i R1 R2 R3 R4 R5 R6 R7 R8 R9 R10 key 1 5 77 26 61 11 59 15 48 19 linka 2 6 9 3 8 5 10 7 4 linkb 4 5 10 7 2 9 6 4 8 (b) 두 번째 반복 후의 구성, first=6

51 리스트 정렬 (5) List1의 예제 (2) i R1 R2 R3 R4 R5 R6 R7 R8 R9 R10 key 1 5 11
26 61 77 59 15 48 19 linka 2 6 8 9 3 5 10 7 4 linkb 4 2 10 7 5 9 6 4 8 (c) 세 번째 반복 후의 구성, first=8 i R1 R2 R3 R4 R5 R6 R7 R8 R9 R10 key 1 5 11 15 61 77 59 26 48 19 linka 2 6 8 10 3 5 9 7 4 linkb 4 2 6 7 5 9 10 4 8 (d) 네 번째 반복 후의 구성, first=10

52 리스트 정렬 (6) 하나의 링크 필드만 사용한 레코드 재배치 M.D.MacLaren이 제시한 방법으로 List1을 수정
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보다 크거나 같아야 함

53 리스트 정렬 (7) List2의 예제 (1) 입력 리스트 : (26, 5, 77, 1, 61, 11, 59, 15, 48, 19) 리스트 정렬 후 그림 7.10(a)와 같은 배치를 얻음 i R1 R2 R3 R4 R5 R6 R7 R8 R9 R10 key 1 5 77 26 61 11 59 15 48 19 link 4 6 9 3 8 5 10 7 1 (a) List2의 for 루프의 첫 번째 반복 후의 구성, first=2 i R1 R2 R3 R4 R5 R6 R7 R8 R9 R10 key 1 5 77 26 61 11 59 15 48 19 link 4 6 9 3 8 5 10 7 1 (b) 두 번째 반복 후의 구성, first=6 i R1 R2 R3 R4 R5 R6 R7 R8 R9 R10 key 1 5 11 26 61 77 59 15 48 19 link 4 6 6 9 3 5 10 7 1 (c) 세 번째 반복 후의 구성, first=8

54 리스트 정렬 (8) List2의 예제 (2) List2의 분석 List2가 List1보다 공간과 시간적인 면에서 우수 i R1
key 1 5 11 15 61 77 59 26 48 19 link 4 6 6 8 3 5 9 7 1 (d) 네 번째 반복 후의 구성, first=10 i R1 R2 R3 R4 R5 R6 R7 R8 R9 R10 key 1 5 11 15 19 77 59 26 48 61 link 4 6 6 8 10 5 9 7 3 (e) 다섯 번째 반복 후의 구성, first=1 List2의 분석 레코드 이동 순서 : List1과 동일 최악의 경우 3(n-1)의 레코드 이동 총 비용 : O(nm) while 루프의 전체 연산시간 : O(n) List2가 List1보다 공간과 시간적인 면에서 우수 두 레코드 교환 시 List1이 더 많은 일을 해야 함

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에 나타난 순열에 따라 레코드를 물리적으로 재배치해야 될 경우도 있다.

56 테이블 정렬 (2) 순열 t[0],t[1],...,t[n-1]에 대응하는 레코드들을 재배치 하는 함수
3 4 5 R1 50 9 11 8 R2 R3 R4 R5 정렬 이후의 테이블 t 순열 t[0],t[1],...,t[n-1]에 대응하는 레코드들을 재배치 하는 함수 모든 순열은 분리된 사이클로 만들어짐 원소 i에 대한 사이클 : i,t[i],t2[i],...,tk[i] (tj[i]=t[tj-1[i]],t0[i]=1,tk[i]=i) 위의 그림의 순열 t는 R1과 R5를 포함하는 사이클과 R4,R3,R2를 포함하는 사이클을 가짐

57 테이블 정렬 (3) Table 함수 - 순열의 사이클 분해를 이용 전체 연산 시간 : O(mn)
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)

58 테이블 정렬 (4) 테이블 정렬의 예 (a)의 테이블 t를 가지고 시작한다고 가정 R1 R2 R3 R4 R5 R6 R7 R8
key 35 14 12 42 26 50 31 18 t 3 2 8 5 7 1 4 6 (a) 초기 구성 key 12 14 18 42 26 35 31 50 t 1 2 3 5 7 6 4 8 (b) 첫 번째 사이클의 재배치 후 구성 key 12 14 18 26 31 35 42 50 t 1 2 3 4 5 6 7 8 (c) 두 번째 사이클의 재배치 후 구성

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

60 내부 정렬 요약 (2) 512MB RAM을 가진 1.7GHz Intel Pentium 4 PC와 Microsoft Visual Studio .NET 2003으로 얻은 결과 n 삽입 히프 합병 퀵 정렬 방법들에 대한 평균 시간

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

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

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

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

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

66 외부 정렬 (5) - 복잡도 분석 표기법 ts = 최대 탐구 시간 tl = 최대 회전지연 시간
trw = 250개의 레코드로 구성된 한 블록을 읽거나 쓰는데 걸리는 시간 tIO = 한 블록을 입력 또는 출력하는데 걸리는 시간 = ts + tl + trw tIS = 750개의 레코드를 내부적으로 정렬하는 시간 ntm = 입력 버퍼에서 출력 버퍼로 n개의 레코드를 합병하는데 걸리는 시간 연산 시간       (1) 18블록의 입력 판독: 18tIO      tIO+6tIS           내부 정렬: 6tIS                          18블록 기록: 18tIO                   (2) 1-6런을 쌍으로 합병            tIO+4500tm       (3) 두개의 1500 레코드로 된        tIO+3000tm           런을 합병 (12 블록)                   (4) 3000 레코드의 런과 1500        tIO+4500tm           레코드의 런을 합병                                                                    전체 시간         132tIO tm + 6tIS 디스크 정렬 예제에 대한 계산 시간

67 외부 정렬 (6) 2원 합병보다 높은 차수의 합병을 이용하면 런에 대해서 일어나는 합병 패스 수를 줄일 수 있음
입력, 출력, 합병을 병렬적으로 처리하기 위해서 적당한 버퍼-관리 방법이 필요

68 외부 정렬 (7) k-원 합병 m개의 런이 있을 때의 합병 트리 의 레벨을 가짐
총 패스 필요  고차 합병을 사용하여 줄일 수 있음 16개 런에 대한 4-원 합병 2-원인 경우에 데이타 패스가 4였지만 2로 줄어듬

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

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

71 외부 정렬 (10) 고정 버퍼 할당의 불충분의 예 (2) ∴ 버퍼들을 필요에 따라 어떤 런에도 할당할 수 있도록 해야 함 5
6 - - 7 8 9 - - ou[0] ou[1] ou[0] ou[1] ou[0] ou[1] 8 9 - - 9 20 25 - 20 25 in[0] in[1] in[0] in[1] in[0] in[1] - 7 - 15 - - 15 - - 15 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) 런 당 두 고정 버퍼 할당이 연속적 병렬 연산에 불충분함을 보여주는 예 ∴ 버퍼들을 필요에 따라 어떤 런에도 할당할 수 있도록 해야 함

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

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으로 간다.  그렇지 않으면 진행 중인 쓰기 작업이 완료되기를 기다린 후 끝낸다.

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

75 외부 정렬 (13) 세 개의 런으로 3-원 합병을 수행하는 예 각 런은 두 개의 레코드로 된 네 개의 블록으로 구성
모든 런에서 네 번째 블록의 마지막 레코드의 키 : +∞ 여섯 개의 입력 버퍼와 두 개의 출력 버퍼 Run 0 33 +∞ Run 1 70 +∞ Run 2 50 +∞ 세 개의 런

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

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 ... 허용된 최대 키 값을 가진 레코드

78 외부 정렬 (16) Runs의 분석 : 평균적으로 런의 크기는 거의 2k
O(nlogk) 패자 트리를 조정하는 데 걸리는 시간 : O(log k)

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

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

81 외부 정렬 (18) 최소 가중 외부 경로 길이를 가진 이진 트리 찾기 D. Huffman이 제시 Huffman의 분석
Pop과 Push에 대한 호출 : O(log n) ∴ 점근적 연산 시간 : O(nlogn) 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); }

82 외부 정렬 (19) - Huffman 트리 구축의 예
가중치 : q1=2, q2=3, q3=5, q5=7, q6=9, q7=13 이 트리의 가중 외부 경로 길이 : 2*4 + 3*4 + 5*3 + 13*2 + 7*2 + 9*2 = 93 비교해보면, 최선의 완전 이진 트리의 가중치 경로 길이는 95 5 10 16 2 3 5 5 9 7 (a) 2 3 (c) 23 (b) 39 10 13 16 23 5 5 9 7 10 13 2 3 5 5 (e) (d) 2 3