병합 정렬 구현 (병합) #2

앞서 분열한 배열들을 정렬해보자

 

처음 들어간 배열은 1~ 8 으로 들어 갔으니 8 ~ 1 로 정렬 해본다

 

아래 그림은 정렬하는 과정을 나타내는 그림이다.

 

노란색 박스를 보자

 

일단 1, 2를 병합 하면서 정렬하여 2,1이 정렬되었고 3,4 역시 정렬 되어 4,3으로 정렬 되었다고 하자

첫번째 병합된 배열은 Start Index에서 End index가 Mid인 상황이고

두번째 병합된 배열은 Start Index가 mid+1 인 상황에서 End Index 까지 정렬 되어있는 상황이다.

 

이제 두 배열을 병합해보자

 

노란박스 안에 배열은 3개가 있고 다음과 같다.

1번째 배열은 이전에 정렬되어 올라온 첫번째 배열(2,1)

2번째 배열은 이전에 정렬되어 올라온 두번째 배열(4,3)

3번째 배열은 1,2배열을  병합한 배열(코드에선 Malloc으로 생성: local 배열로 지칭)

 

첫번째 배열 Start Index 값과 두번째 배열 Start Index 값을 비교 한다 ( 2 하고 4 비교)

4가 크므로 4를 local 배열에 집어 넣는다. 두번째 배열의 값은 local배열에 들어갔으므로 두번째 배열의 start Index를 +1 한다.

 

다시 첫번째 배열의 Start Index와 두번째 배열의 Start Index를 비교한다. (2하고 3 비교)

3이 크므로 3을 local 배열에 집어 넣는다. 두번째 배열의 값 역시 local 배열에 들어갔으므로 두번째 배열의 start Index를 +1을 한다. 

 

이때 살펴보면, 두번째 배열의 Start Index는 End Index를 넘어 버리는 상황이 온다.

즉 더이상 비교할 값이 없다는 뜻이므로 첫번째 배열의 값들을 그냥 malloc배열에 집어 넣는다.

 

local 배열의 시간 순서

4 <--

4 , 3 <--

4 , 3 , (2,1) <--

 

local 배열: 4, 3, 2, 1

original 배열: (1,2,3,4,5,6,7,8)

 

이제 local 배열을 origin 배열에 집어 넣으면 된다.

memcpy (origin arr, local arr);

=> origin 배열: 4, 3, 2, 1, 5, 6, 7, 8

 

위에까지 구현이 검증 되었다면 더이상 설명을 필요 없다

재귀 함수로 구현되어있기 때문에 첫번째 결합이 잘 들어가면 나머지 역시 정상적으로 정렬된다.

 

(빨간색 박스 역시 위 설명의 첫번째 배열을 2, 두번쨰 배열을 1로 잡고 개념을 적용하면 똑같이 2,1로 정렬된다)

 

코드 구현

위 개념을 mergeComp 함수로 구현 하였으며 : 두개의 배열을 정렬 하여 original 배열에 넣는다.

 

mergeComp()

int mergeComp(int *arr, int startIdx, int midIdx, int endIdx, compFunc comp)
{
    int localIdx = 0; //Malloc 으로 잡은 배열의 위치를 가리키는 Index
    int _1st_startIdx = startIdx; // Merge해야할 첫번째 배열의 시작 Index
    int _2nd_startIdx = midIdx; // Merge해야할 두번째 배열의 시작 Index
    int _1st_endIdx = midIdx == 0 ? 0 : midIdx - 1; // Merge 해야할 첫번쨰 배열의 end Index
    int _2nd_endIdx = endIdx; // Merge 해야할 두번째 배열의 end Index
    int *local_arr = malloc((_2nd_endIdx - startIdx + 1) * sizeof(int)); //1, 2배열의 결합 결과

    /* == 첫번째 배열 또는 두번쨰 배열의 시작 인덱스가 end 인덱스를 넘지 않으면 결합한다 == */
    while ((_1st_startIdx <= _1st_endIdx) && (_2nd_startIdx <= _2nd_endIdx))
    {
        if (arr[_1st_startIdx] == comp(arr[_1st_startIdx], arr[_2nd_startIdx]))
        {
            local_arr[localIdx++] = arr[_1st_startIdx++];
            /* == 첫번째 배열의 start Index가 증가 되었기 때문에 End Index를 넘었는지 확인한다. == */
            if (_1st_endIdx < _1st_startIdx)
            {
                /* == 넘었다면 2번째 배열값들을 local 배열에 집어 넣은 후 break 한다 == */
                localIdx += insertBurst(_2nd_startIdx, _2nd_endIdx, arr, &local_arr[localIdx]);
                break;
            }
        }
        else
        {
            local_arr[localIdx++] = arr[_2nd_startIdx++];
            /* == 두번째 배열의 start Index가 증가 되었기 때문에 End Index를 넘었는지 확인한다. == */
            if (_2nd_endIdx < _2nd_startIdx)
            {
                /* == 넘었다면 1번째 배열값들을 local 배열에 집어 넣은 후 break 한다 == */
                localIdx += insertBurst(_1st_startIdx, _1st_endIdx, arr, &local_arr[localIdx]);
                break;
            }
        }
    }
    /* == localIdx 가 0 이라면 따로 정렬을 하지 않았기에 memory copy를 하지 않는다 == */
    if (localIdx)
    {
        memcpy(&arr[startIdx], local_arr, (localIdx) * sizeof(int));
    }

    free(local_arr);

    return 0;
}

 

comp 는 함수포인터 사용하여 구현하였으며 결합할때 의 기준을 결정한다.

int comp(int val1, int val2)
{
    int temp = 0;

    return temp = val1 > val2 ? val1 : val2;
}

 

실행을 하면 다음과 같이 정렬이 됨을 알 수 있다.