O(n log n) 인 정렬 알고리즘 (병합 정렬, 힙정렬, 퀵정렬)

O(n log n)인 정렬 알고리즘들

이 알고리즘은 최선으로나 평균적으로나 O(n log n)의 성능을 나타낸다. 

최악의 상황에서도 병합정렬이나 힙정렬은 O( n log n)을 유지하는 반면 순수한 퀵 정렬은 오히려 O(n^2)로 뒤진다. 그래서 실제로는 퀵 정렬을 조금 개량해서 최악의 경우가 발생하지 않도록 코드를 짠다.

병합 정렬 (Merge Sort)

대표적인 분할정복(Divide and Conquer) 알고리즘.

분할정복이란 말 그대로 문제를 분할 한 다음, 분할한 문제들 (sub-program)을 해결하고, 그 결과를 합쳐서 원래의 문제를 해결하는 것을 말한다.

마찬가지로 합병 정렬은 원소의 개수가 1 또는 0이 될 때 까지 두 부분으로 쪼개고 그 결과들을 크기를 비교하며 정렬하는 방식으로 병합해나간다.

개발자는 폰 노이만으로, 컴퓨터 공학을 전공하다보면 다양한 수업에서 종종 듣게되는 위인인데, 그의 천재성을 엿볼 수 있는 알고리즘이다.

성능은 퀵정렬보다 전반적으로 뒤떨어지고, 데이터 크기만한 메모리가 더 필요하지만, 최대의 장점은 데이터의 상태에 별 영향을 받지 않는다는 점이다.

정렬되어있는 두 배열을 더할 때 이 알고리즘을 사용하면 가장 빠르게 정렬된 상태로 합칠 수 있다.

아래는 C언어를 사용한 병합 정렬 예시이다.

첫 번째 줄에 정렬해야하는 원소의 갯수를, 두 번째 줄에 정렬해야할 원소들을 입력한다.

#include <stdio.h>
 
#define MAX 5005
 
int d[MAX];
int temp[MAX];
 
void MergeSort(int L, int R) {
    if (L >= R) return;
 
    int M = (L + R) / 2;
 
    // Divide
 
    MergeSort(L, M);
    MergeSort(M + 1, R);
 
    // Conquer
    
    for (int i = L, l = L, r = M + 1;
        l != M + 1 || r != R + 1;
        i++) {
 
        if ((r != R + 1 && l <= M && d[l] < d[r]) || r == R + 1) {
            temp[i] = d[l++];
        } else {
            temp[i] = d[r++];
        }
    }
 
    for (int i = L; i <= R; i++) {
        d[i] = temp[i];
    }
}
 
int main() {
    int n;
 
    scanf("%d", &n);
 
    for (int i = 0; i < n; i++)
        scanf("%d", &d[i]);
 
    MergeSort(0, n - 1);
 
    for (int i = 0; i < n; i++)
        printf("%d ", d[i]);
}

힙정렬 (Heap Sort)

힙 정렬을 설명한 동영상. 한번쯤은 보길 바란다.

힙정렬을 알기 위해선 먼저 힙이 무엇인지 알아야 한다. 

여기서 힙은 힙트리로, 여러개의 값 들 중 가장 크거나 작은 값을 빠르게 찾기 위해 만든 이진 트리이다. 짧게 힙이라고 부른다.

힙은 항상 완전 이진 트리의 형태를 띈다. 부모의 값은 항상 자식들의 값보다 크거나 (Max Heap) 작아야 (Min Heap) 한다는 규칙이 있다. 따라서 루트(뿌리) 노드에는 항상 데이터들 중 가장 큰 값 혹은 작은 값이 저장되어 있다.

힙 정렬의 방법은 아래와 같다.

1. 배열의 원소들을 전부 힙에 삽입
2. 가장 부모노드에 있는 값은 최댓값 혹은 최솟값이므로 루트를 출력하고 힙에서 제거
3. 힙이 빌 때 까지 2의 과정을 반복

힙정렬은 추가적인 메모리를 전혀 필요로하지 않는다는 점과 최악의 경우에도 항상 O(n log n) 의 성능을 발휘한다는 장점이 있다.

아래는 힙정렬을 C언어로 구현한 코드이다. 

#include <stdio.h>
#define SWAP(a,b)  {int t; t = a; a=b; b=t;}//a와 b를 교환
#define LCHILD(me)   (2*me +1)
#define RCHILD(me)  (LCHILD(me)+1)
#define PARENT(me)  ((me-1)/2)
 
