정렬(sorting) - 병합정렬(Merge Sort), 힙정렬(Heap Sort), 계수정렬(Counting Sort)

병합정렬

병합정렬은 작게 분할한 뒤에 정렬한 후 합치는 방식이다. 좀 더 자세히 살펴보면 아래 그림과 같다.

병합정렬

아래는 병합정렬의 코드이다.

 

#include <stdio.h>
 
int number = 8;
int sorted[8]; //정렬 배열은 반드시 전역변수로
 
void merge(int a[], int m, int middle, int n) {
    int i, j;
    i = m; j = middle + 1;
    int k = m;
    //작은 순서대로 배열에 삽입
    while (i <= middle && j <= n) {
        if (a[i] <= a[j]) {
            sorted[k] = a[i];
            i++;
        }
        else {
            sorted[k] = a[j];
            j++;
        }
        k++;
    }
    //남은 데이터도 삽입
    if (i > middle) {
        for (int t = j; t <= n;t++) {
            sorted[k] = a[t];
            k++;
        }
    }
    else {
        for (int t = i; t <= n;t++) {
            sorted[k] = a[t];
            k++;
        }
    }
    //정렬된 배열을 삽입
    for (int t = m;t <= n;t++) {
        a[t] = sorted[t];
    }
}
 
void mergeSort(int a[], int m, int n) {
    //크기가 1보다 큰 경우
    if (m < n) {
        int middle = (m + n) / 2;
        mergeSort(a, m, middle);
        mergeSort(a, middle + 1, n);
        merge(a, m, middle, n);
    }
}
 
int main() {
    int array[8] = { 7,6,5,8,3,5,9,1 };
    mergeSort(array, 0, number - 1);
    
    //print sort
    for (int i = 0;i < 8;i++) {
        printf("%d ", array[i]);
    }
    return 0;
}

 

이러한 병합정렬은 추가적으로 배열의 크기만큼의 공간이 더 필요하여 메모리 활용이 비효율적이라는 단점이 있다. 하지만, 최악의 경우 시간복잡도가 O(N*N)이 되는 퀵정렬과 달리 어떠한 경우에도 시간복잡도가 O(N*logN)을 유지하기 때문에, 효율적인 정렬 알고리즘이라고 볼 수 있다.

시간 복잡도가 O(N*logN)이라는 것에 대해 살펴보면,

 

힙정렬

힙정렬은 힙 트리 구조를 이용하는 정렬 방법이다. 추가로, 힙정렬에서는 완전 이진 트리를 사용한다. 먼저 힙 트리 구조에는 최대힙과 최소힙이 있는데 둘의 차이는 아래 그림과 같다.

힙정렬을 수행하기 위해서 Heapify라는 힙 생성 알고리즘을 사용하는데, 이는 특정한 노드의 두 자식 중에 부모보다 큰 자식이 있을 때 더 큰 자식과 부모 자식의 위치를 바꾸는 알고리즘이다. 그림으로 나타내면 아래와 같다.

Heapify 알고리즘은 한 번 자식 노드로 내려갈 때마다 노드의 갯수가 2배씩 증가(완전이진트리니까)하므로 O(logN)이라는 시간 복잡도를 가지고 있다.

 

그럼 이제 힙정렬에 대해 알아보자.

먼저 배열의 형태로 저장된 트리 형태를 Heapify 알고리즘을 사용하여 힙구조로 만든다. (이때, 전체 트리를 힙 구조로 만드는 복잡도는 데이터의 갯수가 N개 이므로 O(N*logN)이다.)

그 후 루트에 있는 값을 가장 뒤의 노드와 바꾸고 힙 트리의 크기를 1씩 뺀다.

(힙트리 크기-1)의 노드를 기준으로 또 다시 Heapify를 수행하고 이전과 같은 과정을 전체 데이터 갯수만큼 반복하면 된다.

힙정렬은 힙 생성 알고리즘을 전체 데이터 갯수만큼 진행하는 것과 같으므로 힙정렬의 전체 시간 복잡도는 O(N*logN)이다.

이해하기 쉽게 그림으로 살펴보면 아래와 같다.

아래는 힙정렬에 대한 코드이다.

#include <stdio.h>
 
int number = 9;
heap[9] = { 7,6,5,8,1,3,2,9,4 };
 
int main() {
    // 전체 트리 구조를 최대 힙 구조로 바꿈
    for (int i = 1;i < number;i++) {
        int c = i;
        do{
            int root = (c - 1) / 2;
            if (heap[root] < heap[c]) {
                int temp = heap[root];
                heap[root] = heap[c];
                heap[c] = temp;
            }
            c = root;
        } while (c != 0);
    }
 
    // 크기를 줄여가며 반복적으로 힙을 구성
    for (int i = number - 1;i >= 0;i--) {
        int temp = heap[0];
        heap[0] = heap[i];
        heap[i] = temp;
        int root = 0;
        int c = 1;
        do {
            c = 2 * root + 1;
            // 자식 중에 더 큰 값을 찾기
            if (heap[c] < heap[c + 1] && c < i - 1)
                c++;
            //루트보다 자식이 더 크다면 교환
            if (heap[root] < heap[c] && c<i) {
                int temp = heap[root];
                heap[root] = heap[c];
                heap[c] = temp;
            }
            root = c;
        } while (c < i);
    }
 
    for (int i = 0;i < number;i++)
        printf("%d ", heap[i]);
    return 0;
}

 

힙정렬도 항상 O(N*logN)을 보장한다는 점에서 매우 빠른 정렬 알고리즘이다. 또한, 병합정렬과 달리 추가적인 배열이 필요하지 않아 메모리 측면에서 효율적이기도 하다.

 

계수정렬

계수정렬은 '범위 조건'이 있는 경우 빠른 알고리즘이다. 계수정렬은 간단하게 크기를 기준으로 갯수를 세는 것으로, 각 원소에 1번만 접근하기 때문에 O(N)이라는 빠른 속도를 가지고 있다.

좀 더 이해하기 쉽게 그림으로 살펴보면 아래와 같다.

아래는 계수정렬의 코드이다.

 

#include <stdio.h>
 
int main() {
    int array[] = { 1,3,2,4,3,2,4,5,1,2,3,2,3,4,5,1,1,3,2,4,3,1,5,2,3 };
    int count[6] = { 0, };
 
    for (int i = 0; i < 25;i++) {
        for (int j = 1;j <= 5;j++) {
            if (array[i] == j) {
                count[j]++;
                break;
            }
        }
    }
 
    //print sort
    for (int i = 1;i <= 5;i++) {
        for (int j = 0;j < count[i];j++) {
            printf("%d ", i);
        }
    }
    return 0;
}

이처럼 계수정렬은 모든 데이터 크기 범위가 메모리 상에서 표현이 가능하다면 O(N)이라는 빠른 속도로 정렬을 수행할 수 있게 된다.