병합 정렬 구현 (분열) #1

병합 정렬을 구현해 보자

 

병합 정렬의 개념은 다음과 같다.

 

1. 데이터를 쪼갤수 없을 때 까지 계속 쪼갠다.

2. 쪼개진 데이터를 병합하면서 정렬한다.

 

우선 1번 개념을 살펴 보자

데이터를 쪼갤 수 없을 떄 까지 쪼갠다는 것을 다음 그림을 보면 이해가 쉽다.

 

 

마지막 red box 를 보면  index 가 더이상 쪼개질 수 없을 만금 쪼개졌다 (배열에 오직 1개의 데이터만 있음)

 

위 처럼 쪼개는 코드를 구현 해보자

 

아래 그림과 같은 Parameter와 재귀 함수를 사용하면 쉽게 구현 할 수 있다.

start Index : 배열의 시작 인덱스

Mid: 배열의 중간 인덱스 ((Start Index + End Index) / 2)

End Index: 배열의 마지막 인덱스

 

start Index와 End Index는 배열의 시작과 끝이기 때문에 구하기 쉽다 다만,

재귀함수로 들어갈 때는 쪼개서 들어가야 하기 때문에 배열의 중앙 Index를 구해야 한다.

다음 재귀함수로 진입시 진입전 구한 Mid는 End Index로 들어가고 (오른쪽 배열)

Mid+1 한 Index는 Start Index로 들어간다. (왼쪽 배열)

 

위 개념을 mergeSort로 구현하였다.

 

mergeSort()

void mergeSort(int *arr, int startIdx, int endIdx)
{
    int midIdx = (startIdx + endIdx) / 2;
 #if log
    printf("array value: ");
    for (int i = startIdx; i <=endIdx; i++)
    {
        printf(" %d ", arr[i]);
    }
    printf("\r\n");
 #endif
    if (startIdx < endIdx)
    {
        mergeSort(arr, startIdx, midIdx); //오른쪽 배열
        mergeSort(arr, midIdx+1, endIdx); //왼쪽 배열
    }
}

main.c

int array[] = {1,2,3,4,5,6,7,8,9,10};

int main(void)
{
    mergeSort(array, 0, (sizeof(array) / sizeof(int)) - 1);

    return 0;
}

재귀 함수의 더이상 진입하지 않는 경우는 start Index와 end Index가 같은 경우다

즉 배열 인덱스가 오직 1개 인경우(배열의 크기가 1)엔 if문에 걸려 더이상 들어가지 않고 종료 된다.

위 코드의 log를 1로 하고 main 함수를 실행시 다음과 같은 log가 나온다.

 

배열의 분열 과정 print