CHAP 9:정렬 C로 쉽게 풀어쓴 자료구조 Slide 1 (of 44)

정렬이란? 정렬은 물건을 크기 순으로 오름차순이나 내림차순으로 나열하는 것 정렬은 컴퓨터공학을 포함한 모든 과학기술분야에서 가장 기본적이고 중요한 알고리즘중의 하나 정렬은 자료 탐색에 있어서 필수적이다. (예) 만약 사전에서 단어들이 정렬이 안되어 있다면? Slide 2 (of 44)

정렬의 대상 일반적으로 정렬시켜야 될 대상은 레코드(record) 레코드는 다시 필드(field)라는 보다 작은 단위로 구성 학생들의 레코드 이름 학번 주소 연락처 필드 필드 필드 필드 레코드 키(key) Slide 3 (of 44)

정렬 알고리즘의 개요 비교횟수 이동횟수 많은 정렬 알고리즘 존재 모든 경우에 최적인 알고리즘은 없음 응용에 맞추어 선택 단순하지만 비효율적인 방법 -- 삽입정렬, 선택정렬, 버블정렬 등 복잡하지만 효율적인 방법 -- 퀵정렬, 히프정렬, 합병정렬, 기수정렬 등 모든 경우에 최적인 알고리즘은 없음 응용에 맞추어 선택 정렬 알고리즘의 평가 비교횟수 이동횟수 Slide 4 (of 44)

정렬 알고리즘의 개요 (계속) 정렬 알고리즘의 안정성(stability) 동일한 키 값을 갖는 레코드들의 상대적인 위치가 정렬 후에도 바뀌지 않음 안정하지 않은 정렬의 예 =====> Slide 5 (of 44)

선택정렬(selection sort) 정렬된 왼쪽 리스트와 정렬안된 오른쪽 리스트 가정 초기에는 왼쪽 리스트는 비어 있고, 정렬할 숫자들은 모두 오른쪽 리스트에 존재 오른쪽 리스트에서 최소값 선택하여 오른쪽 리스트의 첫번째 수와 교환 왼쪽 리스트 크기 1 증가 오른쪽 리스트 크기 1 감소 오른쪽 리스트가 소진되면 정렬 완료 Slide 6 (of 44)

선택정렬 유사코드 선택정렬 함수 selection_sort(A, n) for i←0 to n-2 do least ← A[i], A[i+1],..., A[n-1] 중에서 가장 작은 값의 인덱스; A[i]와 A[least]의 교환; i++; 선택정렬 함수 #define SWAP(x, y, t) ( (t)=(x), (x)=(y), (y)=(t) ) void selection_sort(int list[], int n) { int i, j, least, temp; for(i=0; i<n-1; i++) { least = i; for(j=i+1; j<n; j++) // 최소값 탐색 if(list[j]<list[least]) least = j; SWAP(list[i], list[least], temp); } Slide 7 (of 44)

선택정렬 프로그램 #include <stdio.h> #include <stdlib.h> #define MAX_SIZE 10000 #define SWAP(x, y, t) ( (t)=(x), (x)=(y), (y)=(t) ) int list[MAX_SIZE]; int n; // void selection_sort(int list[], int n) { //... } void main() int i; n = MAX_SIZE; for(i=0; i<n; i++) // 난수 생성 및 출력 list[i] = rand()%n; // 난수 발생 범위 0~n selection_sort(list, n); // 선택 정렬 호출 for(i=0; i<n; i++) // 정렬 결과 출력 printf("%d\n", list[i]); Slide 8 (of 44)

선택정렬 복잡도 분석 비교 횟수 이동 횟수 전체 시간적복잡도: O(n2) 안정성을 만족하지 않음 (n - 1) + (n - 2) + … + 1 = n(n - 1)/2 = O(n2) 이동 횟수 3(n - 1) 전체 시간적복잡도: O(n2) 안정성을 만족하지 않음 Slide 9 (of 44)

삽입정렬(insertion sort) 삽입정렬은 정렬되어 있는 부분에 새로운 레코드를 올바른 위치에 삽입하는 과정을 반복 삽입정렬의 과정 Slide 10 (of 44)

