Internet Computing Laboratory @ KUT Youn-Hee Han 9장. 정렬 알고리즘 Internet Computing Laboratory @ KUT Youn-Hee Han

1. 정렬의 분류 분류 1 - 오름차순 정렬 vs. 내림차순 정렬 분류 2 - 내부 정렬 vs. 외부 정렬 내부 정렬 – 정렬한 레코드 모두를 한꺼번에 메인 메모리 내부에 올려 놓고 정렬하는 방법 외부 정렬 – 정렬할 레코드들은 외부 기억장치 (예, 하드디스크)에 존재하는 상태에서 메인 메모리가 정렬할 수 있는 양만큼씩만 가져다가 정렬하고 그 결과를 다시 외부 기억장치에 저장하는 방법 Swapping Data Structure

1. 정렬의 분류 분류 3 - 안정 정렬 (Stable Sorting) vs. 불안정 정렬 (Unstable Sorting) 1차키 (Primary Key): 학점 2차키 (Secondary Key): 학년 안정 정렬의 특징 1차키로 정렬을 하더라도, 1차키가 같은 레코드들에 대해서는 이전에 이미 정렬 되어 있는 2차키 기준의 정렬 순서가 유지됨 불안정 정렬 안정 정렬 Data Structure

1. 정렬의 분류 분류 4 - 직접 정렬 (Direct Sorting) vs. 간접 정렬 (Indirect Sorting) 원 데이터 (Original Data) 직접 정렬 간접 정렬 원 데이터에서 인덱스 데이터 구성 정렬과정에서 원 데이터의 두 레코드 값을 비교하되 그 두 레코드가 Swap의 필요성이 있다면 그 값을 직접 바꾸는 대신에 인덱스 데이터를 바꾼다. 간접 정렬은 레코드의 사이즈가 클 때 효율이 높다. 포인터 정렬(Pointer Sorting)이라고도 함 Data Structure

2. 선택 정렬 선택 정렬 (Selection Sorting) 원 데이터 중에서 가장 큰 것을 선택하여 뒤의 알맞은 위치로 보내는 방식 (뒤쪽의 데이터와 교체) One Phase 가장 큰 것을 선택하여 뒤로 보냄 Phase 가 하나씩 완료되면 뒤쪽의 이미 정렬이 완료된 그룹이 왼쪽으로 늘어난다. 최종적으로 왼쪽에 정렬이 안된 레코드가 하나 남으면 정렬 완료 Data Structure

