합병 정렬 (Merge Sort)

합병정렬에 대해서 알아보자

분할정복?!을 적용한 정렬이다.

(분할정복 : 2개의 부분문제로 계속 나아가며 크기가 1/2씩 계속 감소하는 알고리즘)

그림으로 표현 하자(내림차순 정렬)

첫번째로 최소단위 까지 분할하여 내려간다. 

두번째로 비교를 통하여 정렬한후 합병한다, 

시간복잡도에 대하여 얘기해보자

1. 분할하는 과정에서는 비교 형태가 아니며 중간(mid)값을 계산과 재귀호출 을 요구하므로 O(1)

2. 합병하는 과정에서는 양쪽을 비교하는데 

       왼쪽의 크기를 m

       오른쪽의 크기를 n

    이라고 가정을하면

    최대비교 횟수는 O(m+n-1)이된다.

        O(m+n-1) = > O(m+n)

    m 과  n은 입력값에 비례하므로 O(n)이 되게되는데

    즉. 층당 O(n)이 적용되는데

    이 층은 분할되어 1/2 가 작용되므로 log2n 이 되어진다

   따라서, (층수)XO(n) = log2n x O(n)  =  O(nlogn)이되어진다.

코드는 어떻게?(CPP)

그림을 보면서 합병 정렬을 이해하기란 쉽다

허나 코드로 구현하자니 감이 안잡힐 수 있다.

먼저 아래코드를 써내려 가기전에 설명을 드리겠습니다

function 은 두가지로

mergeSort, arrayMerge 가 존재합니다

mergeSort 는 재귀 함수인 형태로 계속해서 분할 해나가며 최종적으로 합병을 시행합니다

mergeSort안에는 이러한 형태가 담겨져있는데

        mergeSort(start, mid); // 분할한 왼쪽을 뜻하며

        mergeSort(mid+1, end); // 분할한 오른쪽을 뜻합니다

        arrayMerge(start, end); // 최종적으로 정렬을 하며 합병을 시도합니다

arrayMerge는 합병을 시도 하는함수입니다

입력값은 첫번째는 정렬할 수의 갯수 입니다

예) 5

     3

     2

     1

     8

     10

#include <iostream> using namespace std; int *arr; // 입력값 및 실질적인 포인터 int *tmp; // 임시 저장할 포인터 void printArr(int *parr,int start,int end){ for(int i=start;i<end;i++){ printf("%d\n",parr[i]); } } void arrayMerge(int start,int end){ int mid = (start+end)/2; int i = start; int j = mid+1; int k = start; while(i<=mid&&j<=end){ if(arr[i]<arr[j]){ tmp[k] = arr[i]; i++; }else{ tmp[k] = arr[j]; j++; } k++; } int ns = i>mid?j:i; for(;ns<=end;ns++){ tmp[k] = arr[ns]; k++; } for(k=start;k<end+1;k++){ arr[k] = tmp[k]; } } void mergeSort(int start,int end){ int mid; if(start<end){ mid = (start+end)/2; mergeSort(start, mid); mergeSort(mid+1, end); arrayMerge(start, end); } } int main(int argc, const char * argv[]) { int inputNum; int arrNum = 0; cin >> inputNum; arr = (int*)malloc(sizeof(arr)*(inputNum+1)); tmp = (int*)malloc(sizeof(arr)*(inputNum+1)); for(int i = 0 ; i<inputNum ; i++){ cin >> arr[arrNum]; arrNum++; } mergeSort(0, inputNum-1); printArr(arr, 0,inputNum); return 0; }