Microsoft PowerPoint - 5장 정렬

Transcription

1 01. 버블 02. 삽입 03. 퀵 04. C 표준 라이브러리의 퀵 정렬 정렬 정렬 정렬 함수

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

3 정렬은왜하는가?

4 학생들의레코드 이름학번주소연락처 레코드 필드 필드 필드 필드 키 (key)

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

6 선택정렬 (selection sort) 정렬이안된숫자들중에서최소값을선택하여배열의첫번째요소와교환 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++; 분석 최소값을선택하는데걸리는시간 : O(n) 숫자의개수가 n 전체시간복잡도 : O(n 2 ) 안정성을만족하지않는다.

7 인접한레코드가순서대로되어있지않으면교환 전체가정렬될때까지비교 / 교환연산을계속

8 정렬과정이물속깊은곳에서일어난거품이수면을향해올라오는모습과같다고해서붙여진이름 데이터집합을순회하면서집합내의이웃요소들끼리의교환을통해정렬

9 버블정렬예

10 BubbleSort(A, n) for i n-1 to 1 do for j 0 to i-1 do j와 j+1번째의요소가크기순이아니면교환 ; j++; i--;

11 #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); } }

12 비교횟수 버블정렬의비교횟수는최상, 평균, 최악의어떠한경우에도항상 일정 n 1 i 1 i n ( 2 n 1) 2 O( n ) 이동횟수 최악 : 역순정렬이동 = 3* 비교 최상 : 이미정렬이동 = 0 평균 : O(n 2 )

13 삽입정렬은정렬되어있는부분에새로운레코드를적절한위치에삽입하는과정을반복 삽입정렬의과정

14 데이터집합을순회하면서정렬이필요한요소를뽑아내어이를다시적당한곳에삽입해나가는알고리즘 1. 데이터집합에서정렬대상이되는요소들을선택합니다. ( 이정렬대상은왼쪽부터선택해나가며, 그범위가처음에는 2 개이지만, 알고리즘반복횟수가늘어날때마다 1 개씩커집니다. 정렬대상의최대범위는 데이터집합의크기 -1 이됩니다.) 2. 정렬대상의가장오른쪽에있는요소가정렬대상중가장큰값을갖고있는지확인합니다. 만약그렇지않다면, 이요소를정렬대상에서뽑아내고, 이요소가위치할적절한곳을정렬대상내에서찾습니다.( 여기서적절한곳이라함은, 데이터집합의가장왼쪽을기준으로했을때자신보다더작은요소가없는위치를말합니다.) 3. 뽑아든요소를삽입할적절한곳을찾았다면, 정렬대상내에서삽입할값보다큰값을갖는모든요소를한자리씩오른쪽으로이동시키고 ( 이러면요소가뽑힌자리가채워지고, 새로이위치할곳이비워지겠죠?), 새로생긴빈자리에삽입시킵니다. 4. 전체데이터집합의정렬이완료될때까지 1) ~ 3) 를반복합니다.

15 삽입정렬예

16 Algorithm InsertionSort(list, n): Input: n개의정수를저장하고있는배열 list Output: 정렬된배열 list for i 1 to n-1 do { 정렬된리스트에서 list[i] 보다더큰요소들이동 ; list[i] 를정렬된리스트의적절한위치에삽입 ; i++; }

17 // 삽입정렬 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; } } 많은이동 -> 레코드가클경우불리 안정된정렬방법 이미정렬되어있으면효율적

