빠른정렬(Quick Sort) – 개요 (1/2) 1962년에 영국의 호아(C.A.R. Hoare)의 의해서 고안 빠른정렬(Quicksort)란 이름이 오해의 여지가 있음 사실 가장 빠른 정렬 알고리즘이라고 할 수는 없다. 주어진 배열을 두 개로 분할하고, 각각을 정렬한다. 합병정렬과 동일? 합병정렬과 다른점 합병정렬은 아무생각없이 두 부분으로 나누는 반면에, 빠른정렬은 분할할 때부터 기준 아이템(pivot item) 중심으로, 이보다 작은 것은 왼편, 큰 것은 오른편에 위치시킨다. 즉, 정렬(정복과정)이 분할 과정에서 함께 행해진다. 각 부분 정렬이 끝난 후, 합병정렬은“합병”이라는 후처리 작업이 필요하나, 빠른정렬은 필요로 하지 않는다.
빠른정렬(Quick Sort) – 개요 (2/2) 예제: 15, 22, 13, 27, 12, 10, 20, 25
빠른정렬 – 정렬 알고리즘 void quicksort (index low, index high){ 입력: (1) 크기가 n인 배열 S[1..n] 전역적으로 정의 (2) low - 배열의 첫번째 인덱스, high – 배열의 마지막 인덱스 출력: 비내림차순으로 정렬된 배열 S[1..n] 알고리즘 (교재와 약간 다름): [알고리즘 2.6] (P.61) void quicksort (index low, index high){ index pivotpoint; if (high > low) { pivotpoint = partition(low, high); quicksort(low, pivotpoint-1); quicksort(pivotpoint+1, high); }
빠른정렬 – 분할 알고리즘 (1/4) 문제: 빠른정렬을 하기 위해서 배열 S를 둘로 쪼갠다. 입력: (1) 첨자 low, high (2) 첨자 low에서 high까지의 부분배열 S[low,high] 전역적인 변수 출력: (1) S의 부분배열을 분할한 기준점 pivotpoint (2) 기준아이템 값에 의해 분할된 부분배열 S[low,high] (좌우로 이동 배치된 부분배열) 전역적인 배열에 반영 NOTE: In-place 알고리즘: (see the next page)
빠른정렬 – 분할 알고리즘 (2/4) index partition (index low, index high){ index i, j, pivotpoint; keytype pivotitem; pivotitem = S[low]; j = low; //j의 역할: pivotitem 보다 작은 아이템의 위치 기억 for(i = low + 1; i <= high; i++) if (S[i] < pivotitem) { j++; exchange S[i] and S[j]; } pivotpoint = j; //j의 역할: for루프가 끝난 후 pivotitem이 있을 위치 기억 exchange S[low] and S[pivotpoint]; return pivotpoint;
빠른정렬 – 분할 알고리즘 (3/4) low=1, high=8 pivotitem = s[low] i j S[1] S[2] S[3] S[4] S[5] S[6] S[7] S[8] 비고 - 2 3 4 5 6 7 8 1 12 23 34 15 22 13 27 12 10 20 25 15 13 22 27 12 10 20 25 15 13 12 27 22 10 20 25 15 13 12 10 22 27 20 25 10 13 12 15 22 27 20 25 초기값 if-true for 종료 최종교환 pivotpoint
만약 S[i] >= pivotitem 이면 if 절이 false: i 값만 증가 빠른정렬 – 분할 알고리즘 (4/4) low j i high < pivotitem >= pivotitem to be investigated 만약 S[i] >= pivotitem 이면 if 절이 false: i 값만 증가 low j i high < pivotitem >= pivotitem to be investigated 만약 S[i] < pivotitem 이면 if 절이 true: j 증가 후, i 위치 값과 j 위치 값 교환 그 다음 i도 증가 low j high < pivotitem > pivotitem to be investigated i
빠른정렬 진행예 quicksort(1,8) quicksort(1,3) 4 quicksort(5,8) quicksort(1,0) 6 quicksort(7,8) 5 quicksort(2,2) 3 quicksort(4,3) quicksort(7,7) 8 quicksort(9,8) 2 7
빠른정렬 – 알고리즘 분석 (Worst Case) (1/4) [알고리즘 2.7]의 최악의 경우 시간복잡도 분석 단위연산: S[i]와 pivotitem과의 비교 입력크기: 부분배열이 가지고 있는 항목의 수, high - low + 1 (= n) 분석: 배열의 첫번째 항목만 제외하고 모든 항목을 한번씩 비교하므로, W(n) = n – 1이다. [주의 1] 여기서 n은 전체 배열 S의 크기로 고정되는 것이 아니라 partition 함수를 호출할 때의 부분배열 크기를 나타냄 [주의 2] T(n) = n – 1 이라고 표기해도 좋음. 하지만…
빠른정렬 – 알고리즘 분석 (Worst Case) (2/4) [알고리즘 2.6]의 최악의 경우 시간복잡도 분석 단위연산: partition(low,high)의 호출 결국 S[i]와 pivotitem과의 비교 입력크기: 배열이 S가 가지고 있는 전체 항목의 수, n 분석: 최악의 경우: 배열이 이미 비내림차순으로 정렬이 된 경우 왜 그럴까? S가 원래부터 비내림차순으로 정렬되어 있으면 첫번째(기준아이템) 항목보다 작은 항목은 없으므로, 크기가 0인 부분배열은 왼쪽에 오고, 크기가 n-1인 부분배열은 오른쪽에 오도록 계속 나누어진다. 즉, 분할의 효과가 거의 없다. 따라서, 점화식은 다음과 같다. 여기서, W(0) = 0이므로, 최종적으로 점화식은 다음과 같다. W(n) = W(n - 1) + n - 1, if n > 0 W(0) = 0 W(n) = n – 1 + W(0) + W(n - 1)
빠른정렬 – 알고리즘 분석 (Worst Case) (3/4) 이 점화식을 풀면, 다음과 같다.
빠른정렬 – 알고리즘 분석 (Average Case) (4/4)
빠른정렬 – 알고리즘 분석 (Average Case) (1/3)
빠른정렬 – 알고리즘 분석 (Average Case) (2/3) 분석(계속): 양변에 n을 곱하면, n대신 n - 1을 대입하면, (1)에서 (2)를 빼면, 간단히 정리하면, 여기서, 라 하면, 다음과 같은 점화식을 얻을 수 있다. 그러면, 다음 관계가 성립한다.
빠른정렬 – 알고리즘 분석 (Average Case) (3/3) 분석(계속): 따라서, 해는 다음과 같다. 여기에서 오른쪽 항은 임의의 n에 대해 항상 1보다 작은 값이므로 무시한다. 그런데, ln n = logen이고, 이므로, 해는 an 2 ln n이다. 따라서, A(n)은 다음과 같다.
[실습 4] 빠른 정렬 vs. 합병 정렬 빠른 정렬에 대한 [알고리즘 2.6, 2.7] 를 Java 프로그램으로 작성하고 이전에 작성한 합병 정렬과 속도를 비교해보자. SortMain2.java 를 분석하기 [note] java SortMain2 > out.txt 완성되지 않은 다음 두 함수를 작성한다. public static void quickSort(int low, int high) public static int partition(int low, int high) In-place 합병정렬과 빠른정렬의 수행 시간을 비교해보자. SortMain2 프로그램 자체를 여러 번 수행하여 두 알고리즘의 수행시간을 거듭 분석해보자. 어느 하나의 알고리즘이 다른 알고리즘보다 항상 더 빨리 수행되는가? 만약 그렇지 않다면 num의 크기를 더 늘려서 실험해보자. 만약 그렇다면 그 이유는 무엇일까 고민해보고 자신의 생각을 정리해서 작성하자. [Reference] http://en.wikipedia.org/wiki/Sorting_algorithm