[알고리즘] - 합병 정렬(Merge sort) #7

안녕하세요 고급 정렬 알고리즘 두 번째이자 마지막 시간입니다!

힙 정렬이 하나 더 있기는 하지만 별도의 자료구조가 필요하기 때문에 추후에 다루도록 하겠습니다.

그럼 빠르게 본론으로 들어가보겠습니다!

합병 정렬(Merge sort) - 안정 정렬(Stable sort)

합병 정렬은 데이터를 이분할 하는 작업을 반복하여 크기가 1인 데이터까지 분할하고, 

이 데이터들을 정렬해 나가며 최종적으로 완전 정렬하는 알고리즘입니다.

즉, 분할 정복 기법을 이용한 정렬 방법입니다.

따라서 합병 정렬은 분할, 정복(정렬) 이 두 단계로 이루어져 있습니다.

그림과 함께 조금 더 자세하게 설명해 드리도록 하겠습니다.

- 분할 단계

맨 처음 정렬해야 하는 데이터(7-3-2-1-5-4-6) 가 있습니다.

우선, 주어진 데이터의 인덱스를 0(start)~6(end)번이라고 생각해 보겠습니다.

이를 이분할 하기 위해서 중간점(mid)를 계산해야 하며 mid 는 다음과 같이 계산됩니다.

mid = (start + end) / 2

그렇게 되면 전반부 구간은 start~mid, 후반부 구간은 mid+1~end로 정할 수 있습니다.

이러한 구간 정보를 아래와 같이 분할 함수의 인자로 넘겨주는 작업을 반복(재귀)적으로 수행합니다.

분할(data, start, end){

mid = (start+end) / 2;

분할(data, start, mid);

분할(data, mid+1, end);

}

그렇게 되면 주어진 데이터는 최종적으로 크기가 1인 데이터 까지 분할됩니다.

- 정복(정렬) 단계

정복 단계에서는 분할된 구간을 정렬해 나가면서 부분 문제를 해결합니다.

즉, 분할 이후에 정복 과정을 거치게 되는 것이죠. 간략하게 표현하자면 다음과 같습니다.

분할(data, start, end){

mid = (start+end) / 2;

분할(data, start, mid); //부분 문제 해결로 전반부 정렬 완료

분할(data, mid+1, end); //부분 문제 해결로 후반부 정렬 완료

정복(data, start, mid, end); //전반부와 후반부를 비교하며 정렬

}

이제 정복함수의 간략적인 구성에 대해서 알아보도록 하겠습니다.

정복 함수는 크게 두 단계로 이루어져 있는데, 바로 임시 배열을 채우는 과정과 원래 배열에 임시 배열 값을 복사하는 과정입니다.

1) 전반부와 후반부 데이터를 비교하며 임시 배열 채우기

오름차순으로 정렬한다면, 전반부와 후반부의 데이터 중 작은 값을 비교해가며 임시 배열을 채웁니다.

이 과정을 전반부 혹은 후반부의 데이터가 빌 때 까지 진행하고, 이후 남은 데이터를 일괄적으로 채워주면 됩니다.

2) 임시 배열 값을 원래 배열에 복사하기

임시 배열에 정렬된 데이터를 저장했기 때문에 원래 배열에 복사해줍니다!

소스 코드

#include <cstdio>
int temp[7]; //정렬을 위한 임시 배열
//병합 함수 정의
void merge(int* a, int start,int mid, int end) {
    int firstPart = start;
    int lastPart = mid + 1;
    int savePoint = start;
 
    //전반부와 후반부를 비교하며 임시배열에 복사
    while ((firstPart <= mid) && (lastPart <=end)) {
        if (a[firstPart] <= a[lastPart])
            temp[savePoint++] = a[firstPart++];
        else
            temp[savePoint++] = a[lastPart++];
    }
 
    //전반부의 값이 남아 있다면
    while (firstPart <= mid)
        temp[savePoint++] = a[firstPart++];
 
    //후반부의 값이 남아 있다면
    while (lastPart <= end) 
        temp[savePoint++] = a[lastPart++];
 
    //임시 배열의 값을 원래 배열에 복사
    for (int i = start; i <= end; i++)
        a[i] = temp[i];
}
//분할 함수 정의
void partion(int * a, int start, int end) {
    int mid;
    if (start < end) {
        mid = (start + end) / 2;
        partion(a, start, mid); //전반부 - 분할 과정
        partion(a, mid + 1, end); //후반부 - 분할 과정
        merge(a, start, mid, end); //병합 - 정복 과정
    }
}
int main() {
    int a[7] = { 7,3,2,1,5,4,6 };
    partion(a,0, 6);
    for (int i = 0; i < 7; i++)
        printf("%d ", a[i]);
    return 0;
}

* 소스코드 라인별 설명은 주석으로 대체하겠습니다! *

시간 복잡도

합병 정렬의 경우에는 퀵 정렬과 달리, 항상  을 보장합니다.

그 이유는 매번 이분할을 하기 때문에 분할된 구간의 크기가 항상 일정하게 형성됩니다.

따라서 위 그림처럼 크기가 N인 데이터를 이분할 했을 경우에는 의 분할이 존재하게 되고,

이 각 분할에 대해서 N번의 비교가 이루어지기 때문에 항상  을 보장합니다.

이러한 특성 때문에 합병 정렬은 안정적인 성능을 보장하는 정렬 방법으로 알려져 있습니다.

다만 합병 정렬의 경우에는 소스 코드에서 볼 수 있듯이, 정렬하기 위한 추가적인 공간이 필요하다는 특징을 가지고 있습니다.

이번 포스팅에서 준비한 내용은 여기까지 입니다!

이제 드디어 정렬이 끝났습니다. 

다음 포스팅 부터는 본격적으로 그래프 관련 알고리즘에 대해서 알아보도록 하겠습니다.

그래프 관련 알고리즘들은 코딩테스트에서도 많이 출제되는 부분이니 더 힘내서 공부해주시기 바라겠습니다!