삽입정렬 알고리즘 insertion_sort(A, n) 1. for i ← 1 to n-1 do 2. key ← A[i]; 3. j ← i-1; 4. while j≥0 and A[j]>key do 5. A[j+1] ← A[j]; 6. j ← j-1; 7. A[j+1] ← key 1. 인덱스 1부터 시작 2. 현재 삽입될 숫자인 i번째 정수를 key 변수로 복사 3. 현재 정렬된 배열은 i-1까지 이므로, i-1번째부터 역순으로 조사 4. j값이 음수가 아니어야 되고 key값보다 정렬된 배열에 있는 값이 크면 수행 5. j번째를 j+1번째로 이동 6. j를 하나 감소 7. j번째 정수가 key보다 작으므로 j+1번째가 key값이 들어갈 위치 Slide 11 (of 44)

삽입정렬 프로그램 // 삽입정렬 void insertion_sort(int list[], int n) { int i, j, key; for(i=1; i<n; i++){ key = list[i]; for(j=i-1; j>=0 && list[j]>key; j--) list[j+1] = list[j]; /* 레코드의 오른쪽 이동 */ list[j+1] = key; } Slide 12 (of 44)

삽입정렬 복잡도 분석 최상의 경우: 이미 정렬되어 있는 경우 최악의 경우: 역순으로 정렬 평균의 경우 O(n2) 모든 단계에서 앞에 놓인 자료 전부 이동 비교: 이동: 평균의 경우 O(n2) 많은 이동 필요 -> 레코드가 클 경우 불리 안정된 정렬방법 대부분 정렬되어 있으면 매우 효율적 Slide 13 (of 44)

버블정렬(bubble sort) 인접한 2개의 레코드를 비교하여 순서대로 되어 있지않으면 교환 이러한 비교-교환 과정을 리스트의 왼쪽 끝에서 오른쪽 끝까지 반복(스캔) 한번의 스캔이 완료되면 리스트의 오른쪽 끝에 가장 큰 레코드가 이동함 끝으로 이동한 레코드를 제외한 왼쪽 리스트에 대하여 스캔 과정 반복함 Slide 14 (of 44)

버블정렬 알고리즘 버블정렬 프로그램 BubbleSort(A, n) for i←n-1 to 1 do for j←0 to i-1 do j와 j+1번째의 요소가 크기순이 아니면 교환 j++; i--; 버블정렬 프로그램 #define SWAP(x, y, t) ( (t)=(x), (x)=(y), (y)=(t) ) void bubble_sort(int list[], int n) { int i, j, temp; for(i=n-1; i>0; i--){ for(j=0; j<i; j++) // 앞뒤의 레코드를 비교한 후 교체 if(list[j]>list[j+1]) SWAP(list[j], list[j+1], temp); } Slide 15 (of 44)

버블정렬 복잡도 분석 비교 횟수(최상, 평균, 최악의 경우 모두 일정) 이동 횟수 레코드의 이동 과다 역순으로 정렬된 경우(최악의 경우) : 이동 횟수 = 3 * 비교 횟수 이미 정렬된 경우(최선의 경우) : 이동 횟수 = 0 평균의 경우 : O(n2) 레코드의 이동 과다 이동연산은 비교연산 보다 더 많은 시간이 소요됨 Slide 16 (of 44)

쉘정렬(Shell sort) 삽입 정렬은 요소들이 이웃한 위치로만 이동하므로, 많은 이동에 의해서만 요소가 제자리를 찾아감 삽입정렬이 어느 정도 정렬된 리스트에서 대단히 빠른 것에 착안 삽입 정렬은 요소들이 이웃한 위치로만 이동하므로, 많은 이동에 의해서만 요소가 제자리를 찾아감 요소들이 멀리 떨어진 위치로 이동할 수 있게 하면, 보다 적게 이동하여 제자리 찾을 수 있음  전체 리스트를 일정 간격(gap)의 부분 리스트로 나눔 나뉘어진 각각의 부분 리스트를 삽입정렬 함 간격을 줄임 부분 리스트의 수는 더 작어짐 각 부분 리스트의 크기는 더 커짐 간격이 1이 될때까지 부분 리스트의 삽입정렬 과정 반복 평균적인 경우의 시간적복잡도 : O(n1.5) Slide 17 (of 44)