void ViewArr(int *arr, int n);
void HeapSort(int *base, size_t n);
int main(void)
{
    int arr[10] = { 9,4,3,10,5,8,7,6,2,1 };   
    ViewArr(arr, 10);
    HeapSort(arr, 10);
    ViewArr(arr, 10);
    return 0;
}
void HeapSort(int *base, size_t n)
{    
    for (size_t i = 1; i<n; i++)
    { 
        int j = i;
        while (j>0)//루트가 아니면 반복
        {                    
            int pa = PARENT(j);//부모 인덱스를 구하기                 
            if (base[j]< base[pa]) //부모보다 크면
            {
                SWAP(base[j], base[pa]);//부모와 교환                
                ViewArr(base, n);
                j = pa;
            }            
            else
            {
                break;
            }
        }
    }
    SWAP(base[0], base[n - 1]);//루트와 마지막 자손 교환    
    ViewArr(base, n);
    n--;
    size_t me;
    size_t lc;
    size_t rc;
    while (n>1)//반복: n이 1보다 크면 
    {
        me = 0;
        while (1)
        {
            lc = LCHILD(me);
            rc = RCHILD(me);
            if (lc >= n)//자식이 없음
            {
                break;
            }
            if (rc == n)//왼쪽 자식만 있음
            {
                if (base[me]< base[lc])
                {
                    SWAP(base[me], base[lc]);                    
                    ViewArr(base, n);
                }
                break;
            }
            int bc = lc;
            if (base[lc]< base[rc])
            {
                bc = rc;
            }
            if (base[bc]> base[me])
            {                
                SWAP(base[bc], base[me]);                
                ViewArr(base, n);
                me = bc;
            }
            else
            {
                break;
            }
        }
        SWAP(base[0], base[n - 1]);//루트와 마지막 자손 교환        
        ViewArr(base, n);
        n--;
    }
}
void ViewArr(int *arr, int n)
{
    int i = 0;
    for (i = 0; i<n; i++)
    {
        printf("%2d ", arr[i]);
    }
    printf("\n");
}

퀵 정렬 (Quick Sort)

퀵이라는 이름에서 알 수 있듯이 평균적인 상황에서 최고의 성능을 보인다.

퀵 정렬을 재미있게 표현한 영상이다ㅋㅋㅋㅋ 

퀵정렬은 배열에 있는 수 중 사용자가 지정한 규칙대로 임의의 pivot을 잡고, 해당 pivot을 기준으로 작거나 같은 수를 왼쪽 파티션, 큰 수를 오른쪽 파티션으로 보낸다. 다시 왼쪽 파티션 구간에 한하여 pivot을 잡고 파티션을 나누고 오른쪽 파티션 구간에서도 pivot을 잡고 파티션을 나누는 과정을 반복하여 정렬시킨다.

이 알고리즘의 핵심은 pivot을 잡는 것인데, pivot을 해당 구간의 중앙값으로 잘 설정하면 시간복잡도 O(n log n)에 수행할 수 있지만, 만약 매 케이스마다 구간의 최댓값이나 최솟값으로 나눠버리면 O(n^2)의 수행시간을 갖게 된다.

현존하는 컴퓨터 아키텍처 상에서 비교연산자를 사용하여 구현된 정렬 알고리즘 중 가장 고성능인 알고리즘이다. 단, 데이터에 접근하는 시간이 오래 걸리는 외부 기억장소(하드디스크 등)에서 직접 정렬을 수행할 경우에는 병합 정렬이 더 빠른 것으로 알려져 있다. 

아래는 C언어로 구현한 샘플 코드다.

첫 줄에는 정렬할 원소의 갯수를, 둘째 줄에는 정렬할 원소들을 입력한다. 

#include <stdio.h>
 
void quickSort(int *arr, int left, int right) {
    int pivot, left_temp, right_temp;
    left_temp = left;
    right_temp = right;
    pivot = arr[left];
    while (left < right) {
        while (arr[right] >= pivot && (left < right)) {
            right--;
        }
        if (left != right) {
            arr[left] = arr[right];
        }
        while (arr[left] <= pivot && (left < right)) {
            left++;
        }
        if (left != right) {
            arr[right] = arr[left];
            right--;
        }
    }
    arr[left] = pivot;
    pivot = left;
    left = left_temp;
    right = right_temp;
    if (left < pivot) quickSort(arr, left, pivot - 1);
    if (right > pivot) quickSort(arr, pivot + 1, right);
}
int N;
int arr[100010];
int main() {
    scanf("%d", &N);
    for (int i = 0; i < N; i++) {
        scanf("%d", &arr[i]);
    }
    quickSort(arr, 0, N - 1);
    for (int i = 0; i < N; i++) {
        printf("%d ", arr[i]);
    }
}