합병 정렬 알고리즘을 이용해 int 배열을 오름차순으로 정렬하는 함수

합병 정렬

합병 정렬(merge sort) 은 하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 리스트를 합하여 전체가 정렬된 리스트트를 만드는 방법이다. 이것은 분할 정복(divide and conquer) 기업에 바탕을 두고 있는데, 하나의 문제를 작은 2개의 문제로 분리하고 각가을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략이다. 분리된 문제가 아직도 해결하기 어렵다면, 즉 충분히 작지 않다면 분할 정복 방법을 연속하여 다시 적용한다. 분할 정복 기법은 대개 순환 호출을 이용하여 구현된다.

1. 분할(Divide) : 입력 배열을 같은 크기의 2개의 부분 배열로 분할 한다.

2. 정복(Conquer) : 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출을 이용하여 다시 분할 정복 기법을 적용한다.

3. 결합(Combine) : 정렬된 부분 배열들을 하나의 배열에 통합한다.

| 합병 정렬 알고리즘

---

mergeSort(A, left, right)

if left < right

mid = (left+right)/2;

mergeSort(A, left, mid);

mergeSort(A, mid+1, right);

merge(A, left, mid, right);

---

합병 정렬에서 실제로 정렬이 이루어지는 시점은 2개의 리스트를 합병(merge)한느 단계이다. 합병 방법을 생각해보자. 합병은 2개의 리스트의 요소들을 처음부터 하나씩 비교하여 두 요소 중에서 더 작은 요소를 새로운 리스트로 옮긴다. 두 리스트 중에서 하나가 모두 끝날 때 까지 이 과정을 반복한다. 하나의 리스트가 먼저 끝나면 나머지 리스트의 요소들을 전부 새로운 리스트로 복사한다. 이러한 합병 과정은 어렵지는 않으나 추가적인 리스트를 필요로 한다. 

| 합병 알고리즘

---

// 2개의 인접한 배열 A[left.. mid]  와 A[mid+1.. right]를 합병

b1 = left;

e1 = mid;

b2 = mid + 1;

e2 = right;

sorted 배열을 생성;

index = 0;

while b1<=e1 and b2<= e2 do

if(A[b1] < A[b2])

then

sorted[index] = A[b1];

b1++;

index++;

else

sorted[index] = A[b2];

b2++;

index++;

요소가 남아있는 부분 배열을 sorted로 복사한다;

sorted를 A로 복사한다;

---

---

#define MAX_SIZE 1024

static void merge(int A[], int left, int mid, int right) {

int i, j, k = left, l; // k는 정렬될 리스트에 대한 인덱스

static int sorted[MAX_SIZE];

// 분할 정렬된 A의 합병

for (i = left, j = mid + 1; i <= mid && j <= right;)

sorted[k++] = (A[i] <= A[j]) ? A[i++] : A[j++];

// 한쪽에 남아 있는 레코드의 일괄 복사

if (i > mid)

for (l = j; l <= right; l++, k++)

sorted[k] = A[l];

else

for (l = i; l <= mid; l++, k++)

sorted[k] = A[l];

// 배열 sorted[]의 리스트를 배열 A[]로 재복사

for (l = left; l <= right; l++)

A[l] = sorted[l];

}

//합병 정렬 알고리즘을 이용해 int 배열을 오름차순으로 정렬하는 함수

void mergeSort(int A[], int left, int right) {

if (left < right) {

int mid = (left + right) / 2; // 리스트의 균등 분할

mergeSort(A, left, mid); // 부분 리스트 정렬

mergeSort(A, mid + 1, right); // 부분 리스트 정렬

merge(A, left, mid, right); // 합병

}

}

---

하나의 합병 단계에서 보면 임시 배열에 복사했다가 다시 가져와야 되므로 이동 연산은 총 부분 배열에 들어 있는 요소의 개수가 n인 경우, 레코드의 이동이 2n번 발생하므로 하나의 합병 단계에서 2n개가 필요하다. 따라서개의 합병 단계가 필요하므로 총 개의 이동 연산이 필요하다. 결론적으로 합병 정렬은 의 복잡도를 가지는 알고리즘이다.

합병 정렬의 특징은 입력 데이터가 어떻게 이루어져 있는지에 상관없이, 즉 최악, 평균, 최선의 경우에도 모두 동일한 시간에 정렬된다는 것이다. 합병 정렬의 단점은 임시배열이 필요한 것과, 만약 레토드들의 크기가 큰 경우에는 이동횟수가 많아 큰 시간적 낭비가 발생할 수 있다는 것이다. 그러나 레코드 자체를 이동하지 않고 포인터(또는 링크 인덱스)만 이동하며 이런 문제가 해결된다. 따라서 합병 정렬은 매우 효율적인 정렬 방법의 하나이다.