쉘정렬(Shell sort) (계속) Slide 18 (of 44)

쉘정렬 프로그램 // gap 만큼 떨어진 요소들을 삽입 정렬 // 정렬의 범위는 first에서 last inc_insertion_sort(int list[], int first, int last, int gap) { int i, j, key; for(i=first+gap; i<=last; i=i+gap){ key = list[i]; for(j=i-gap; j>=first && key<list[j];j=j-gap) list[j+gap]=list[j]; list[j+gap]=key; } // void shell_sort( int list[], int n ) // n = size int i, gap; for( gap=n/2; gap>0; gap = gap/2 ) { if( (gap%2) == 0 ) gap++; for(i=0;i<gap;i++) // 부분 리스트의 개수는 gap inc_insertion_sort(list, i, n-1, gap); Slide 19 (of 44)

쉘정렬 복잡도 분석 셸정렬의 장점 시간적복잡도 불연속적인 부분 리스트에서 원거리 자료 이동으로 보다 적은 위치교환으로 제자리 찾을 가능성 증대 부분 리스트가 점진적으로 정렬된 상태가 되므로 삽입정렬 속도 증가 시간적복잡도 최악의 경우 O(n2) 평균적인 경우 O(n1.5) Slide 20 (of 44)

합병정렬 (Merge Sort) 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분리스트를 정렬 정렬된 두 개의 부분 리스트를 합하여 전체 리스트를 정렬함 분할 정복(divide and conquer) 방법 사용 문제를 보다 작은 2개의 문제로 분리하고 각 문제를 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략 분리된 문제가 아직도 해결하기 어렵다면(즉 충분히 작지 않다면) 분할정복방법을 다시 적용(재귀호출 이용) 1. 분할(Divide): 배열을 같은 크기의 2개의 부분 배열로 분할 2. 정복(Conquer): 부분배열을 정렬한다. 부분배열의 크기가 충분히 작지 않으면 재귀호출을 이용하여 다시 분할정복기법 적용 3. 결합(Combine): 정렬된 부분배열을 하나의 배열에 통합 Slide 21 (of 44)

분할정복법 입력파일: (27 10 12 20 25 13 15 22) 1.분할(Divide): 전체 배열을 (27 10 12 20), (25 13 15 22) 2개 부분배열로 분리 2.정복(Conquer): 각 부분배열 정렬 (10 12 20 27), (13 15 22 25) 3.결합(Combine): 2개의 정렬된 부분배열 통합 (10 12 13 15 20 22 25 27) Slide 22 (of 44)

합병정렬의 전체과정 Slide 23 (of 44)

합병정렬의 알고리즘 merge_sort(list, left, right) 1 if left < right 2 mid = (left+right)/2; 3 merge_sort(list, left, mid); 4 merge_sort(list, mid+1, right); 5 merge(list, left, mid, right); 1. 만약 나누어진 구간의 크기가 1이상이면 2. 중간 위치 계산 3. 왼쪽 부분 배열 정렬 : merge_sort 함수 순환 호출 4. 오른쪽 부분 배열을 정렬 : merge_sort 함수 순환 호출 5. 정렬된 2개의 부분 배열을 통합하여 하나의 정렬된 배열 만듦 Slide 24 (of 44)

합병과정 Slide 25 (of 44)

합병 알고리즘 merge(list, left, mid, right): // 2개의 인접한 배열 list[left..mid]와 list[mid+1..right]를 합병 i←left; j←mid+1; k←left; while i≤left and j≤right do if(list[i]<list[j]) then sorted[k]←list[i]; k++; i++; else sorted[k]←list[j]; j++; 요소가 남아있는 부분배열을 sorted로 복사한다; sorted를 list로 복사한다; Slide 26 (of 44)

