쉽게배우는알고리즘 장. 정렬 Sorting http://www.hanbit.co.kr
장. 정렬 Sorting 은유, 그것은정신적상호연관성의피륙을짜는방법이다. 은유는살아있다는것의바탕이다. - 그레고리베이트슨 - 2 -
학습목표 기본정렬알고리즘을이해한다. 정렬을귀납적관점에서볼수있도록한다. 1 장과 2 장에서배운기법을사용해각정렬의수행시간을분석할수있도록한다. 비교정렬의한계를이해하고, 선형시간정렬이가능한조건과선형시간정렬알고리즘을이해한다. - -
Sorting Algorithms 대부분 O(n 2 ) 과 O(nlogn) 사이 Input 이특수한성질을만족하는경우에는 O(n) sorting 도가능 E.g., input 이 O(n) 과 O(n) 사이의정수 - 4 -
원시적 Sorting 알고리즘들의재조명 알고리즘을보는시각 flow 중심 관계중심 원시적정렬알고리즘들을관계중심의시각으로다시한번조명 생각하는방법에대한좋은연습자료 - 5 -
Selection Sort 각루프마다 최대원소를찾는다 최대원소와맨오른쪽원소를교환한다 맨오른쪽원소를제외한다 하나의원소만남을때까지위의루프를반복 - 6 -
Finding the Recursive Structure The largest item 수행시간 : (n-1)+(n-2)+ +2+1 = O(n 2 ) - 7 - Worst case Average case
selectionsort(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 ) - -
정렬할배열이주어짐 1 4 가장큰수를찾는다 (7) 7 IT COOKBOOK Selection 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
bubblesort(a[], n) A[1... n] 을정렬한다 { for last n downto 2 ----------------- 1 for i 1 to last-1 ------------------ 2 if (A[i] > A[i+1]) then A[i] A[i+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 -
왼쪽부터시작해이웃한쌍들을비교해간다 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-14 -
Insertion Sort 수행시간 : O(n 2 ) Worst case: 1+2+ +(n-2)+(n-1) Average case: ½ (1+2+ +(n-2)+(n-1)) - -
insertionsort(a[], n) A[1... n] 을정렬한다 { for i 2 to n ---------------------- 1 A[1... i] 의적당한자리에 A[i] 를삽입한다 ; ----------- 2 } 수행시간 : 1 의 for 루프는 n-1 번반복 2 의삽입은최악의경우 i-1 회비교 Worst case: 1+2+ +(n-2)+(n-1) = O(n 2 ) Average case: ½ (1+2+ +(n-2)+(n-1)) = O(n 2 ) - 16 -
Inductive Verification of Insertion Sort 배열 A[1] 만놓고보면 정렬되어있음 배열 A[1 k] 까지정렬되어있다면 2 행의삽입에의해 A[1 k+1] 까지정렬된다 고등학교에서배운수학적귀납법과다를바없음 - 17 -
Inductive Verification of Selection/Bubble Sort IT COOKBOOK 각자생각해보기 삽입정렬과가장큰차이점은무엇인가? - 1 -
Mergesort mergesort(a[ ], p, r) A[p... r] 을정렬한다 { if (p < r) then { q (p+q)/2; ----------------------- 1 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
p q r 1 7 4 IT COOKBOOK Merge 의작동예 i j t 1 7 4 i t j 1 7 4 i j t - 21 -
1 7 4 i j t 1 7 4 i j t 1 7 4 i t j - 22 -
1 7 4 i j t 7 4 i j 1 t 7 i j 1 4 t - 2 -
1 4 7 i j t - 24 -
Animation (Mergesort) 72 1 42 97 94 6 1 7 691 27 74 2 49 7 49 27 72 94 94 7 2 9 4 수행시간 : O(nlogn) - 25 -
Quicksort quicksort(a[], p, r) A[p... r] 을정렬한다 { if (p < r) then { q = partition(a, p, r); 분할 quicksort(a, p, q-1); 왼쪽부분배열정렬 quicksort(a, q+1, r); 오른쪽부분배열정렬 } } partition(a[], p, r) { 배열 A[p... r] 의원소들을 A[r] 을기준으로양쪽으로재배치하고 A[r] 이자리한위치를 return 한다 ; } - 26 -
Animation (Quicksort) 5 1 2 1 49 4 2 45 269 66 9 2 1 21 4 4 2 69 6 9 21 2 1 1 2 4 6 6 1 평균 6 수행시간 : O(nlogn) 최악의경우수행시간 : O(n 2 ) - 27 -
Quicksort 의작동예 정렬할배열이주어짐. 첫번째수를기준으로삼는다. 1 4 7 기준보다작은수는기준의왼쪽에나머지는기준의오른쪽에오도록재배치한다 1 4 7 (a) 기준 (1) 왼쪽과오른쪽을각각독립적으로정렬한다 ( 정렬완료 ) 1 4 7 (b) - 2 -
p 1 4 7 r IT COOKBOOK Partition 의예 i i j 1 4 7 j 1 4 7 i j 1 4 7 i j 1 4 7 i j 4 7 1 i j - - (a) (b) (c)
7 1 4 i j 7 1 4 i j 7 1 4 i j 7 1 4 i 1 4 7 i - 0 - (d) (e)
Heapsort Heap Complete binary tree 로서다음의성질을만족한다 Heapsort 각노드의값은자신의 children 의값보다크지않다 주어진배열을힙으로만든다음, 차례로하나씩힙에서제거함으로써정렬한다 - 1 -
heapsort(a[ ], n) { buildheap(a, n); 힙만들기 for i n downto 2 { A[1] A[i]; 교환 heapify(a, 1, i-1); } } 최악의경우에도 O(nlogn) 시간소요! - 2 -
Heap 6 4 4 9 7 힙 6 9 7 힙아님 - -
6 4 7 9 힙아님 - 4 -
Heap 은 Array 를이용해서표현할수있다 1 4 2 6 4 5 6 9 7 A 1 2 4 5 6 6 4 9 7-5 -
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-6 -
6 제거 (h) 7 제거 9 (g) 9 7 7 9 7 (i) 6 4 6 4 6 4 (k) 9 제거 (j) 7 6 4-7 - 9 7 6 4
O(n) Sort 두원소를비교하는것을기본연산으로하는정렬의하한선은 Ω (nlogn) 이다 그러나원소들이특수한성질을만족하면 O(n) 정렬도가능하다 Counting Sort 원소들의크기가모두 O(n) ~ O(n) 범위에있을때 Radix Sort 원소들이모두 k 이하의자리수를가졌을때 (k: 상수 ) - -
Counting Sort countingsort(a[ ], n) simple version { A[ ]: 입력배열, n: 입력크기 for i = 1 to k C[i] 0; for j = 1 to n C[A[j]]++; 이지점에서 C[i] : 값이 i 인원소의총수 for i = 1 to k print C[i] i s; i 를 C[i] 번출력 } 원리에집중하기위한 Simple version 임. Full version 은 textbook 참조! - 9 -
Radix Sort radixsort(a[ ], d) { } for j = d downto 1 { } Stable sort Do a stable sort on A[ ] by j th digit; 같은값을가진 item 들은 sorting 후에도원래의순서가유지되는성질을가진 sort 를일컫는다. - 40 -
012 60 0004 0004 0004 24 0222 1061 012 0222 1061 012 012 0222 0004 0222 02 02 012 24 24 1061 60 02 60 0222 60 1061 24 1061 02 0004 02 60 24 Running time: O(n) d: a constant - 41 -
효율성비교 Worst Case Average Case Selection Sort n 2 n 2 Bubble Sort n 2 n 2 Insertion Sort n 2 n 2 Mergesort nlogn nlogn Quicksort n 2 nlogn Counting Sort n n Radix Sort n n Heapsort nlogn nlogn - 42 -
Thank you - 4 -