병합 정렬(Merge Sort) (2)

아래의 게시물과 같은 병합 정렬이지만 다른 코드를 소개하고자 한다.

아래 코드보다는 조금 더 길지만, 내용을 이해하기에는 더 편한 코드이다.

아래 그림은 소스코드의 내용 이해를 돕기 위해 제작하였다.

#include <stdio.h>
#include <stdlib.h>
 
 
void MergeTwoArea(int arr[], int left, int mid, int right)
{
    int fIdx = left;
    int rIdx = mid + 1;
    int i;
    // 병합 결과를 담을 메모리 공간 할당
    int *sortArr = (int*)malloc(sizeof(int)*(right + 1));
    int sIdx = left;
 
 
    // 병합 할 두 영역의 데이터를 비교하여 
    // 배열 sortArr에 담는다.
    while (fIdx <= mid && rIdx <= right)
    {
        if (arr[fIdx] <= arr[rIdx])
            sortArr[sIdx] = arr[fIdx++];
 
        else
            sortArr[sIdx] = arr[rIdx++];
 
        sIdx++;
    }
 
    // 배열의 앞 부분이 sortArr로 모두 이동되어서 배열
    // 뒷부분에 남은 데이터를 모두 sortArr로 이동
    if (fIdx > mid)
    {
        for (i = rIdx; i <= right; i++, sIdx++)
            sortArr[sIdx] = arr[i];
    }
 
    // 배열 뒷부분이 sortArr로 모두 이동되어서 배열
    // 앞부분에 남은 데이터를 모두 sortArr로 이동
    else
    {
        for (i = fIdx; i <= mid; i++, sIdx++)
            sortArr[sIdx] = arr[i];
    }
 
    // malloc를 통해 정렬한 내용을 원래 배열에 넣는다.
    for (i = left; i <= right; i++)
        arr[i] = sortArr[i];
 
    // 메모리 할당 해제
    free(sortArr);
}
 
void MergeSort(int arr[], int left, int right)
{
    int mid;
 
    if (left < right)
    {
        // 중간 지점을 계산
        mid = (left + right) / 2;
 
        // 둘로 나눠서 각각을 정렬한다.
        MergeSort(arr, left, mid);    // left~mid에 위치한 데이터 정렬
        MergeSort(arr, mid + 1, right); // mid+1~right에 위치한 데이터 정렬
 
                                        // 정렬된 두 배열을 병합한다.
        MergeTwoArea(arr, left, mid, right);
    }
}
 
 
int main()
{
    int arr[10] = { 2,3,5,6,1,8,6,9,0,7 };
 
    printf("정렬 전 ::");
    for (int i = 0; i <= 9; i++)
        printf("%d ", arr[i]);
 
    MergeSort(arr, 0, 9);
 
    printf("\n정렬 후 ::");
    for (int i = 0; i <= 9; i++)
        printf("%d ", arr[i]);
 
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>