합병정렬 프로그램 int sorted[MAX_SIZE]; // 추가 공간이 필요 // i는 정렬된 왼쪽리스트에 대한 인덱스 // j는 정렬된 오른쪽리스트에 대한 인덱스 // k는 정렬될 리스트에 대한 인덱스 void merge(int list[], int left, int mid, int right) { int i, j, k, l; i=left; j=mid+1; k=left; // 분할 정렬된 list의 합병 while(i<=mid && j<=right){ if(list[i]<=list[j]) sorted[k++] = list[i++]; else sorted[k++] = list[j++]; } if(i>mid) // 남아 있는 레코드의 일괄 복사 for(l=j; l<=right; l++) sorted[k++] = list[l]; else // 남아 있는 레코드의 일괄 복사 for(l=i; l<=mid; l++) // 배열 sorted[]의 리스트를 배열 list[]로 복사 for(l=left; l<=right; l++) list[l] = sorted[l]; void merge_sort(int list[], int left, int right) { int mid; if(left<right) mid = (left+right)/2; // 리스트의 균등 분할 merge_sort(list, left, mid); // 부분리스트 정렬 merge_sort(list, mid+1, right);//부분리스트 정렬 merge(list, left, mid, right); // 합병 } Slide 27 (of 44)

합병정렬의 복잡도 분석 비교 횟수 이동 횟수 최적, 평균, 최악의 경우 큰 차이 없이 O(n*log(n))의 복잡도 각 패스에서 리스트의 모든 레코드 n개를 비교하므로 n번의 비교 연산 이동 횟수 레코드의 이동이 각 패스에서 2n번 발생하므로 전체 레코드의 이동은 2n*log(n)번 발생 레코드의 크기가 큰 경우에는 매우 큰 시간적 낭비 초래 레코드를 연결 리스트로 구성하여 합병 정렬할 경우, 링크 인덱스만 변경되므로 데이터의 이동은 무시할 수 있을 정도로 작아짐 따라서 크기가 큰 레코드를 정렬할 경우, 다른 어떤 정렬 방법보다 매우 효율적 최적, 평균, 최악의 경우 큰 차이 없이 O(n*log(n))의 복잡도 안정적이며 데이터의 초기 분산 순서에 영향을 덜 받음 Slide 28 (of 44)

퀵정렬(quick sort) 평균적으로 가장 빠른 정렬 방법 분할정복법 사용 리스트를 2개의 부분리스트로 비균등 분할하고, 각각의 부분리스트를 다시 퀵정렬함(재귀호출) Slide 29 (of 44)

