정렬 강의자료

Transcription

1 CHAP 9 : 정렬

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

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

4 정렬알고리즘개요 모든경우에최적인정렬알고리즘은없음 각응용분야에적합한정렬방법사용해야함 레코드수의많고적음 레코드크기의크고작음 Key의특성 ( 문자, 정수, 실수등 ) 메모리내부 / 외부정렬 정렬알고리즘의평가기준 비교횟수의많고적음 이동횟수의많고적음

5 정렬알고리즘개요 단순하지만비효율적인방법 삽입정렬, 선택정렬, 버블정렬등 복잡하지만효율적인방법 퀵정렬, 히프정렬, 합병정렬, 기수정렬등 내부정렬 (internal sorting) 모든데이터가주기억장치에저장되어진상태에서정렬 외부정렬 (external sorting) 외부기억장치에대부분의데이터가있고일부만주기억장치에저장된상태에서정렬 정렬알고리즘의안정성 (stability) 동일한키값을갖는레코드들의상대적인위치가정렬후에도바뀌지않음 안정하지않은정렬의예 =====>

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

7 선택정렬유사코드 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); } } // 최소값탐색

8 선택정렬프로그램 #include <stdio.h> #include <stdlib.h> #define MAX_SIZE #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]);

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

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

11 삽입정렬알고리즘 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 값이들어갈위치

12 삽입정렬프로그램 // 삽입정렬 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; // 레코드의오른쪽이동

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

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

15 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);

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

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

18 셸정렬 (Shell sort)

19 셸정렬프로그램 // 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); }

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

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

22 합병정렬 입력파일 : ( ) 1. 분할 (Divide): 전체배열을 ( ), ( ) 2 개부분배열로분리 2. 정복 (Conquer): 각부분배열정렬 ( ), ( ) 3. 결합 (Combine): 2 개의정렬된부분배열통합 ( )

23 합병정렬의전체과정

24 합병정렬알고리즘 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개의부분배열을통합하여하나의정렬된배열만듬

25 합병과정

26 합병알고리즘 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]; k++; j++; 요소가남아있는부분배열을 sorted 로복사한다 ; sorted 를 list 로복사한다 ;

27 합병의중간상태

28 합병정렬프로그램 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); // 합병 } } 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[k++] = list[l]; // 배열 sorted[] 의리스트를배열 list[] 로복사 for(l=left; l<=right; l++) list[l] = sorted[l]; }

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

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

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

32 분할 (partition) 피벗 (pivot): 가장왼쪽숫자라고가정 두개의변수 low 와 high 를사용한다. low 는피벗보다작으면통과, 크면정지 high 는피벗보다크면통과, 작으면정지 정지된위치의숫자를교환 low 와 high 가교차하면종료

33 분할과정

34 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;

35 퀵정렬전체과정 밑줄친숫자 : 피벗

36 퀵정렬복잡도분석 최선의경우 ( 거의균등한리스트로분할되는경우 ) 패스수 : log(n) 2->1 4->2 8->3 n->log(n) 각패스안에서의비교횟수 : n 총비교횟수 : n*log(n) 총이동횟수 : 비교횟수에비하여적으므로무시가능

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

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

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

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

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

42 기수정렬프로그램 // 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; // 그다음자리수로간다.

43 기수정렬복잡도분석 n 개의레코드, d 개의자릿수로이루어진키를기수정렬할경우 메인루프는자릿수 d번반복 큐에 n개레코드입력수행 O(dn) 의시간적복잡도 키의자릿수 d 는 10 이하의작은수이므로빠른정렬임 실수, 한글, 한자로이루어진키는정렬못함

44 정렬알고리즘의비교

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