정렬과 탐색(Sort & Search) - 2

퀵 정렬(Quick Sort): 랜덤화에 의한 정렬

정렬을 하려는 n개의 원소들로부터 랜덤 원소 p를 피벗(pivot)으로 선택

 

퀵 정렬은 피벗 p를 제외한 n - 1개의 원소들을 두 부분으로 분리:

- 왼쪽 부분에는 정렬된 순서에서 p보다 먼저 나오는 원소

- 오른쪽 부분에는 정렬된 순서에서 p보다 나중에 나오는 원소

 

피벗 p는 정렬이 끝난 순서에서 위치하여야 할 배열의 자리에 머무르게 된다.

분할된 후 한쪽 편에 있는 어떠한 원소도 마지막 정렬된 순서에서 다른 쪽으로 옮겨지지 않는다

-> 피벗의 양쪽으로 나뉘어져 있는 원소들은 서로 독립적으로 정렬 가능 (재귀 알고리즘 표현 가능)

 

quick_sort(item_type s[], int l, int h) {
    int p;
    
    if ((h - 1) > 0) {
    	p = partition(s, l, h);
        quick_sort(s, l, p - 1);
        quick_sort(s, p + 1, h);
    }
}

int partition(item_type s[], int l, int h) {
    int i, p, firsthigh;
    
    p = h;
    firsthigh = l;
    for (i = l; i < h; i++) 
    	if (s[i] < s[p]) {
                swap(&s[i], &s[firsthigh]);
                firsthigh++;
        }
    swap(&s[p], &s[firsthigh]);
    return firsthigh;
}

분할 단계에서 n번의 원소 swap하므로, 선형 시간이 걸림

전체 퀵 정렬의 시간 복잡도는 n개의 원소의 중첩 반복된 부분 구간에 대해 재귀 트리 형성

각 부분배열의 원소들을 처리하는 데 선형 시간이 걸림, h가 재귀 트리의 높이라면 O(n * h)

 

각 분할에서 피벗의 위치에 따라 높이가  달라진다

운이 좋아서 매번 중앙값이 피벗이 된다면 부분문제들은 항상 이전 레벨의 절반 크기가 된다.

하나가 남을 때까지 n을 반으로 나누는 횟수가 트리의 높이 : log2n --> 최선의 경우

 

피벗의 원소가 항상 불균형하게 배열의 원소를 나눈다. 피벗 원소가 부분배열에서 항상 가장 크거나 가장 작은 원소일 거다.

이러한 원소를 피벗으로 하면 원소들은 나누어지지 않고 크기가 n - 1인 하나의 부분 문제만 남는다.

트리의 높이가 n - 1이 되므로 Θ(n^2)이 된다.

 

퀵 정렬의 최악의 경우는 힙 정렬이나 합병 정렬보다도 나쁘다.

 

퀵 정렬의 기대 시간

퀵 정렬의 기대 성능은 각 단계에서 랜덤하게 선택하는 피벗 원소에 의해 분할된 트리의 높이에 좌우된다.

정렬된 배열의 중간 근처에 매번 피벗 원소가 있다면, 분할이 잘되고 합병 정렬과 같은 성능을 얻게 된다. O(nlogn)

 

중앙값이 선택될 확률은 1/n으로 매우 적다.

정렬된 키의 공간에서 중앙 절반 부분에 존재하는 경우 충분히 좋은(good enough) 피벗이이라고 한다면 충분히 좋은 피벗 원소가

선택될 확률은 1/2이다.

 

평균적으로, 랜덤 퀵 정렬 분할 트리의 높이는 매우 좋다

운이 없는 경우 랜덤 선택한 원소가 항상 최대값이거나 최소값이면, 퀵 정렬은 삽입정렬 O(n^2)이 되지만 가능성은 매우 적다.

 

퀵 정렬은 정말 빠를까?

Θ(nlogn)과 Θ(n^2)에는 명확한 점근적 차이가 있다.

합병 정렬, 퀵 정렬, 힙 정렬이 선택, 삽입 정렬보다 빠르지만 O(nlogn) 사이에서 뭐가 더 빠른지 어떻게 알까?

RAM-모델과 O표기로는 차이를 알아낼 만큼 정교한 도구는 아니다.

 

퀵 정렬의 구현이 잘 되었을 때, 힙 정렬이나 합병 정렬보다는 2~3배 빠르다.

그 이유는 가장 내부의 반복문이 더 간단하기 때문이다.

 

이진 탐색(Binary Search)과 이와 관련된 알고리즘

이진 탐색은 정렬된 원소들의 배열 S를 탐색하는 데 있어서 빠른 알고리즘

키 q를 탐색하기 위해서 먼저 q와 S[n/2]를 비교한다.

q가 S[n/2] 앞에 나타나면 q는 S의 전반부에 있고 뒤에 있으면 후반부에 있다.

 

적절히 절반에 대해 재귀적으로 이 과정을 반복하면, 총 logn의 비교로 그 키의 위치를 찾을 수 있다.

int binary_search(item_type s[], item_type key, int low, int high) {
    int middle;
    
    if (low > high) return -1;
    
    middle = (low + high) / 2;
    
    if (s[middle] == key) return middle;
    
    if (s[middle] > key) return binary_searh(s[], key, low, middle - 1);
    else return binary_search(s[], key, middle + 1, high);

 

분할 정복(Divide and Conquer)

문제를 해결하는 가장 강력한 기법 중의 하나는 문제의 크기를 더 작게 나누어서 더 쉽게 해결할 수 있는 작은 문제로 만드는 것이다.

더 작아진 같은 유형의 문제 사례로 나누어질 때 재귀 알고리즘은 명백

 

동적 계획법도 문제를 더 작은 크기로 나누는 것에 기반을 둔다.

문제로부터 하나의 원소를 제거하고, 더 작아진 문제를 해결하고, 해결한 문제에 다시 제거한 원소를 추가하여 적당한 방법으로 해를 구한다.

 

분할 정복 알고리즘 설계법은 문제를 절반으로 나누고, 각각을 해결한 다음 이 두 결과를 합하여 전체 문제의 해를 만들어낸다.

두 개의 더 작은 부분문제로 나누고, 각각을 재귀적으로 해결한 다음, 두 개의 부분 해를 합하여 전체문제의 하나의 해로 만들어 낸다.

 

점화 관계(Recurrence Relation: 점화식, 재귀 관계, 재귀식, 점화 관계)

많은 분할 정복 알고리즘들의 시간 복잡도는 점화 관계로 자연스럽게 만들어진다.

점화식이란 자신의 용어로 자신이 정의되는 방정식이다.

 

분할 정복 점화 관계

분할 정복 알고리즘은 주어진 문제를 크기가 n/b이 되는 몇 개의 작은 조각(a)으로 나누는 경향이 있다.

이러한 부분 문제들로 하나의 완전한 결과로 합병하는데 f(n) 시간을 사용한다.

T(n)은 크기까 n인 문제를 해결하는 알고리즘이 사용하는 최악의 경우

 

정렬 - 같은 크기의 둘로 나눈다 -> 2T(n/2), 합병하는 데 선형 시간 -> O(n)  T(n) = 2T(n/2) + O(n) => T(n) = O(nlogn)

이진 탐색 - 상수시간에 문제의 크기를 절반으로 줄인다 -> O(n)  T(n) = T(n/2) + O(1) => T(n) = O(logn)

 

마스터 정리(Master Theorem)