병합 정렬

병합 정렬은 말그대로 “분할”하여 “정복” 하는 방법이다.

• 1단계 (분할) 해결이 용이한 단계까지 분할해 나간다.
• 2단계 (정복) 해결이 용이한 수준까지 분할된 문제를 해결한다.
• 3단계 (결합) 분할해서 해결한 결과를 결합하여 마무리한다.

예를들어 8개의 데이터를 동시에 정렬하는 것 보다, 이를 둘로나눠 4개의 데이터를 정렬하는 것이 쉽고, 또 이들 각각을 다시 한번 둘로 나눠서 2개의 데이터를 정렬하는 것이 더 쉽다.

https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html

code

#include <stdio.h>
#include <stdlib.h>

void MergeTwoArea(int arr[], int left, int mid, int right)
{
    int fIdx = left;
    int rIdx = mid + 1;
    int sIdx = left;

    int *sortArr = (int *)malloc(sizeof(right) + 1);

    while (fIdx <= mid && rIdx <= right) // 이 부분을 이해 해야한다. 
    {
        if (arr[fIdx] < arr[rIdx])
            sortArr[sIdx] = arr[fIdx++];
        else
            sortArr[sIdx] = arr[rIdx++];
        sIdx++;
    }
    if (fIdx > mid)
    {
        for (int i = rIdx; i <= right; i++, sIdx++)
        {
            sortArr[sIdx] = arr[i];
        }
    }
    else
    {
        for (int i = fIdx; i <= mid; i++, sIdx++)
        {
            sortArr[sIdx] = arr[i];
        }
    }

    for (int 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);
        MergeSort(arr, mid + 1, right);
        MergeTwoArea(arr, left, mid ,right);
    }
}

int main(void)
{
    int arr[8] = {21, 10, 12, 20, 25, 13, 15, 22};
    int i;

    MergeSort(arr, 0, sizeof(arr) / sizeof(int));
    for (int i = 0; i < 8; i++)
        printf("%d ", arr[i]);
    return 0;
}

하나와 하나 가 모여 2개 가 될때, 비교연산은 2회 진행된다.

while (fIdx <= mid && rIdx <= right) { if (arr[fIdx] < arr[rIdx]) sortArr[sIdx] = arr[fIdx++]; else sortArr[sIdx] = arr[rIdx++]; sIdx++; } if (fIdx > mid) { for (int i = rIdx; i <= right; i++, sIdx++) { sortArr[sIdx] = arr[i]; } } else { for (int i = fIdx; i <= mid; i++, sIdx++) { sortArr[sIdx] = arr[i]; } } for (int i = left; i <= right; i++) { arr[i] = sortArr[i]; }

while문을 지날 때, if~else문을 지날 때.

위의 그림에서 병합 1을 지날 때의 비교연산의 수는 8회이다.

두개와 두개가 모여 4개가 될 때?. 비교연산의 수는 8회이다.

이렇듯 마지막 하나의 데이터가 남을 때 까지 비교연산이 진행되는 경우에 비교연산의 횟수는 총 8회이다.

“정렬의 대상인 데이터의 수가 n개 일때, 병합 정렬에서 진행되는 최대 연산의 수는 최대 n번이다.

따라서 병합 정렬의 비교연산에 대한 빅-오는 다음과 같다.

O(n log2n)

병합 정렬

병합 정렬

병합 정렬은 말그대로 “분할”하여 “정복” 하는 방법이다.

• 1단계 (분할) 해결이 용이한 단계까지 분할해 나간다.
• 2단계 (정복) 해결이 용이한 수준까지 분할된 문제를 해결한다.
• 3단계 (결합) 분할해서 해결한 결과를 결합하여 마무리한다.

예를들어 8개의 데이터를 동시에 정렬하는 것 보다, 이를 둘로나눠 4개의 데이터를 정렬하는 것이 쉽고, 또 이들 각각을 다시 한번 둘로 나눠서 2개의 데이터를 정렬하는 것이 더 쉽다.

https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html

code

#include <stdio.h>
#include <stdlib.h>

void MergeTwoArea(int arr[], int left, int mid, int right)
{
    int fIdx = left;
    int rIdx = mid + 1;
    int sIdx = left;

    int *sortArr = (int *)malloc(sizeof(right) + 1);

    while (fIdx <= mid && rIdx <= right) // 이 부분을 이해 해야한다. 
    {
        if (arr[fIdx] < arr[rIdx])
            sortArr[sIdx] = arr[fIdx++];
        else
            sortArr[sIdx] = arr[rIdx++];
        sIdx++;
    }
    if (fIdx > mid)
    {
        for (int i = rIdx; i <= right; i++, sIdx++)
        {
            sortArr[sIdx] = arr[i];
        }
    }
    else
    {
        for (int i = fIdx; i <= mid; i++, sIdx++)
        {
            sortArr[sIdx] = arr[i];
        }
    }

    for (int 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);
        MergeSort(arr, mid + 1, right);
        MergeTwoArea(arr, left, mid ,right);
    }
}

int main(void)
{
    int arr[8] = {21, 10, 12, 20, 25, 13, 15, 22};
    int i;

    MergeSort(arr, 0, sizeof(arr) / sizeof(int));
    for (int i = 0; i < 8; i++)
        printf("%d ", arr[i]);
    return 0;
}

하나와 하나 가 모여 2개 가 될때, 비교연산은 2회 진행된다.

while (fIdx <= mid && rIdx <= right)

{

if (arr[fIdx] < arr[rIdx])

sortArr[sIdx] = arr[fIdx++];

else

sortArr[sIdx] = arr[rIdx++];

sIdx++;

}

if (fIdx > mid)

{

for (int i = rIdx; i <= right; i++, sIdx++)

{

sortArr[sIdx] = arr[i];

}

}

else

{

for (int i = fIdx; i <= mid; i++, sIdx++)

{

sortArr[sIdx] = arr[i];

}

}

for (int i = left; i <= right; i++)

{

arr[i] = sortArr[i];

}

while문을 지날 때, if~else문을 지날 때.

위의 그림에서 병합 1을 지날 때의 비교연산의 수는 8회이다.

두개와 두개가 모여 4개가 될 때?. 비교연산의 수는 8회이다.

이렇듯 마지막 하나의 데이터가 남을 때 까지 비교연산이 진행되는 경우에 비교연산의 횟수는 총 8회이다.

“정렬의 대상인 데이터의 수가 n개 일때, 병합 정렬에서 진행되는 최대 연산의 수는 최대 n번이다.

따라서 병합 정렬의 비교연산에 대한 빅-오는 다음과 같다.

O(n log2n)