6. 합병 정렬 합병 정렬 (Merge Sorting) 각 단계별로 두 그룹의 정렬된 데이터를 서로 합쳐서 정렬된 더 큰 그룹으로 만들어 나아가는 정렬 Data Structure

6. 합병 정렬 합병 정렬 (Merge Sorting) 두 그룹을 합친 새로운 그룹을 위한 임시 저장공간이 필요함 각 그룹당 포인터 한 개씩 필요 각 포인터가 가리키는 데이터 두 개를 비교하여 더 작은 것에 대해 임시 저장공간에 복사 복사한 것에 대해서는 포인터를 다음으로 움직임 두 그룹 중 하나는 먼저 처리가 완료되어 포인터가 밖으로 나감 남은 그룹의 데이터를 순서대로 임시 저장공간으로 그대로 복사 위와 같은 작업이 끝나면 임시 저장공간에 있는 데이터를 원래의 배열에 다시 옮긴다. Data Structure

6. 합병 정렬 합병 정렬 (Merge Sorting) int Temp[MAX_TEMP_DATA_SIZE_FOR_MERGE]; void Merge_Sub (int A[ ], int F, int Mid, int L) { int First1 = F; int Last1 = Mid; int First2 = Mid + 1; int Last2 = L; int Index = First1; for (; (First1 <= Last1) && (First2 <= Last2); ++Index) { if (A[First1] < A[First2]) { Temp[Index] = A[First1]; ++First1; } else { Temp[Index] = A[First2]; ++First2; } for (; First1 <= Last1; ++First1, ++Index) for (; First2 <= Last2; ++First2, ++Index) for (Index = F; Index <= L; ++Index) A[Index] = Temp[Index]; 배열 A First1 Last1 First2 Last2 Data Structure

6. 합병 정렬 합병 정렬 (Merge Sorting) 재귀호출을 이용 원 데이터를 반 잘라서 왼쪽재귀 호출, 오른쪽 재귀 호출. 그 두 결과를 합병 베이스 케이스로부터 빠져 나와 호출 함수로 되돌아오는 과정에서 Merge(A, First, Middle, Last)를 수행. 즉, 합병에 의해 정렬 void MergeR(int A[ ], int First, int Last) { if (First < Last) { int Middle = (First + Last) / 2; MergeR(A, First, Middle); MergeR(A, Middle+1, Last); Merge_Sub(A, First, Middle, Last); //Merge 작업 – 실제 정렬이 수행됨 } void Merge(int A[ ], int N) { MergeR(A, 0, N-1); 배열 A First Middle Middle+1 Last N-1 Data Structure

6. 합병 정렬 합병 정렬 (Merge Sorting) Data Structure

6. 합병 정렬 합병 정렬 (Merge Sorting) 복잡도: 수학적 증명에 의하여 O(NlnN)로 밝혀짐 합병정렬은 안정정렬 합병과정에서 임시 저장공간에 데이터를 복사할 때, 원래 순서를 유지하면서 복사함 Data Structure

6. 합병 정렬 삽입 정렬 (Insertion Sorting) vs. 합병 정렬 (Merge Sorting) O(N2) vs. O(NlnN) 삽입 정렬 합병 정렬 Data Structure

7. 퀵 정렬 퀵 정렬 (Quick Sorting) 1960년 C.A.R. Hoare 에 의하여 개발된 알고리즘 재귀 호출의 순서에 유의 실제 정렬 작업이 어디서 일어나는지 유의 퀵 정렬은 실제 정렬작업이 재귀 함수의 처음에 Partition 작업에 의하여 수행된다. 합병 정렬 – Divide and Conquer 쾌속 정렬 – Conquer and Divide Data Structure

7. 퀵 정렬 퀵 정렬 (Quick Sorting) 0  1   2 3   4 5   6 p 10 7 2 8 3 1 9 6 퀵 정렬 (Quick Sorting) low high int Quick_Sub(int A[ ], int First, int Last) { int low, high, p; p = A[Last]; low = First; high = Last-1; while (low < high) { while (p > A[low]) low++; while (p < A[high]) high--; if (low < high) { int Temp = A[low]; A[low] = A[high]; A[high] = Temp; } A[low] = A[Last]; A[Last] = Temp; return low; •   p 10 7 2 8 3 1 9 6 •     p 10 7 2 8 3 1 9 6 •   p 1 7 2 8 3 10 9 6   • p 1 7 2 8 3 10 9 6   • p 1 3 2 8 7 10 9 6   • p 1 3 2 8 7 10 9 6   • p 1 3 2 8 7 10 9 6   p 1 3 2 6 7 10 9 8 Data Structure

7. 퀵 정렬 퀵 정렬 (Quick Sorting) Quick_Sub는 파티션 함수 피벗을 중심으로 그보다 작은 것은 왼쪽, 그보다 큰 것은 오른쪽으로 몰아넣음 피벗이 그 사이에 끼어 들어감 피벗의 위치를 돌려줌 이후 피벗의 왼쪽, 오른쪽 데이터가 각각 정렬되더라도 피벗의 위치는 불변, 즉 최종정렬까지 그 위치가 고정됨 void QuickR(int A[ ], int First, int Last) { if (First < Last) { int PivotIndex= Quick_Sub(A, First, Last); //Partition 작업 – 실제 정렬이 수행됨 QuickR(A, First, PivotIndex-1); QuickR(A, PivotIndex+1, Last); } void Quick(int A[ ], int N) { QuickR(A, 0, N-1); Data Structure

7. 퀵 정렬 퀵 정렬 (Quick Sorting) Data Structure

7. 퀵 정렬 퀵 정렬 (Quick Sorting) 복잡도: 수학적 증명에 의하여 O(NlnN)로 밝혀짐 일반 퀵 정렬 의 단점 피벗을 중심으로 데이터가 정확하게 반으로 갈린다는 보장이 없음 파티션의 결과 두 그룹이 균형(Balanced)이 잡히는 것은 퀵 정렬 성능에 중요한 영향을 미침 만약 균형이 잘 안 잡히면 단계의 수가 lnN 보다 많아짐 그래서, 거의 정렬이 되어진 데이터 집합에 대하여 퀵 정렬은 최악의 성능을 보임 완벽하게 정렬된 데이터 집합에 대하여 퀵정렬의 복잡도는 O(N2) Data Structure

7. 퀵 정렬 퀵 정렬 (Quick Sorting) 향상법 향상된 파티션 방법 (더 나은 균형을 위하여) Case I: Median-of-Three 파티션 임의로 세 개의 데이터 값을 골라서 그 중 중간 값에 해당하는 것을 키로 정함 Case II: Sample 정렬 데이터 배열에서 임의로 많은 샘플을 끄집어 내어 일단 정렬한 후, 그 중에 중간 값을 피벗으로 사용 Case III: Bentley-Mcllroy 방식 한 번에 세 개의 데이터 값을 고르고, 이를 세 번 반복하여 메디안 값에 해당하는 것인 세 개의 값 중의 메디안 값을 피벗으로 사용 작은 사이즈의 파티션 처리 방법 파티션 데이터가 열 개 미만이면 더 이상 파티션 하여 재귀호출 부르지 않고 바로 삽입 정렬들을 불러서 정렬을 끝냄 Data Structure

7. 퀵 정렬 합병 정렬 (Merge Sort) vs. 퀵 정렬 (Quick Sorting) 최악의 경우 비교 합병 정렬은 매 단계 마다 완벽한 균형 잡힌 분할을 함 합병 정렬은 최악의 경우에도 O(NlgN) 을 보장 퀵 정렬은 최악의 경우 O(N2) 추가 메모리 필요 여부 퀵 정렬은 임시 저장 공간이 불필요한 제자리 연산 (In-Place Computation) 합병 정렬은 임시 저장 공간에 옮겨가고 옮겨오는 시간이 필요 평균적 (일반적)으로는 퀵 정렬이 더 빠름 합병 정렬 퀵 정렬 Data Structure

7. 퀵 정렬 삽입 정렬 (Insertion Sort) vs. 퀵 정렬 (Quick Sorting) vs. 합병 정렬 (Merge Sort) Data Structure

8. 외부 정렬 외부 정렬 초기 수행 방법 한꺼번에 모든 데이터를 메모리에 올리지 못할 때 수행. Problem: sort 1Gb of data with 1Mb of RAM!!! 기본적으로 합병 정렬 방식이 사용됨 초기 수행 방법 메인 메모리의 크기가 Maximum 3 개의 Record만 수용할 수 있다고 가정 입력 파일(하드디스크) D A T A S T R U C T U R E A N D A L G O R I T H M 초기 단계 3개의 Record 단위로 메인 메모리로 읽어 들임 읽어 드린 3개의 Record를 메모리에서 정렬 다시 하드 디스크의 파일로 저장 이 때 여러 파일로 나누어서 저장 (*은 블록 나눔을 의미): 파일 1: ADT * RTU * GOR * 파일 2: AST * AEN * HIT * 파일 3: CRU * ADL * M * 파일 1: ADT * CRU * AEN * GOR * M 파일 2: AST * RTU * ADL * HIT * Data Structure

8. 외부 정렬 3-WAY Merge Example (3개 단위의 합병) 초기 단계 Procedure 파일 1: ADT * RTU * GOR * 파일 2: AST * AEN * HIT * 파일 3: CRU * ADL * M * Procedure 개념적 포인터 세 개를 각 파일의 첫 번째 Record에 위치시킴 포인터가 가리키는 세 개의 Record를 메모리로 올림 비교 결과 가장 작은 것을 파일 4에 저장하고 포인터를 움직임 해당 포인터에 있는 Record를 다시 읽어 들임 다시 세 개의 Record를 비교하여 가장 작은 것을 파일 4에 저장 결과적으로 파일 4에는 기존 파일 1,2,3의 첫 블록들이 정렬되어 기록 2단계 파일 4: AACDRSTTU * 파일 5: AADELNRTU * 파일 6: GHIMORT * 3단계 파일 1: AAAACDDEGHILMNORRSTTTTUU * 반복 Data Structure

8. 외부 정렬 2-WAY Merge Example (2개 단위의 합병) 초기 단계 Procedure 파일 1: ADT * CRU * AEN * GOR * M 파일 2: AST * RTU * ADL * HIT * Procedure 2단계 파일 3: AADSTT * AADELN * M 파일 4: CRRTUU * GHIORT * 3단계 파일 1: AACDRRSTTTUU * M 파일 2: AADEGHILNORT * 4단계 파일 3: AAAACDDEGHILNORRSTTTTUU * 파일 4: M 5단계 파일 1: AAAACDDEGHILMNORRSTTTTUU * Data Structure

8. 외부 정렬 효율 p개 단위의 합병 (p-way external merge sort) CPU 연산시간 << 입출력 시간 외부정렬의 효율은 입출력시간에 좌우됨 Dominant Factor: 입출력 시간 몇 단계에 걸쳐 파일 출력이 일어나는가가 관건 p개 단위의 합병 (p-way external merge sort) 초기 단계 실행결과 정렬된 블록의 개수는 N/M 개 N: 주어진 데이터 사이즈 (Ex. 1000MBytes = 1GBytes) M: 허용된 메모리 사이즈 (Ex. 100MBytes) 정렬의 효율은 대략 logp(N/M) Data Structure

9. 최선의 정렬 효율 결정트리 (Decision Tree) 3개의 키에 대해서 크기 순서의 조합은 3! = 6 Sorting algorithm’s behavior corresponds to some path on a Decision tree. 트리의 높이는 최소한 log2(N!) 보다 크고 최소 비교의 회수는 log2(N!). 스털링(Stirling)의 공식: log2(N!) ≥ log2(N/e)N = Nlog2N - Nlog2e. 즉, log2(N!)  O(Nlog2N). 따라서 임의의 정렬 알고리즘의 복잡도는 최소한 O(Nlog2N) Data Structure

10. 버킷 정렬과 셈 정렬 버킷 정렬 (Bucket Sorting) 방법 효율 단점 정렬의 대상으로 주어진 Record들의 Key Field 값을 전부 살펴본다. 가장 큰 Key Field 값과 같거나 큰 값을 최대 Index로 지니는 Bucket Array를 만든다. 다시 한번 주어진 Record들을 앞에서 부터 읽어 가며, 해당 Key Field값을 Array의 Index로 매칭하여 Bucket Array에 Record를 삽입한다. 효율 O(N). 키 비교에 의한 정렬이 아니므로 O(NlgN)을 능가할 수 있음 단점 버켓 배열의 크기는 최대 Key Field 값으로 설정. 메모리 공간낭비 가능성 이를 개선한 것이 셈 정렬 (계수 정렬) Data Structure

10. 버킷 정렬과 셈 정렬 버킷 정렬 (Bucket Sorting) 같은 배열 인덱스로 분류되는 Record의 처리 방법 Data Structure

10. 버킷 정렬과 셈 정렬 셈 정렬 (Counting Sorting or Distribution Sorting, 계수 정렬) Key Field의 값 자체의 크기와 무관하게 입력 레코드의 수와 같은 크기의 공간만으로 정렬 방법 키 빈도를 Count[ ] 배열에 넣음. Count[1]= 4, Count[2] = 2, Count[3] = 1 누계를 구하면 Count[1] = 4, Count[2] = 4 + 2 = 6, Count[3] = 6 + 1 = 7 다시 한번 오른쪽에서 왼쪽으로 스캔 해 가면서 버켓에 삽입 삽입 위치는 현재의 카운트 값. 삽입 직후에는 카운트 값을 하나씩 줄임 효율 O(N+N) = O(2N) = O(N) 특징 버킷 정렬과 셈 정렬 모두 안정정렬이며 Key Field 비교 없이 정렬 수행 단점: 메모리사용 큼, Bucket 생성 방법 및 데이터 분배 방법이 쉽지 않음 1 1 2 2 Data Structure

10. 버킷 정렬과 셈 정렬 셈 정렬 (Counting Sorting or Distribution Sorting, 계수 정렬) Data Structure

10. 버킷 정렬과 셈 정렬 셈 정렬 (Counting Sorting or Distribution Sorting, 계수 정렬) 셈 정렬에서 추가적으로 사용하는 메모리 사용량에 대한 분석 아래 TempC의 사이즈는 키필드 값에 대하여 Max – MIN + 1 이면 됨 int TempC[MAX_TEMP_DATA_SIZE_FOR_COUNT]; void Count(int A[ ], int N) { for (int i = 0 ; i < MAX_TEMP_DATA_SIZE_FOR_COUNT ; i++) TempC[i] = 0; for (int j = 0 ; j < N ; j++) TempC[A[j]-1]++; for (int k = 0 ; k < MAX_TEMP_DATA_SIZE_FOR_COUNT ; k++) { TempC[k+1] += TempC[k]; } if (TempC[0] != 0) { for (int t = TempC[0]-1 ; t >= 0 ; --t) A[t] = 1; for (int s = 1 ; s < MAX_TEMP_DATA_SIZE_FOR_COUNT ; s++) { if (TempC[s] == TempC[s-1]) continue; for (int t = TempC[s]-1 ; t >= TempC[s-1] ; --t) { A[t] = s+1; Data Structure

11. 기수 정렬 기수 정렬 (Radix Sort) – 문자열 정렬로 사용 Radix Basic Policy 뿌리(Root)에 그 어원을 가짐 키의 구성요소. 분해된 문자열, 분해된 문자 문자열 “KEY”의 뿌리는 각 문자 ‘K’, ‘E’, ‘Y’ 문자의 뿌리는 비트 (bit) Basic Policy 문자열 단위로 비교하는 대신 문자열을 잘라서 문자 단위로 비교 더 나아가서 문자 단위로 비교하는 대신 비트 단위로 비교도 가능 int strcmp ( const char * string1, const char * string2 ); [Parameters] string1: Null-terminated string to compare. string2: Null-terminated string to compare. [Results] Data Structure

11. 기수 정렬 LSD 기수 정렬 (Radix Sort) MSD 기수 정렬 (Radix Sort) 잘 사용 안됨 왼쪽 (MSD: Most Significant Digit) 에서 오른쪽으로 진행 셈 정렬(Distribution Counting)을 사용. O(WN) = O(N) W: 각 문자열의 길이 이전의 모든 문자가 일치하는 것들만 다음 문자를 비교 앞부분이 유일(Uniqueness) 해지면 더 이상 비교 대상에서 제외 a d 1 c b 2 f e 3 4 5 6 7   ⇧ a d 1 c e 2 b 3 4 5 6 7 f   ⇧ a c e 1 d 2 b 3 4 5 6 7 f   ⇧ a c e 1 d 2 b 3 4 5 6 7 f   Data Structure

11. 기수 정렬 기수교환 정렬 (Radix Exchange Sort) 문자 단위의 정렬에 셈 정렬 대신 퀵 정렬 사용 별도 메모리 대신 스와핑이 이용됨 3-way 파티션 피벗 b와 일치하지 않는 키(add, ace 그룹, dad, fee, cab 그룹)는 다시 첫 문자를 기본으로 재귀적으로 정렬해야 함. 피벗 b와 일치하는 키(bed, bad, bee)는 두 번째 문자를 대상으로 정렬을 진행 a d 1 c b 2 f e 3 4 5 6 7   ⇧ a d 1 c e 2 b 3 4 5 6 f 7   ⇧ Data Structure

11. 기수 정렬 비트 단위의 기수 교환 정렬 (Radix Exchange Sort) 파티션 결과 0인 그룹과 1인 그룹으로 양분 비트단위의 쾌속정렬 비트 열이 유일(Uniqueness)해지면 더 이상 비교대상에서 제외시킴 Data Structure

11. 기수 정렬 Comparison Sort Non-comparison Sort Quick sort Merge sort Shell sort Insertion sort Selection sort Bubble sort Heap sort Non-comparison Sort Bucket sort Counting sort Radix sort Data Structure