알고리즘 합병(merge) 정렬 C언어

▶합병 정렬

각 단계에서 입력을 반으로 나눠 재귀 호출해 다시 합치면서 정렬

평균 성능 시간 복잡도 : O(nlogn)

최악 성능 시간 복잡도 : O(nlogn)

최선 성능 시간 복잡도 : O(nlogn)

 

▶소스코드

#define SIZE 10
int temp[SIZE];

void Merge(int arr[], int left, int mid, int right)
{
    int L = left;
    int R = mid + 1;
    int n = left;

    while (L <= mid && R <= right) {
        if (arr[L] <= arr[R]) {
            temp[n++] = arr[L++];
        }
        else {
            temp[n++] = arr[R++];
        }
    }

    if (L > mid) {
        for (int i = R; i <= right; i++) {
            temp[n++] = arr[i];
        }
    }
    else {
        for (int i = L; i <= mid; i++) {
            temp[n++] = arr[i];
        }
    }

    for (int i = left; i <= right; i++) {
        arr[i] = temp[i];
    }
}

void MergeSort(int arr[], int left, int right)
{
    if (left >= right) return;
    int mid = (left + right) / 2;
    MergeSort(arr, left, mid);
    MergeSort(arr, mid + 1, right);
    Merge(arr, left, mid, right);
}

위 소스는 오름차순 정렬이다.

 

▶해석

재귀를 이용하여 반으로 나눈 값들을 정렬할 때 임시로 저장하는 배열을 선언해준다.

#define SIZE 10
int temp[SIZE];

 

함수가 호출되는 순서에 맞게 MergeSort함수부터 설명하겠다.

 

배열 자릿수를 left에서 right까지 범위로 잡을 것이다. 그러니 left가 right와 같거나 크면 종료한다.

void MergeSort(int arr[], int left, int right)
{
    if (left >= right) return;

 

중앙 mid를 기준으로 left에서 mid까지 와 mid+1에서 right까지 이렇게 반으로 나눠 재귀 호출한다.

MergeSort(arr, left, mid);
MergeSort(arr, mid + 1, right);

 

앞 재귀 호출로 인해 Merge함수가 처음으로 호출될 때는 left값과 right값이 더 이상 반으로 나눌 수 없을 때이다. 이때부터 정렬을 시작한다.

MergeSort함수의 재귀 호출이 끝나면서 Merge함수가 호출될 때마다 left~right 범위가 점점 커져 마지막에 호출될 때는 처음 MergeSort함수가 main에서 호출됐을 때 이므로 정렬할 배열 전체를 반으로 나눈 것을 Merge함수에서 호출한다.

Merge(arr, left, mid, right);

 

이제부터 정렬이 시작된다.

정렬할 때 값을 조작하여 사용하기 위해 L, R에 값을 대입하였다.

L : mid를 기준으로 나눈 왼쪽, 오른쪽 값들 중 왼쪽을 담당하며 왼쪽 값의 가장 작은 자릿수(left)

R : mid를 기준으로 나눈 왼쪽, 오른쪽 값들 중 오른쪽을 담당하며 오른쪽 값의 가장 작은 자릿수(mid+1)

n : 임시로 저장할 temp배열의 자릿수. 꼭 left가 아니어도 됨(코드를 조정하여 바꾸기 가능)

void Merge(int arr[], int left, int mid, int right)
{
    int L = left;
    int R = mid + 1;
    int n = left;

 

왼쪽을 담당하는 L의 끝은 mid이고, 오른쪽을 담당하는 R의 끝은 right이다.

작은 자릿수(L : left , R : mid+1)부터 L++, R++하므로 각자 끝자리를 하나라도 넘으면 종료한다.

while (L <= mid && R <= right)

 

양쪽 구역의 가장 작은 자릿수부터 비교하여 arr[L]보다 arr [R] 값이 더 크면

오름차순이므로 작은 arr[L]부터 temp배열에 대입한다.

대입할 때 n값은 다음 공간을 가리키기 위해 n++하고, L도 temp에 대입했으므로 다음 값을 가리키기 위해 L++한다.

반대로 arr[R]값이 더 작으면 temp배열에 arr [R]을 대입한다.

if (arr[L] <= arr[R]) {
    temp[n++] = arr[L++];
}
else {
    temp[n++] = arr[R++];
}

이렇게 작은 값부터 temp배열에 담으면 자연스레 정렬이 이루어지고, L 또는 R이 +1씩 돼서 while조건에 하나라도 넘어가면 종료된다.

 

한쪽만 while조건에 맞지 않으면 다른 한쪽은 아직 temp배열에 다 대입하지 못한 것이다.

예를 들어 L이 +1씩 반복하여 while문 조건에서 mid보다 커지면 R은 right까지 가지 못한 채 while문이 종료된다.

R부터 right까지 temp배열에 넣기 위해 if문으로 L이 mid보다 커지면 for문으로 R에서 right까지 temp에 대입하였다.

마찬가지로 R이 right를 넘으면 else문으로 L에서 mid까지 temp에 대입한다.

if (L > mid) {
    for (int i = R; i <= right; i++) {
        temp[n++] = arr[i];
    }
}
else {
    for (int i = L; i <= mid; i++) {
        temp[n++] = arr[i];
    }
}

 

이제 temp배열에 left부터 right까지 정렬되었으므로 원래 값이 들어가 있던 arr배열에 복사한다.

for (int i = left; i <= right; i++) {
    arr[i] = temp[i];
}

 

▶예시

#include <stdio.h>
#define SIZE 10
int temp[SIZE];

void Merge(int arr[], int left, int mid, int right)
{
    int L = left;
    int R = mid + 1;
    int n = left;

    while (L <= mid && R <= right)
    {
        if (arr[L] <= arr[R]) {
            temp[n++] = arr[L++];
        }
        else {
            temp[n++] = arr[R++];
        }
    }

    if (L > mid) {
        for (int i = R; i <= right; i++) {
            temp[n++] = arr[i];
        }
    }
    else {
        for (int i = L; i <= mid; i++) {
            temp[n++] = arr[i];
        }
    }

    for (int i = left; i <= right; i++) {
        arr[i] = temp[i];
    }
}

void MergeSort(int arr[], int left, int right)
{
    if (left >= right) return;
    int mid = (left + right) / 2;
    MergeSort(arr, left, mid);
    MergeSort(arr, mid + 1, right);
    Merge(arr, left, mid, right);
}

int main()
{
    int arr[10] = {5, 3, 7, 6, 1, 9, 0, 2, 8, 4};
    MergeSort(arr, 0, 9);
    for (int i = 0; i < 10; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

결과

0 1 2 3 4 5 6 7 8 9