합병 정렬 (Merge Sort)

개념
리스트를 두 개로 나누어, 각각을 정렬한 다음, 다시 하나로 합치는 정렬 방법

I.  합병 정렬 (Merge Sort)의 개요

  가.  합병 정렬의 정의

- 리스트를 두 개로 나누어, 각각을 정렬한 다음, 다시 하나로 합치는 정렬 방법

 

나.  합병 정렬의 특징

- 분할과 정복 : 분할(Divide) -> 정복(Conquer) -> 결합(Combine) 과정 수행

- 재귀적 수행 : 분할을 마친 후 분활된 부분의 반복적 수행

- 정렬을 위한 별도의 공간이 필요

- 수행시간 복잡도: O(n·log2n)

 

Ⅱ. 합병 정렬의 단계 및 사례

   가.  합병 정렬의 단계

 

나.  합병 정렬 개념

void mergeSort(int arr[], int l, int r)

{

    if (l < r)

    {

        int m = l+(r-l)/2; //Same as (l+r)/2, but avoids overflow for large l and h

        mergeSort(arr, l, m);

        mergeSort(arr, m+1, r);

        merge(arr, l, m, r);

    }

}

 

void merge(int arr[], int l, int m, int r)

{

    int i, j, k;

    int n1 = m - l + 1;

    int n2 =  r - m;

 

    /* create temp arrays */

    int L[n1], R[n2];

 

    /* Copy data to temp arrays L[] and R[] */

    for(i = 0; i < n1; i++)

        L[i] = arr[l + i];

    for(j = 0; j < n2; j++)

        R[j] = arr[m + 1+ j];

 

    /* Merge the temp arrays back into arr[l..r]*/

    i = 0;

    j = 0;

    k = l;

    while (i < n1 && j < n2)

    {

        if (L[i] <= R[j])

        {

            arr[k] = L[i];

            i++;

        }

        else

        {

            arr[k] = R[j];

            j++;

        }

        k++;

    }

 

    /* Copy the remaining elements of L[], if there are any */

    while (i < n1)

    {

        arr[k] = L[i];

        i++;

        k++;

    }

 

    /* Copy the remaining elements of R[], if there are any */

    while (j < n2)

    {

        arr[k] = R[j];

        j++;

        k++;

    }

}

 

댓글