[알고리즘] 정렬(2) - 병합 정렬, 퀵 정렬, 힙 정렬

반응형

 

앞에서는 시간 복잡도가 \(\Theta(n^2)\)인 정렬 알고리즘들을 알아봤다. 이번에는 \(\Theta(nlogn)\)인 알고리즘들을 알아보자.

병합 정렬(Merge Sort)

병합 정렬은 먼저 입력을 절반으로 나눈다. 이후 그 두 덩이를 각각 정렬한 뒤, 서로 합쳐서 정렬하는 방식이다. 나뉘어진 두 덩어리도 다시 반으로 나눈 뒤 정렬하고 병합하고, 또 그 나누어진 덩이를 나누는 과정을 반복한다. 즉, 정렬 과정을 재귀적으로 반복하는 방법이다.

 

3

2

4

1

우선 절반을 가른다.

3

2

4

1

각각을 또 절반으로 가른다.

3

2

4

1

왼쪽과 오른쪽에서 자른 덩어리를 합하며 정렬한다.

2

3

1

4

나머지 덩어리를 합하며 정렬한다.

1

2

3

4

정렬이 끝난 배열

1

2

3

4

 

C++로 구현한 병합정렬

void merge_sort(int* arr, int start = 0, int end = SIZE - 1) {
    int mid = (start + end) / 2;

    if (start == mid) {
        merge(arr, start, mid, end);
    }
    else {
        merge_sort(arr, start, mid);
        merge_sort(arr, mid + 1, end);
        merge(arr, start, mid, end);
    }
}

void merge(int* arr, int start, int mid, int end) {
    int tmp[SIZE] = {};
    int i = start, j = mid + 1, k = 0;

    while (i <= mid && j <= end) {
        if (arr[i] <= arr[j]) {
            tmp[k] = arr[i];
            k++;
            i++;
        }
        else {
            tmp[k] = arr[j];
            k++;
            j++;
        }
    }
    while (i <= mid) {
        tmp[k] = arr[i];
        k++;
        i++;
    }
    while (j <= end) {
        tmp[k] = arr[j];
        k++;
        j++;
    }
    
    for (i = start, k = 0; i <= end; i++, k++) {
        arr[i] = tmp[k];
    }
}

이전 시간에 구현했던 정렬들에 비해 코드가 길어졌다. 병합 정렬은 \(\Theta(nlogn)\)의 시간 복잡도를 가진다.

 

[+] 병합 정렬의 시간 복잡도

병합 정렬은 크기가 1이라면 상수 a만큼의 시간이 걸릴 것이다. 크기가 n이라면 n을 절반으로 나눈 뒤(\(n\over2\)), 병합을 n번 진행한다. 즉, \(T(n) = 2T({n\over2}) + cn\)(\(c\)는 상수)가 된다. 이를 정리하면 다음과 같다.

$$\begin{flalign}T(n)=\begin{cases}a & \mbox{if n} = 1\\\\2T({n\over2}) + cn & \mbox{if n} > 1\end{cases}&&\end{flalign}$$

 

이 식을 전개해보자.

 

$$\begin{flalign}T(n) &= 2T({n\over2})+cn \\&= 2^2T({n\over2^2})+2cn \\&= 2^3T({n\over2^3})+3cn \\&\vdots \\&= 2^kT({n\over2^k})+kcn &&\end{flalign}$$

 

\(n = 2^k\) 라고 한다면,

$$\begin{flalign}T(n) &= 2^kT({n\over2^k})+kcn \\&= nT(1) + kcn = an + cnlog_2n&&\end{flalign}$$

 

따라서, 병합 정렬의 시간 복잡도는 \(\Theta(nlogn)\)이 된다.

 

[+] 왜 \(n = 2^k\)로 가정할까?

\(n \le 2^k \le 2n\)을 만족하는 \(2^k\)이 하나 이상 존재한다.

\(T(2n) = O(2n) = O(n)\) 이므로

\(T(n) = T(2^k) = T(2n)\) 이 성립한다.

따라서, \(n\)을 \(2k\)로 가정해도 점근적 분석에 영향을 주지 않는다.

퀵 정렬(Merge Sort)

평균적으로 가장 좋은 성능을 가지는 정렬 알고리즘이다. 병합 정렬처럼 입력을 분할하는 것은 동일하나, 균등하게 분할하지는 않는다. 기준이 되는 원소를 하나 정해서 큰 원소는 오른쪽 작은 원소는 왼쪽으로 보낸 뒤, 이 과정을 정렬이 끝날 때 까지 재귀적으로 반복하는 방식이다. 평균적으로 \(\Theta(nlogn)\)의 성능을 보인다. 이름에서 알 수 있듯 같은 \(\Theta(nlogn)\)의 정렬 알고리즘 중 평균적인 상황에서 가장 빠른 성능을 보인다.

 

6

2

9

7

3

10

4

1

8

5

기준이 되는 원소를 하나 잡는다.

6

2

9

7

3

10

4

1

8

5

기준(4)를 중심으로 작은 원소는 왼쪽, 큰 원소는 오른쪽에 배치한다.

