[Sort] 병합 정렬

병합 정렬

1. 병합 정렬이란?

- 분할 정복 ( DAC - Divide And Conquer ) 알고리즘 디자인 기법에 근거하여 만들어진 정렬 방법

* 분할정복이란? 복잡한 문제를 분할 하여 정복 후 결합하는 방법

∙ 1단계 분할(Divide) 해결이 용이한 단계까지 문제를 분할해 나간다.

∙ 2단계 정복(Conquer) 해결이 용이한 수준까지 분할된 문제를 해결한다.

∙ 3단계 결합(Combine) 분할해서 해결한 결과를 결합하여 마무리한다

2. 분할 방법

3. 재귀적 구현 (최소단위 까지 분할)

void MergeSort(int arr[], int left, int right) { int mid; if(left < right) { // 중간 지점을 계산한다. mid = (left+right) / 2; // 둘로 나눠서 각각을 정렬한다. MergeSort(arr, left, mid); //MergeSort함수는 둘로 나눌 수 없을 때까지 재귀적으로 호출 된다. MergeSort(arr, mid+1, right); // 정렬된 두 배열을 병합한다. MergeTwoArea(arr, left, mid, right); } }

4. 병합을 위한 함수 정의

void MergeTwoArea(int arr[], int left, int mid, int right) { int fIdx = left; int rIdx = mid+1; int i; int * sortArr = (int*)malloc(sizeof(int)*(right+1)); int sIdx = left; /** * 병합 할 두 영역의 데이터를 비교화여 * 배열 sortArr에 담는다 */ while(fIdx<=mid && rIdx<=right) { if(arr[fIdx] <= arr[rIdx]) sortArr[sIdx] = arr[fIdx++]; else sortArr[sIdx] = arr[rIdx++]; sIdx++; } /** * 배열의 앞 부분이 sortArr로 모두 이동되어서 * 배열 뒷부분에 남은 데이터를 모두 sortArr로 이동 */ if(fIdx > mid) { for(i=rIdx; i<=right; i++, sIdx++) sortArr[sIdx] = arr[i]; } /** * 배열의 뒷 부분이 sortArr로 모두 이동되어서 * 배열 앞부분에 남은 데이터를 모두 sortArr로 이동 */ else { for(i=fIdx; i<=mid; i++, sIdx++) sortArr[sIdx] = arr[i]; } // 병합 결과를 옮겨 담는다 for(i=left; i<=right; i++) arr[i] = sortArr[i]; free(sortArr); }