[알고리즘] 7. Merge Sort, Quick Sort

1. Merge Sort와 Merge 알고리즘

Merge Sort는 주어진 배열을 가운데에서 쪼개어 두 개로 만든 뒤 이들을 각각 재귀 호출을 하여 정렬한다. 그 후 정렬된 두 배열을 Merge 알고리즘을 통하여 하나로 합쳐서 정렬된 배열을 얻는다.

Merge 알고리즘: 배열 A, B를 병합하여 배열 C에 저장하고자 한다. A, B의 원소들을 가리키는 포인터가 각각 존재한다고 하면 처음에는 그 포인터가 $A[0], B[0]$ 에 존재한다. 배열 C에는 두 포인터가 가리키는 값 중 더 작은 값이 들어가게 되고, 그 값을 가리키던 포인터는 한칸 뒤로 이동하게 된다. 이 과정을 두 포인터가 모두 배열의 끝에 갈때까지 반복한다. 이 알고리즘 자체는 포인터가 이동하면서 n개의 원소를 이동시키므로 $O(n)$이 걸린다.

int sort(int a[], int n)
{
    if (n <= 1) return;
    int h;
    int b[n];
    h = n / 2;
    // copy a[] to b
    sort(b, h);
    sort(b+h, n-h);
    // Merge two halves in b to a
    return;
}

 

2. Merge Sort의 정당성 증명

1. 집합 조건을 깰 수 있는 코드는 없다.
2. $n = 1$인 경우: 할 일이 없다. (이미 정렬됨)
3. $n/2$ 일 때 sort() 함수가 성공한다고 가정하자. 즉, 재귀 호출이 끝난 후 새로 생성된 배열 c에 대하여 $c[0] < c[1] < ... < c[n/2 - 1]$ 이고, $c[n/2] < c[n/2 + 1] < ... < c[n-1]$ 이다. 
4. n일때는 merge 알고리즘의 정확성 (집합관계가 깨지지 않고, sorted 된 상태로 merge 됨) 에 의해 sort() 함수가 성공한다.
5. 시간복잡도: $T(n) = n + 2T(n/2) = n + 2(n/2 + 2(T(n/4)) = ... = O(nlogn)$

 

3. Quick Sort

Merge Sort는 $O$ notation 상으로는 가장 빠르지만 배열 할당할 때 메모리 소비가 커서 n이 커지면 잘 안쓰게 된다. Quick Sort는 추가 메모리를 할당하지 않는 것이 목적이다. 

1. 배열에서 어떤 값 하나를 pivot으로 설정한다.
2. 배열의 가장 앞과 가장 뒤 값을 가리키는 포인터를 각각 i, j라 하자. i와 j가 겹칠때까지 아래의 과정을 반복한다.
3. i가 가리키는 값이 피봇보다 작으면 i를 뒤로 옮겨서 피봇보다 커질때까지 옮기고, j가 가리키는 값이 피봇보다 크면 j를 앞으로 옮겨서 피봇보다 작아질때까지 옮긴다. 둘 다 멈춘 뒤 i가 j보다 작으면 i가 가리키는 값과 j가 가리키는 값을 교환한다.
4. pivot과 j가 가리키는 값을 교환한다.
5. 이제 처음부터 j가 가리키는 곳까지 / j가 가리키는 곳 다음부터 배열의 끝까지를 각각 재귀적으로 정렬한다.

int qsort(int a[], int n) {
    // if n <= 5 do selection sort
    int p = a[0];
    int i =1; int j = n-1;
    while (i < j) {
        while (a[i] < p) i++;
        while (a[j] > p) j-;
        if (i < j) swap(a[i], a[j]);
    }
    swap(a[0], a[j]);
    qsort(a, j); qsort(a+j+1, n-j-1);
    return;
}

 

4. Quick Sort의 정확성 증명

1. 집합 조건을 깰 수 있는 코드는 없다.
2. $n <= 1$인 경우: 할 일이 없다.
3. 함수 내의 재귀함수가 성공한다고 가정하자. 즉, 재귀 호출이 끝난 후 $a[0] < a[1] < ... < a[j-1]$ 이고, $a[j+1] < a[j+2] < ... < a[n-1]$이다.
4. 재귀 호출이 일어나기 전에 $a[j-1] < p == a[j] < a[j+1]$ 이 성립했다. 따라서, 함수가 끝났을 때 $a[0] < a[1] < ... < a[n-1]$ 이 성립하므로, qsort()

 

5. Quick Sort 시간 복잡도

Pivot이 뭐냐에 따라서 성능이 달라짐! 대부분 $O(nlogn)$으로 작동함.

• Worst Case : $T(n) = T(n-1) + n = ... = O(n^2)$
• Best Case (피봇이 중간일때): $T(n) = 2T(n/2) + n = ... = O(nlog n)$ 
• Average Case (배열의 모든 값이 피봇으로 선택될 확률이 동일하다고 가정): $T(n) = O(nlog n)$ 

성능 향상 시키는 Idea: 애초에 피봇을 중간값으로 잘 뽑으면 Worst Case의 시간 복잡도가 더 향상될 것이다. Pivot Selection 중 Approximate Median이 $O(nlogn)$ 으로 풀려서 Quick Sort도 $O(nlogn)$에 풀리게 된다.