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

Presentation on theme: "6. 합병 정렬 합병 정렬 (Merge Sorting)"— Presentation transcript:

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

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

3 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

4 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

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

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

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

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

9 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

10 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

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

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

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

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

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

16 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

17 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

18 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

19 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

20 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

21 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

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

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

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

25 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

26 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

27 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

28 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

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

30 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