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

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

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

삽입 정렬 (2) insert(e, a, i)는 최악의 경우 삽입 전 i+1번 비교해야 함 insertionSort의 복잡도 void insertionSort(element a[], int n) {/* a[1:n]을 비감소 키 순서대로 정렬 */ int j; for(j = 2; j <= n; j++) { element 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)

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

삽입 정렬 (4) n = 5, 입력 키 순서가 2, 3, 4, 5, 1일 경우 j = 2, 3, 4에 대한 시간 : O(1) j = 5에 대한 시간 : O(n) insertionSort는 안정적 작은 n(예를 들어, n≤30)에 대해 가장 빠른 정렬 방법 j [1] [2] [3] [4] [5] _ 2 3 4 5 1 2 2 3 4 5 1 3 2 3 4 5 1 4 2 3 4 5 1 5 1 2 3 4 5

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

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

퀵 정렬 (2) 퀵 정렬 void quickSort(element a[], int left, int right) {/* a[left:right]를 비감소 키 순서대로 정렬한다. a[left].key는 피벗으로 임의로 선정한다. a[left].key≤ a[right+1].key라고 가정한다. */ int pivot, i, j; element temp; if(left < right) { i = left; j = right +1; pivot = a[left].key; do{ /* 서브리스트를 왼쪽에서 오른쪽으로 탐색하면서 left와 right 경계가 교차되거나 만날 때까지 out-of-order 원소들을 swap한다 */ do i++; while(a[i].key < pivot); do j--; while(a[j].keky > pivot); if(i < j) SWAP(a[i], a[j],temp); } while(i < j); SWAP(a[left], a[j],temp); quickSort(a, left, j-1); quickSort(a, j+1, right); } 퀵 정렬

퀵 정렬 (3) 키 (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를 호출할 때마다의 리스트 상태 대괄호는 계속해서 정렬할 서브리스트를 나타냄

퀵 정렬 (4) 평균 연산 시간 : 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)

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

합병 정렬 (1) 합병(Merging) 두개의 정렬된 리스트를 하나의 정렬된 리스트로 합병 합병시간 : O(n-l+1) void merge(element initList[], element mergedList[], int i, int m, int n) { /* initList[1:m]과 initList[m+1:n]는 정렬된 리스트. 이들은 정렬된 리스트 mergedList[i:n]으로 합병된다.*/ int j,k,t; j = m+1; k = i; while( i <= m && j <= n) { if (initList[i].key <= initList[j].key) mergeList[k++] = initList[i++]; else mergeList[k++] = initList[j++]; } if (i > m) /* mergedList[k:n] = initList[j:n]*/ for(t = j; t <= n; t++) mergeList[t] = initList[t]; /* mergedList[k:n] = initList[i:m] */ for(t = i; t <= m; t++) mergeListpk+t-i] = initList[t]; 합병시간 : O(n-l+1) n-l+1 : 합병될 레코드 수

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

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

합병 정렬 (4) 합병 정렬은 여러 개의 합병 단계(pass)로 구현된다. 합병 패스 void mergePass(element initList[], element resultList[], int n, int s) { /* 길이가 s인 서브리스트의 인접 쌍들이 // initList에서부터 resultList로 합병된다. n은 initList에 있는 레코드 수이다. for(i = 1; i <= n-2*s+1; i+= 2*s) merge(initList, mergedList, i, i+s-1, i+2*s-1); if((i+s-1)<n) merge(initList, mergedList, i, i+s-1, n); else for(j=i; j <= n; j++) mergedList[j] = initList[j]; } 합병 패스

합병 정렬 (5) mergeSort 분석 i번째 패스 : 크기가 2i-1인 리스트를 합병 총 단계가 데이타에 적용된다. void mergeSort(element a[], int n) { int s = 1; /* 현재 segment 크기 */ element extra[MAX_SIZE]; while (s<n) mergePass(a, extra, n, s); s *= 2; mergePass(extra , a, n , s); } mergeSort 분석 i번째 패스 : 크기가 2i-1인 리스트를 합병 총 단계가 데이타에 적용된다. 합병의 각 단계에 걸리는 시간 : O(n) 총 연산 시간 : O(nlogn)

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

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

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

합병 정렬 (8) 순환 합병 정렬 구현 rMergeSort의 분석 합병 정렬의 순환 버전 안정적 연산 시간 : O(nlogn) int rmergeSort(element a[], int link[], int left, 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)

합병 정렬 (9) int listMerge(element a[], int link[], int start1, int start2) { // start1과 start2에서 시작하는 정렬된 체인이 합병된다. // link[0]가 임시 헤더로 사용된다. 합병된 체인의 시작을 반환한다. int last1, last2, lastResult=0; // 결과 체인의 마지막 레코드 for(last1 =start1, last2 = start2; last1 && last2; ) if(a[last1] <= a[last2]) { link[lastResult] = last1; lastResult = last1; last1 = link[last1]; } else { link[lastResult] = last2; lastResult = last2; last2 = link[last2]; // 나머지 레코드들을 결과 체인에 첨가 if(last1 == 0) link[lastResult] = last2; else link[lastResult] = last1; return link[0]; 정렬된 체인의 합병

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

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

히프 정렬 (3) 정렬 과정 전체 연산 시간 : O(nlogn) adjust를 반복적으로 호출  최대 히프 구조를 만든다. void heapSort(element a[], int n) { int i, j; element temp; for(i=n/2; i>0; i--) adjust(a,i,n); for(i=n-1; i>0;i--) SWAP(a[1], a[i+1],temp); adjust(a, 1, i); } } 정렬 과정 adjust를 반복적으로 호출  최대 히프 구조를 만든다. 히프의 첫번째 레코드와 마지막 레코드를 교환한다. 최대 키를 가진 레코드가 정렬된 배열의 정확한 위치에 자리잡게 됨 히프의 크기를 줄인 후 히프를 재조정한다. 전체 연산 시간 : O(nlogn)

(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 루프를 거친 후의 최대 히프 모습)

히프 정렬 (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]

히프 정렬 (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]

여러 키에 의한 정렬 (3) LSD(least-significant-digit-first) 정렬 LSD가 MSD보다 더 단순 최소 유효 숫자 우선 정렬 카드 숫자 값(키 K2)에 따라 13개의 파일을 만듦 3들을 2들 위에, king들을 queen들 위에, ace들을 king들 위에 올려놓음 카드 뭉치를 거꾸로 놓고 안정된 정렬 방법을 이용하여 무늬(K1)에 따라 4개의 파일로 만듦 4개의 파일들은 각각 키 K2에 따라 정렬되게 함 4개의 파일을 합침 LSD가 MSD보다 더 단순 생성된 파일과 서브 파일을 독립적으로 정렬할 필요가 없으므로 오버헤드가 적게 든다.

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

여러 키에 의한 정렬 (5) int radixSort(element a[], int link[], int d, int r, int n) { int front[r], rear[r]; int i, bin, current, first, last; first = 1; for(i = 1; i < n; i++) link[i] = i+1; link[n] = 0; for(i=d-1; i >=0; i--) for(bin = 0; bin < r; bin++) front[bin] = 0; for(current = first; current; current = link[current]) bin = digit[a[current], i, r); if(front[bin] == 0) front[bin] = current; else link[rear[bin]] = current; rear[bin] = current; } for(bin++; bin < r; bin++) if(front[bin]) {link[last] = front[bin]; last = rear[bin]; } link[last] = 0; return first; }  LSD 기수 정렬

여러 키에 의한 정렬 (6) radixSort의 분석 : 전체 연산 시간 : O(d(n+r)) d 패스를 처리하면서 각 패스의 연산 시간은 O(n+r)임 d 값은 기수 r의 선택과 가장 큰 키에 의해 정해짐 r의 선택을 달리하면 연산 시간이 달라진다.

여러 키에 의한 정렬 (7) 기수 정렬의 예 범위가 [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) 과 결과 체인

여러 키에 의한 정렬 (8) 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) 과 결과 체인

여러 키에 의한 정렬 (9) 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) 과 결과 체인