18 최상의경우 : 이미정렬되어있는경우 비교 : n-1 번 이동 : 2(n-1) 번 최악의경우 : 역순으로정렬 모든단계에서앞에놓인자료전부이동 비교 : n 1 i 1 i n n 1) O( n 2 ( 2 ) 이동 : n n 1) 2 ( 2 2( n 1) O( n )

19 분할정복법 (divide and conquer) 문제를작은 2 개의문제로분리하고각각을해결한다음, 결과를모아서원래의문제를해결하는전략 분리된문제가아직도해결하기어렵다면, 즉충분히작지않다면분할정복방법을다시적용 주로재귀호출을이용하여구현 1. 분할 (Divide): 배열을같은크기의 2개의부분배열로분할한다. 2. 정복 (Conquer): 부분배열을정렬한다. 부분배열의크기가충분히작지않으면재귀호출을이용하여다시분할정복기법을적용한다. 3. 결합 (Combine): 정렬된부분배열을하나의배열에통합한다. 입력파일 : 분할 (Divide): 배열을 과 의 2개의부분배열로분리 2. 정복 (Conquer): 부분배열을정렬하여 과 를얻는다. 3. 결합 (Combine): 부분배열을통합하여 을얻는다.

20 평균적으로가장빠른정렬방법 분할정복법사용 전체리스트를 2 개의부분리스트로분할하고, 각각의부분리스트를다시퀵정렬로정렬

21 분할정복 (Divide and Conquer) 에기반한알고리즘 1. 데이터집합내에서임의의기준요소를선택하고, 기준요소보다작은요소들은순서에관계없이무조건기준요소의왼편에, 큰값은오른편에위치시킵니다. 2. 기준요소왼편에는기준요소보다작은요소들이모여있고오른편에는큰요소들이모여있겠죠? 이렇게나눈데이터집합들을다시 1 에서와같이임의의기준요소를선택하고같은방법으로데이터집합을분할합니다 과 2 의과정을더이상데이터집합을나눌수없을때까지반복하면정렬된데이터집합을얻게됩니다.

22 퀵정렬예 기준요소로선택

23 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 까지를대상으로순환호출한다 ( 피봇은제외된다 ).

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

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

26 밑줄친숫자 : 피봇

27 최상의경우 : 거의균등한리스트로분할되는경우 패스수 : log 2 n 2->1 4->2 8->3 n->log 2 n 각패스안에서의비교횟수 : n 총비교횟수 : n log 2 n 총이동횟수 : 비교횟수에비하여무시가능

28 최악의경우 : 불균등한리스트로분할되는경우 패스수 : n 각패스안에서의비교횟수 : n 총비교횟수 : n 2 총이동횟수 : 비교횟수에비하여무시가능 ( 예 ) 정렬된리스트가주어졌을경우 ( ) 1 ( ) 1 2 ( ) ( ) ( )

29 퀵정렬의성능 : 루프의반복횟수대신재귀횟수를이용하여분석 최선의경우 : nlog2 n 최악의경우 : 평균의경우 :

30 qsort() 함수원형 void qsort( void *base, /* 데이터집합배열의주소 */ size_t num, /* 데이터요소의개수 */ size_t width, /* 한데이터요소의크기 */ int ( cdecl *compare )(const void *, const void *) /* 비교함수에대한포인터 */ ); int CompareScore( const void *_elem1, const void *_elem2 ) { int* elem1 = (int*)_elem1; int* elem2 = (int*)_elem2; } if ( *elem1 > *elem2) return 1; else if ( *elem1 < *elem2) return -1; else return 0;

31 합병정렬은리스트를두개로나누어, 각각을정렬한다음, 다시하나로합치는방법 합병정렬은분할정복기법에바탕

32

33 merge_sort(list, left, right) if left < right mid = (left+right)/2; merge_sort(list, left, mid); merge_sort(list, mid+1, right); merge(list, left, mid, right); 하나의리스트를두개의균등한크기로분할하고분할된부분리스트를정렬한다음, 두개의정렬된부분리스트를합하여전체가정렬된리스트를얻음 실제로정렬이이루어지는시점은 2 개의리스트를합병하는단계

34

35 merge(list, left, mid, last): // 2 개의인접한배열 list[left..mid] 와 list[mid+1..right] 를합병 b1 left; e1 mid; b2 mid+1; e2 right; sorted 배열을생성 ; index 0; while b1 e1 and b2 e2 do if(list[b1]<list[b2]) then sorted[index] list[b1]; b1++; index++; else sorted[index] list[b2]; b2++; index++; 요소가남아있는부분배열을 sorted로복사한다 ; sorted를 list로복사한다 ;

36 비교횟수 합병정렬은크기 n인리스트를정확히균등분배 퀵정렬의이상적인경우와마찬가지로정확히 logn개의패스를가짐 각패스에서리스트의모든레코드 n개를비교하여합병하므로 n 번의비교연산이수행된다. 합병정렬은최적, 평균, 최악의경우모두큰차이없이 nlogn번의비교를수행하므로 O(nlogn) 의복잡도를가진다. 합병정렬은안정적이며데이터의초기분산순서에영향을덜받는다. 이동횟수 배열을이용하는레코드의이동이각패스에서 2n 번발생하므로전체레코드의이동은 2nlogn 번발생한다. 레코드를연결리스트로구성하여합병정렬할경우, 링크인덱스만변경되므로데이터의이동은무시할수있을정도로작아진다. 크기가큰레코드를정렬할경우, 연결리스트를이용하는합병정렬은퀵정렬을포함한다른어떤정렬방법보다매우효율적이다.

37 삽입정렬이어느정도정렬된배열에대해서는대단히빠른것에착안한방법 셀정렬은삽입정렬보다빠르다. 삽입정렬의최대문제점은요소들이이동할때, 이웃한위치로만이동쉘정렬에서는요소들이멀리떨어진위치로도이동할수있다. 전체리스트를일정간격의부분리스트로나누고부분리스트를정렬한다. 간격 (gap) 은점점줄어들게된다. 평균적인경우시간복잡도는 O(n 1.5 )

38 // 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); } }

39 기수정렬은레코드를전체를비교하지않고자리수개념을적용하여정렬하는방법 O(nlogn) 이라는이론적인하한선을깰수있는유일한방법 O(kn) 의시간복잡도를가지는데대부분 k<4 이하 단점 : 정렬할수있는레코드의타입이한정-> 레코드의키들이동일한길이를가지는숫자나문자열로구성 ( 예 ) 한자리수의기수정렬 (8, 2, 7, 3, 5) 단순히자리수에따라버킷에넣었다가꺼내면정렬됨

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