처음하시는 분들을 위한 C언어 기초강의 시즌2 - 39 [정렬 알고리즘(합병 정렬)]

제 39강) 정렬 알고리즘 - 합병 정렬

오늘은 정렬 알고리즘의 네번째 시간으로 "합병 정렬"에 대해서 알아봅니다.

기본적으로 합병 정렬은 배열에서 사용합니다.

(Merge Sort라고 불립니다.)

(합병 정렬 혹은 병합 정렬이라고 불립니다.)

 

합병 정렬이란

(사진 출처 : 위키 백과 - 합병 정렬)

합병 정렬은 배열을 계속 쪼개어 최소 단위인 2개일때 선행적으로 정렬을 한 뒤에 다시 합병하여 정렬, 합병하여 정렬을 반복하는 정렬방식입니다.

일단 배열을 원소의 크기가 최대 2개가 될 때까지 쪼갭니다.

이 쪼개지는 과정을 크게 "왼쪽 부분"과 "오른쪽 부분"으로 구분할 수 있습니다.

이렇게 9와 11은 왼쪽으로 2번 나뉘어진 부분이 되고 8은 왼쪽으로 한 번, 오른쪽으로 한 번 나뉘어진 부분이 되며, 2와 3은 오른쪽으로 한 번 나뉘어진 부분이 됩니다.

 

원소 배열이 2개가 되었다면 그 2개를 크기 분류에 맞게 비교하여 정렬합니다.

만약 원소 배열이 1개라고 한다면 비교 정렬할 필요가 없습니다.

 

이렇게 정렬되어 분할된 배열을 바로 윗단계 크기로 병합 시킵니다.

시키기 전에 두 배열간의 원소 크기비교를 해가면서 정렬하며 병합시킵니다.

 

이렇게 되어 합병 정렬의 비교 횟수는 T(n) = n * logn 이 됩니다.

그리하여 시간 복잡도는 O(nlogn)이 됩니다.

상당히 빠르죠.

그래서 실제적으로 사용하는 알고리즘중의 하나입니다.

 

정렬명	시간 복잡도	메모리 사용
합병 정렬	O(nlogn)	최대 2n

 

메모리의 경우에는 매번 쪼개어 합병되기 전에 임시의 배열을 생성하여 정렬 후 합병하기 때문에 정렬할 배열의 길이만큼 더 먹습니다.

 

위의 영상은 합병 정렬을 시각적인 춤으로 표현한 좋은 영상입니다.

꼭 보세요.

 

합병 정렬 구현

이제 합병 정렬을 구현하여 봅시다.

합병 정렬은 기본적으로 "재귀" 방식을 사용합니다.

#include <stdio.h>
#include <stdlib.h>
 
void printArr(int* arr, int length)
{
    printf("arr: ");
    for (int i = 0; i < length; i++)
    {
        printf("%d", arr[i]);
        if (i + 1 < length)
            printf(", ");
        else
            printf("\n");
    }
    printf("\n");
}
 
void mergeSort(int* arr, int start, int end)
{
    int mid = (end + start) / 2;         // 반으로 가르기 위해서 절반 위치를 계산합니다.
    if (end - start > 1)              // 만약 원소의 개수가 1보다 크면
    {
        mergeSort(arr, start, mid);      // 왼쪽을 한 번더 쪼갭니다.
        mergeSort(arr, mid + 1, end);    // 오른쪽을 한 번더 쪼갭니다.
    }
    
    int left = start, right;             // 왼쪽 시작점과 오른쪽 시작점 변수
    if (start == end)                    // start와 end가 같다면(원소가 1개라면)
        return;                          // 1개뿐이니 정렬할 필요 없음
    else
        right = mid + 1;                 // 1개 이상이니 오른쪽 배열의 시작점을 중간 + 1로 설정
    int idx = 0;                         // while 문 탈출에 쓰일 원소를 샐 변수
    int length = end - start + 1;        // 현재 정렬하려는 배열의 길이
    int* tmpArr = (int*)calloc(length, sizeof(int));    // 임시적으로 정렬한 배열의 원소를 저장할 배열
    while (idx != length)                // 현재 원소 카운트가 정렬할 배열의 개수보다 적으면 계속 반복
    {
        // 왼쪽 배열의 현재 위치가 중간지점보다 크거나, 오른쪽 배열 인덱스 범위를 침범한다면
        if (left > mid || left > right)            
            tmpArr[idx++] = arr[right++];       // 왼쪽배열의 끝에 도달한것이므로 오른쪽 배열로 전부 채운다.
        else if (right > end)                // 오른쪽 배열이 끝 범위를 벗어난다면
            tmpArr[idx++] = arr[left++];        // 오른쪽 배열의 끝에 도달한것이므로 왼쪽 배열로 전부 채운다.
        else // 일반적으로
        {
            if (arr[left] < arr[right])      // 현재 오른쪽 배열요소가 왼쪽 배열요소보다 크면
                tmpArr[idx++] = arr[left++];    // 왼쪽 배열 요소를 저장하고 현재 왼쪽배열의 인덱스와 임시저장배열의 인덱스를 1증가
            else                                // 현재 왼쪽 배열요소가 오른쪽 배열요소보다 크면
                tmpArr[idx++] = arr[right++];   // 오른쪽 배열 요소를 저장하고 현재 오른쪽배열의 인덱스와 임시저장배열의 인덱스를 1증가
        }
    }
 
    // 임시로 저장한 배열의 원소를 현재 배열에 그대로 저장
    for (int i = 0; i < length; i++)
        arr[start + i] = tmpArr[i];
    
    // 임시 배열 메모리 해제
    free(tmpArr);
}
 
int main(void)
{
    int arr[] = { 9, 11, 8, 2, 3 };
    int length = sizeof(arr) / sizeof(int);
 
    printf("[정렬 전 배열]\n");
    printArr(arr, length);
 
    mergeSort(arr, 0, length - 1);
    
    printf("[정렬 후 배열]\n");
    printArr(arr, length);
 
    return 0;
}

이해가 잘 안되시다면 직접 그림을 그려가면서 생각해보세요.

그럼 바로 이해가 됩니다.

 

이번시간에는 성능이 좋은 "합병 정렬"을 보았습니다.

이 알고리즘은 실제적으로도 사용되는 정렬이니 꼭 숙달하는게 좋습니다.

 

다음 시간에는 퀵정렬에 대해서 알아봅니다.