2. 선택 정렬 선택 정렬 (Selection Sorting) void Selection (int A[ ], int N) { 위와 같은 분석에서 Dominant Factor는 (1)이므로 (1)의 횟수만 고려해도 충분하다. void Selection (int A[ ], int N) { for (int Last = N-1; Last >= 1; --Last) { int Largest = 0; for (int Current=1; Current<=Last; Current++) { if (A[Current] > A[Largest]) Largest = Current; } int Temp = A[Last]; A[Last] = A[Largest]; A[Largest] = Temp; (1) (2) Data Structure

2. 선택 정렬 선택 정렬 (Selection Sorting) 의 특성 비교 횟수의 복잡도는 O(N2) 이지만 스왕핑 작업에 대한 복잡도는 O(N) 그러므로, 직접 정렬(Direct Sorting)을 행해야 하는 상황에서 용량이 큰 레코드들에 대하여 선택 정렬은 효율이 좋다고 말할 수 있음 이중 선택 정렬 (Duplex Selection Sort) 한번의 스캔에 대하여 최대치와 최소치를 동시에 발견하고 각각을 맨 왼쪽과 맨 오른쪽의 레코드와 스와핑 Min-Max Sorting Phase 의 수가 절반으로 감소 하지만, 각 Phase당 비교를 두 번씩 해야 하므로 복잡도 면에서는 변화 없음 Dominant Factor의 횟수 (N-2) + (N-4) + … + 2 = 등차수열의 합 공식 Data Structure

3. 버블 정렬 버블 정렬 (Bubble Sorting) 가장 큰 레코드가 한칸씩 오른쪽 끝으로 밀려가는 정렬 한 쌍 (버블)씩 비교하되 이전 쌍의 둘째 레코드가 다음 쌍의 첫 레코드가 되게 중복시킴 Data Structure

3. 버블 정렬 버블 정렬 (Bubble Sorting) 3번의 비교 단계수 데이터 N개 라면 버블정렬의 단계수는 대략 N 하지만, 중간 단계 에서 버블 정렬이 끝날 수도 있음 어떤 단계에서 스와핑이 한 번도 일어나지 않았 다면 정렬 완료 된 것임. 두번의 for문에 의한 비교 구문 수행 횟수: (N-1) + (N-2) + … 1 = 3 * N(N-1)/2 비교구문 안쪽의 할당문 수행 횟수 (최악일 때): 4 * N(N-1)/2 복잡도: 3 * N(N-1)/2 + 4 * N(N-1)/2 = O(N2) void Bubble (int A[ ], int N) { bool Sorted = false; for (int Pass = 1; (Pass < N) && (!Sorted); ++Pass) { Sorted = true; for (int Current=0; Current < N-Pass; ++Current) { if (A[Current] > A[Current+1]) { int Temp = A[Current]; A[Current] = A[Current+1]; A[Current+1] = Temp; Sorted = false; } Data Structure

3. 버블 정렬 버블 정렬 (Bubble Sorting) vs. 선택 정렬 (Selection Sorting) 단계별 Swapping에 대한 비교 단계별로 가장 큰 것이 가장 오른쪽으로 이동한다는 점에서 동일 선택정렬은 한 단계당 가장 큰 것과 가장 오른쪽 것이 한 번 스와핑. 버블정렬은 한 단계당 가장 큰 것이 한 칸씩 오른쪽으로 이동하여 스와핑 그러므로, 버블 정렬이 교환 및 복사에 걸리는 시간이 많이 걸림 특히, 큰 레코드에 대해서 직접 정렬 (Direct Sorting)을 할 시에 버블정렬은 선택정렬보다 매우 불리 Data Structure

3. 버블 정렬 버블 정렬 (Bubble Sorting) vs. 선택 정렬 (Selection Sorting) 이미 정렬이된 데이터에 대한 처리 방법 비교 버블정렬은 효율이 높다 1단계에서 끝남. (스와핑이 전혀없음) 복잡도: O(N) 선택정렬은 여전히 O(N2)의 복잡도를 보임 가장 큰 데이터인 마지막 데이터가 자기자신과 스왑 (Self Swap) Self Swap을 생략할 지라도 비교 구문이 Dominant Factor 로서 O(N2)의 복잡도를 가짐 Data Structure

4. 삽입 정렬 삽입 정렬 (Insertion Sorting) 보통 화투나 카드패를 정렬할 때 하는 방법 실수로 노트를 떨어트렸을 때 뒤섞인 페이지를 정렬하는 방법 정렬 방법 왼쪽 정렬된 그룹을 점차 키워간다 1 단계 가장 왼쪽 첫 레코드 하나만 주목. 그 자체로 정렬 2 단계: 다음 레코드를 왼쪽 것과 비교. 37은 22보다 크므로 그대로 둠. 3 단계: 15는 22의 왼쪽으로 가야 한다. 풀 스왑 (Full Swap): 삽입할 레코드가 계속적으로 왼쪽으로 옮겨짐 하프 스왑 (Half Swap): 삽입될 레코드는 단 한번만 움직임. 4 단계 19는 15와 22의 사이로 가야 한다. 5 단계 12는 15의 왼쪽으로 가야한다. Data Structure

4. 삽입 정렬 삽입 정렬 (Insertion Sorting) 효율 이미 정렬이 되어진 데이터에 대해서는 효율이 좋다. 안쪽 루프 명령문은 1 + 2 + ... + (N-1) = (N-1)N/2 번 실행 for 문 자체에 비교 2번, 할당 1번, for 문 내부에 할당이 1번 총 4(N-1)N/2 = 2(N-1)N = O(N2) 이미 정렬이 되어진 데이터에 대해서는 효율이 좋다. 복잡도: O(N) void Insertion(int A[ ], int N) { for (int Pick=1; Pick<N; ++Pick) { int Current = Pick; int Temp = A[Pick]; for ( ; (Current > 0) && (A[Current-1]>Temp) ; --Current) A[Current] = A[Current-1]; A[Current] = Temp; } Data Structure

4. 삽입 정렬 삽입 정렬 (Insertion Sorting) vs. 버블 정렬 (Bubble Sorting) vs. 선택 정렬 (Selection Sorting) 효율 비교 모든 정렬의 복잡도가 O(N2) 효율이 높은 편이 아님 실제 프로그램에서 활용이 잘 안됨 정렬하려는 데이터가 작은 경우는 알고리즘이 간단해서 사용이 되는 경우도 있음 안정 정렬 (Stable Sorting) 비교 버블 정렬과 삽입 정렬은 안정 정렬 레코드들이 하나하나 순차적으로 이동(Shift)하기 때문에 원래의 순서가 유지 선택 정렬은 불안정 정렬 스왑(Swap)에 의해 단번에 멀리 떨어진 곳으로 이동 Data Structure

5. 셀 정렬 셀 정렬 (Shell Sorting) 삽입정렬의 비효율적인 면을 개선 n-정렬 삽입 정렬에서는 키 값이 작은 레코드가 왼쪽으로 올 때 그보다 큰 데이터는 모두 한 칸씩 오른쪽으로 이동해야 함 셀 정렬: 한 칸씩 이동하는 대신 한 번에 여러 칸 이동을 시도하는 것 n-정렬 n: 간격 – Step, Hop을 의미 전체적으로 정렬하는 것이 아니라 n칸 단위로 정렬하는 것 4-정렬의 예 2, 16, 32, … 1, 5, 6, … 21, 22, 27, … 4, 8, … Data Structure

5. 셀 정렬 셀 정렬 (Shell Sorting) 방법 1-정렬 이전에 미리 큰 단위의 n-정렬을 수행하는 이유 마지막에는 반드시 1-정렬(일반적인 삽입 정렬)을 수행 1-정렬 이전에 미리 큰 단위의 n-정렬을 수행하는 이유 4-정렬을 통하여 가장 오른쪽에 존재하는 3이 맨 왼쪽으로 이동하는 데 있어서 중간에 있는 데이터들의 많은 이동이 필요하지 않다. Data Structure

5. 셀 정렬 셀 정렬 (Shell Sorting) Shell은 껍질 혹은 틀을 의미 셀 정렬은 큰 틀을 먼저 잡아가면서 전체적인 정렬을 한다는 의미 대략적인 정렬을 먼저 하고 점차 세부적으로 정렬해 들어가는 방법 전체적으로 레코드의 이동(Shifting)이 일어나는 확률이 줄어든다. Another Example Data Structure

5. 셀 정렬 셀 정렬 (Shell Sorting) void Shell(int A[ ], int N) { int step = 4; while (step > 0) { for (int i = 0 ; i < step ; i++) { int j = 1; int Pick= j * step + i; for (; Pick < N ; ++j, Pick= j * step + i) { int Current = Pick; int Temp = A[Pick]; for ( ; (Current > i) && (A[Current - step] > Temp) ; Current -=step) A[Current] = A[Current - step]; A[Current] = Temp; } if (step/2 != 0) step = step/2; else if (step == 1) step = 0; else step = 1; 복잡도: 수학적 증명에 의하여 O(N3/2)로 밝혀짐 삽입정렬은 안정정렬인 반면에 셀 정렬은 불안정 정렬 step i j pick 4 0 1 4 4 0 2 8 4 0 3 12 … 4 1 1 5 4 1 2 9 4 1 3 13 … … 2 0 1 2 Robert Sedgewick, Analysis of Shellsort and Related Algorithms, the proceedings of Fourth Annual European Symposium on Algorithms, Barcelona, September, 1996 Data Structure