퀵정렬 알고리즘 3. 정렬할 범위가 2개 이상의 데이터이면 void quick_sort(int list[], int left, int right) { if(left<right){ int q=partition(list, left, right); quick_sort(list, left, q-1); quick_sort(list, q+1, right); } 3. 정렬할 범위가 2개 이상의 데이터이면 4. partition 함수 호출로 피벗을 기준으로 2개의 리스트로 분할 partition 함수의 반환값이 피벗의 위치 5. left에서 피벗 바로 앞까지를 대상으로 순환호출(피벗 제외) 6. 피벗 바로 다음부터 right까지를 대상으로 순환호출(피벗 제외) Slide 30 (of 44)

분할(partition) 피벗(pivot): 가장 왼쪽 숫자라고 가정 두개의 변수 low와 high를 사용한다. 정지된 위치의 숫자를 교환 low와 high가 교차하면 종료 Slide 31 (of 44)

분할 과정 Slide 32 (of 44)

partition 함수 int partition(int list[], int left, int right) { int pivot, temp; int low,high; low = left; high = right+1; pivot = list[left]; do { do low++; while(low<=right &&list[low]<pivot); do high--; while(high>=left && list[high]>pivot); if(low<high) SWAP(list[low], list[high], temp); } while(low<high); SWAP(list[left], list[high], temp); return high; } Slide 33 (of 44)

퀵정렬 전체과정 밑줄친 숫자: 피봇 Slide 34 (of 44)

퀵정렬의 분석 최상의 경우: 거의 균등한 리스트로 분할되는 경우 패스 수: log2n 2->1 4->2 8->3 … n->log2n 각 패스안에서의 비교횟수: n 총비교횟수: n log2n 총이동횟수: 비교횟수에 비하여 작으므로 무시가능 Slide 35 (of 44)

퀵정렬의 복잡도 분석(cont.) 최악의 경우: 불균등한 리스트로 분할되는 경우 패스 수: n 각 패스 안에서의 비교횟수: n 총 이동횟수: 비교횟수에 비하여 무시가능 (예) 이미 정렬된 리스트를 정렬할 경우 중간 값(medium)을 피벗으로 선택하면 불균등 분할 완화 가능 (1 2  3  4  5  6  7  8  9) 1 (2  3  4  5  6  7  8  9) 1  2 (3  4  5  6  7  8  9) 1  2  3 (4  5  6  7  8  9) 1  2  3  4 (5  6  7  8  9)                     ... 1  2  3  4  5  6  7  8  9 Slide 36 (of 44)

기수정렬(Radix Sort) 대부분의 정렬 방법들은 레코드들을 비교함으로써 정렬 수행 비교에 의한 정렬의 하한인 O(n*log(n)) 보다 좋을 수 있음 기수 정렬은 O(dn) 의 시간적복잡도를 가짐(대부분 d<10 이하) 기수 정렬의 단점 정렬할 수 있는 레코드의 타입 한정(실수, 한글, 한자 등은 정렬 불가) 즉, 레코드의 키들이 동일한 길이를 가지는 숫자나 단순 문자(알파벳 등)이어야만 함 Slide 37 (of 44)

기수정렬 (예) 한자리수 (8, 2, 7, 3, 5)의 기수정렬 단순히 자리수에 따라 버켓(bucket)에 넣었다가 꺼내면 정렬됨 Slide 38 (of 44)

기수정렬 만약 2자리수이면? (28, 93, 39, 81, 62, 72, 38, 26) 낮은 자리수로 먼저 분류한다음, 순서대로 읽어서 다시 높은 자리수로 분류하면 된다. Slide 39 (of 44)

기수정렬 알고리즘 버킷은 큐로 구현 버킷의 개수는 키의 표현 방법과 밀접한 관계 이진법을 사용한다면 버킷은 2개. RadixSort(list, n): for d←LSD의 위치 to MSD의 위치 do {   d번째 자릿수에 따라 0번부터 9번 버킷에 집어놓는다.   버킷에서 숫자들을 순차적으로 읽어서 하나의 리스트로 합친다.   d++; } 버킷은 큐로 구현 버킷의 개수는 키의 표현 방법과 밀접한 관계 이진법을 사용한다면 버킷은 2개. 알파벳 문자를 사용한다면 버킷은 26개 십진법을 사용한다면 버킷은 10개 (예)32비트의 정수의 경우, 8비트씩 나누면 -> 버킷은 256개로 늘어남. 대신 필요한 패스의 수는 4로 줄어듦.  Slide 40 (of 44)

기수정렬 프로그램 // 6장의 큐 소스를 여기에... #define BUCKETS 10 #define DIGITS 4 void radix_sort(int list[], int n) { int i, b, d, factor=1; QueueType queues[BUCKETS]; for(b=0;b<BUCKETS;b++) init(&queues[b]); // 큐들의 초기화 for(d=0; d<DIGITS; d++){ for(i=0;i<n;i++) // 데이터들을 자리수에 따라 큐에 입력 enqueue( &queues[(list[i]/factor)%10], list[i]); for(b=i=0;b<BUCKETS;b++) // 버켓에서 꺼내어 list로 합친다. while( !is_empty(&queues[b]) ) list[i++] = dequeue(&queues[b]); factor *= 10; // 그 다음 자리수로 간다. } Slide 41 (of 44)

기수정렬 복잡도 분석 n개의 레코드, d개의 자릿수로 이루어진 키를 기수정렬할 경우 O(dn) 의 시간적복잡도 실수, 한글, 한자로 이루어진 키는 정렬 못함 Slide 42 (of 44)

정렬 알고리즘의 비교 Slide 43 (of 44)

정렬 알고리즘의 실험 예 (정수 60,000개) Slide 44 (of 44)