2

3

1

4

7

6

10

9

8

5

왼쪽에서 기준(2)을 정하고 재배치한다.

1

2

3

4

7

6

10

9

8

5

오른쪽에서 기준(7)을 정하고 재배치한다.

1

2

3

4

6

5

7

9

8

10

.

.

.

정렬이 끝난 배열

1

2

3

4

5

6

7

8

9

10

 

C++로 구현한 퀵 정렬

void quick_sort(int* arr, int start, int end) {
    if (start < end) {
        int q = partition(arr, start, end); // 기준을 하나 잡아서 분할
        quick_sort(arr, start, q - 1); // 왼쪽 부분 정렬
        quick_sort(arr, q + 1, end); // 오른쪽 부분 정렬
    }
}

int partition(int* arr, int start, int end) { // 맨 뒤의 원소를 기준으로 분할.
    int low = start - 1;
    int pivot = arr[end];

    for (int i = start; i < end; i++) {
        if (arr[i] < pivot) {
            low++;
            swap(arr[low], arr[i]);
        }
    }
    low++;
    swap(arr[low], arr[end]);
    return low;
}

위의 코드에서는 기준을 마지막 원소로 잡았다. 퀵 정렬의 시간 복잡도를 구해보자. 분할의 경우는 배열을 처음부터 끝까지 방문하게 되므로 \(\Theta(n)\)의 시간이 필요하다. 분할이 항상 절반씩 균등하게 이루어진다고 해보자. 그렇다면, 병합정렬과 동일하게 \(T(n) = 2T({n \over 2}) + \Theta(n)\)이 된다. 즉, 최선의 경우에는 \(\Theta(nlogn)\)이다. 최악의 경우는 분할이 한쪽에 몰리는 경우다. 즉, 선택한 값이 늘 최소이거나 최대일 경우이다. 이럴 경우에는 \(T(n) = T(n-1) + \Theta(n)\)이 되어 결국 최악의 경우에는 \(\Theta(n^2)\)이 된다.

 

[+] 평균적인 경우의 시간 복잡도

분할이 가능한 모든 경우의 수를 평균내면 평균적인 경우의 시간 복잡도를 구할 수 있다.

기준이 되는 원소를 중심으로 n개의 원소를 분할한다고 해보자. 기준이 되는 원소가 가장 작다면 왼쪽:오른쪽이 각각 0:n-1이 된다. 2번째로 작다면 1:n-2, 3번째는 2:n-3, ... 순으로 이어지게 된다. 다시 말해, a번째 크기의 원소라면 a-1:n-a 의 크기로 분할된다.

 

\(T(n) = T(a-1)+T(n-a)+\Theta(n)\)

 

a가 1부터 n까지의 모든 경우의 수를 구해서 n으로 나누어주면 평균적인 경우를 구할 수 있다.

 

$$\begin{flalign}T(n)&={1 \over n} \sum_{a=1}^n [T(a-1)+T(n-a)] + \Theta(n) \\&={2 \over n} \sum_{k=0}^{n-1} T(k) +\Theta(n) && \end{flalign}$$

 

\(T(n) \le cnlogn\)이 됨을 증명해보자.

충분히 큰 \(c\)와 \(2 \le k < n\)인 모든 \(k\)에 대해 \(T(k) \le cklogk\)가 성립한다고 가정하자.

 

$$\begin{flalign}T(n)&={2 \over n} \sum_{k=2}^{n-1} T(k) + \Theta(n) \\&\le {2 \over n} \sum_{k=2}^{n-1} cklogk + \Theta(n) \\&\le {2c \over n} ({1 \over 2}n^2logn-{1 \over 8}n^2) + \Theta(n) \\&=cnlogn - {cn \over 4} + \Theta(n) \\&\le cnlogn &&\end{flalign}$$

 

\(∴T(n) = \Theta(nlogn)\)

 

힙 정렬(Heap Sort)

자료구조인 힙을 사용한 정렬 방법이다. 최소힙(또는 최대힙)에 원소들을 삽입하고, 하나씩 차례대로 꺼내면 정렬된 원소들을 얻을 수 있다.

 

[참고] 우선순위 큐와 힙

[자료구조] 우선순위 큐와 힙

 

void heap_sort(int *arr) {
    Heap h; // 자료구조 - 힙 에서 만든 힙 클래스
    
    for (int i = 0; i < SIZE; i++) {
        h.insert(arr[i]);
    }
    
    for (int i = SIZE - 1; i >= 0; i--) {
        arr[i] = h.remove();
    }
}

Heap은 자료구조를 공부하며 만든 클래스이다. 힙에서는 삭제와 삽입 연산이 \(\Theta(logn)\)인 것을 알고 있다. 배열을 한번씩 둘러보는 연산은 \(\Theta(n)\)이므로 힙 정렬의 시간 복잡도는 \(\Theta(nlogn)\)이 됨을 알 수 있다.

 

 

[Reference]

문병로, 「쉽게 배우는 알고리즘」 (한빛 아카데미, 2018)

 

 

728x90