-09- 쉽게배우는알고리즘 장. 정렬 Sortng http://academy.hanb.co.kr 장. 정렬 Sortng 은유, 그것은정신적상호연관성의피륙을짜는방법이다. 은유는살아있다는것의바탕이다. - 그레고리베이트슨 - 2 - 한빛미디어 1
-09- 학습목표 기본정렬알고리즘을이해한다. 정렬을귀납적관점에서볼수있도록한다. 1 장과 2 장에서배운기법을사용해각정렬의수행시간을분석할수있도록한다. 비교정렬의한계를이해하고, 선형시간정렬이가능한조건과선형시간정렬알고리즘을이해한다. - - 한빛미디어 Sortng Algorthms 대부분 O(n 2 ) 과 O(nlogn) 사이 Input 이특수한성질을만족하는경우에는 O(n) sortng 도가능 E.g., nput 이 O(n) 과 O(n) 사이의정수 - 4-2
-09- 원시적 Sortng 알고리즘들의재조명 알고리즘을보는시각 flow 중심 관계중심 원시적정렬알고리즘들을관계중심의시각으로다시한번조명 생각하는방법에대한좋은연습자료 - 5 - Selecton Sort 각루프마다 최대원소를찾는다 최대원소와맨오른쪽원소를교환한다 맨오른쪽원소를제외한다 하나의원소만남을때까지위의루프를반복 - 6 -
-09- Fndng the Recursve Structure The largest tem ü 수행시간 : (n-1)+(n-2)+ +2+1 = O(n 2 ) Worst case Average case - 7 - selectonsort(a[], n) 배열 A[1... n] 을정렬한다 for last n downto 2 ------------------ 1 A[1... last] 중가장큰수 A[k] 를찾는다 ; ----------- 2 A[k] A[last]; A[k] 와 A[last] 의값을교환 -------- ü 수행시간 : 1 의 for 루프는 n-1 번반복 2 에서가장큰수를찾기위한비교횟수 : n-1, n-2,, 2, 1 의교환은상수시간작업 ü (n-1)+(n-2)+ +2+1 = O(n 2 ) - - 4
-09- 정렬할배열이주어짐 1 4 가장큰수를찾는다 (7) 7 Selecton Sort 의작동예 1 4 7 7 을맨오른쪽수 () 와자리바꾼다 1 의첫번째 loop 1 4 7 맨오른쪽수를제외한나머지에서가장큰수를찾는다 () 1 4 7 를맨오른쪽수 () 와자리바꾼다 1 의두번째 loop 1 4 7 맨오른쪽두수를제외한나머지에서가장큰수를찾는다 (4) 1 4 7... 을맨오른쪽수 () 와자리바꾼다 1 4 7 최종배열 1 4-9 - 7 Bubble Sort ü 수행시간 : (n-1)+(n-2)+ +2+1 = O(n 2 ) - 10 - Worst case Average case 5
-09- bubblesort(a[], n) A[1... n] 을정렬한다 for last n downto 2 ----------------- 1 for 1 to last-1 ------------------ 2 f (A[] > A[+1]) then A[] A[+1]; 원소교환 -- ü 수행시간 : 1 의 for 루프는 n-1 번반복 2 의 for 루프는각각 n-1, n-2,, 2, 1 번반복 은상수시간작업 ü (n-1)+(n-2)+ +2+1 = O(n 2 ) - - 정렬할배열이주어짐 1 4 7 Bubble Sort 의작동예 왼쪽부터시작해이웃한쌍들을비교해간다 1 4 7 순서대로되어있지않으면자리바꾼다 1 4 7 1 4 7 1 4 7 1 4 7 맨오른쪽수 (7) 를대상에서제외한다 1 4 7-12 - 6
-09- 왼쪽부터시작해이웃한쌍들을비교해간다 1 4 7 순서대로되어있지않은경우에는자리바꾼다 1 4 7 1 4 7 1 4 7 1 4 7 1 4 7 1 4 7 맨오른쪽수 () 를대상에서제외한다 1 4-1 - 7 앞의작업을반복하면서계속제외해나간다 1 4 7 두개짜리배열의처리를끝으로정렬이완료된다 1 4 7 1 4 7 ü Improved BubbleSort 배열이우연히도정렬되어있는경우에도의미없이순환함 개선책 : 교재 76p 참조 - 14-7
-09- Inserton Sort ü 수행시간 : O(n 2 ) Worst case: 1+2+ +(n-2)+(n-1) Average case: ½ (1+2+ +(n-2)+(n-1)) - - nsertonsort(a[], n) A[1... n] 을정렬한다 for 2 to n ---------------------- 1 A[1... ] 의적당한자리에 A[] 를삽입한다 ; ----------- 2 ü 수행시간 : 1 의 for 루프는 n-1 번반복 2 의삽입은최악의경우 -1 회비교 ü 삽입시간 : A[] 가 A[-1] 보다크면그냥제자리에두면됨. 그렇지않다면, A[-1] 부터시작해서왼쪽으로차례로훑으면서 A[] 가들어갈자리를찾는다. ü Worst case: 1+2+ +(n-2)+(n-1) = O(n 2 ) ü Average case: ½ (1+2+ +(n-2)+(n-1)) = O(n 2 ) - 16 -
-09- Inductve Verfcaton of Inserton Sort 배열 A[1] 만놓고보면 정렬되어있음 배열 A[1 k] 까지정렬되어있다면 è 2 행의삽입에의해 A[1 k+1] 까지정렬된다 ü 고등학교에서배운수학적귀납법과다를바없음 - 17 - Inductve Verfcaton of Selecton/Bubble Sort 각자생각해보기 삽입정렬과가장큰차이점은무엇인가? 교재 79p 참조 - 1-9
-09- mergesort(a[ ], p, r) A[p... r] 을정렬한다 f (p < r) then q (p+q)/2; ----------------------- 1 Mergesort p, q의중간지점계산 전반부정렬 mergesort(a, p, q); ---------------- 2 mergesort(a, q+1, r); -------------- 후반부정렬 merge(a, p, q, r); ------------------ 4 병합 merge(a[ ], p, q, r) 정렬되어있는두배열 A[p... q] 와 A[q+1... r] 을합하여정렬된하나의배열 A[p... r] 을만든다. - 19 - 정렬할배열이주어짐 Mergesort 의작동예 1 7 4 배열을반반으로나눈다 1 7 4 1 각각독립적으로정렬한다 1 7 4 2 병합한다 ( 정렬완료 ) 1 4 7 4 - - 10
-09- p q r 1 7 4 Merge 의작동예 t 1 7 4 t 1 7 4 t - 21-1 7 4 t 1 7 4 t 1 7 4 t - 22 -
-09-1 7 4 t 7 4 1 t 7 1 4 t - 2-1 4 7 t - 24-12
-09- Anmaton (Mergesort) 72 1 42 97 94 ½6 1 7 691 27 74 2 49 7 49 2 7 72 49 94 7 2 9 4 ü 수행시간 : O(nlogn) - 25 - Qucksort qucksort(a[], p, r) A[p... r] 을정렬한다 f (p < r) then q = partton(a, p, r); 분할 qucksort(a, p, q-1); 왼쪽부분배열정렬 qucksort(a, q+1, r); 오른쪽부분배열정렬 partton(a[], p, r) 배열 A[p... r] 의원소들을 A[r] 을기준으로양쪽으로재배치하고 A[r] 이자리한위치를 return 한다 ; - 26-1
-09- Anmaton (Qucksort) 5 1 2 1 49 4 2 45 269 66 9 2 1 21 4 4 2 69 6 9 2 1 2 1 4 6 6 1 ü 평균 6 수행시간 : O(nlogn) ü 최악의경우수행시간 : O(n 2 ) - 27 - Qucksort 의작동예 정렬할배열이주어짐. 첫번째수를기준으로삼는다. 1 4 7 기준보다작은수는기준의왼쪽에나머지는기준의오른쪽에오도록재배치한다 1 4 7 (a) 기준 (1) 왼쪽과오른쪽을각각독립적으로정렬한다 ( 정렬완료 ) 1 4 7 (b) - 2-14
-09- p 1 4 7 r Partton 의예 1 4 7 1 4 7 1 4 7 1 4 7 4 7 1 - - (a) (b) (c) 7 1 4 7 1 4 7 1 4 7 1 4 1 4 7-0 - (d) (e)
-09- Heapsort Heap( 최소힙을가정 ) Complete bnary tree 로서다음의성질을만족한다 각노드의값은자신의 chldren 의값보다작다.( 힙에값이같은원소가두개이상있는경우에는 작다 대신 작거나같다 ) 최소힙에서는이진트리의루트에는최소값이자리하게됨. Heapsort 주어진배열을힙으로만든다음, 힙에서가장작은값을차례로하나씩제거하면서힙크기를줄여나감. 나중에힙에아무원소도남아있지않으면힙정렬완료. 제거순서가정렬순서임 - 1 - Heap 6 4 4 9 7 힙 6 9 7 힙아님 - 2-16
-09-6 4 7 9 힙아님 - - Heap 은 Array 를이용해서표현할수있다 1 4 2 6 4 5 6 9 7 A 1 2 4 5 6 6 4 9 7 ü A[k] 의자식 : A[2k] 와 A[2k+1] 에있음 ü A[k] 의부모 : A[ k/2 ] - 4-17
-09- 힙정렬알고리즘 heapsort(a[ ], n) buldheap(a, n); for n downto 2 A[1] A[]; heapfy(a, 1, -1); 힙만들기 교환한후 A[1] 이루트가되게힙을수선 ü 최악의경우에도 O(nlogn) 시간소요! - 5 - 힙만들기 buldheap(a[ ], n) // A[1 n] 을힙으로만든다. for ß downto 1 // 말단노드는생략해도되므로 부터시작. heapfy(a,, n); // 들중맨마지막노드의인덱스임. Heapfy(A[], k, n) // A[k] 를루트로하는트리를힙성질을만족하도록수선한다. // A[k] 의두자식을루트로하는서브트리는힙성질을만족하고있다. // n은최대인덱스 ( 전체배열의크기 ) left ß 2k; rght ß 2k+1; // 작은자식고르기. smaller: A[2k] 와 A[2k+1] 중작은원소 f (rght <= n) then // k가두자식을가지는경우 f (A[left] < A[rght]) then smaller ß left; else smaller ß rght; else f (left <= n) then smaller ß left; // k의왼쪽자식만있는경우 else return; // A[k] 가말단노드임. 끝남. // 재귀적조정 f (A[smaller] < A[k]) then A[k] ßà A[smaller]; heapfy(a, smaller, n); 은리프가아닌노드 - 6-1
-09- Heapsort 의작동예 (a) (b) 7 (c) 제거 4 6 4 6 4 6 7 9 7 9 9 (f) 6 (e) 6 (d) 9 4 제거 7 9 4 9 7 4 6 7 4-7 - 6 제거 (h) 7 제거 9 (g) 9 7 7 9 7 () 6 4 6 4 6 4 (k) 9 제거 () 7 6 4 9 7 6 4 - - 19
-09- 힙정렬알고리즘의복잡도 buldheap Θ(n) heapsort Θ(nlogn) ü 최악의경우에도 O(nlogn) 시간소요! - 9 - O(n) Sort 두원소를비교하는것을기본연산으로하는비교정렬의하한선은 Θ(nlogn) 이다. 그러나원소들이특수한성질을만족하면 O(n) 정렬도가능 Countng Sort 원소들의크기가모두 O(n) ~ O(n) 범위에있을때 Radx Sort 원소들이모두 k 이하의자리수를가졌을때 (k: 상수 ) - 40 -
-09- Countng Sort countngsort(a[ ], n) A[ ]: 입력배열, B[ ]: 출력배열, n: 입력크기 for 1 to k C[] 0; for 1 to n C[A[]]++; 이지점에서 C[] : 값이 인원소의총수 for 2 to k C[] C[] + C[-1] 이지점에서 C[] : 보다작거나같은원소의총개수 for n downto 1 B[C[A[]]] A[]; C[A[]]--; // 같은값이여러개있을때 - 41 - Radx Sort radxsort(a[ ], d) ü Stable sort for = d downto 1 Do a stable sort on A[ ] by th dgt; 같은값을가진 tem 들은 sortng 후에도원래의순서가유지되는성질을가진 sort 를일컫는다. - 42-21
-09-012 60 0004 0004 0004 24 20 0222 1061 012 0222 1061 012 012 0222 0004 0222 20 20 02 02 012 24 24 1061 60 02 60 0222 60 1061 24 1061 02 20 20 0004 02 60 24 ü Runnng tme: O(n) d: a constant - 4 - 효율성비교 Worst Case Average Case Selecton Sort n 2 n 2 Bubble Sort n 2 n 2 Inserton Sort n 2 n 2 Mergesort nlogn nlogn Qucksort n 2 nlogn Countng Sort n n Radx Sort n n Heapsort nlogn nlogn - 44-22
-09- Thank you - 45 - 한빛미디어 2