1. Merge Sort

간단한 도식화 그림을 살펴보자.

 

위의 도식화 그림을 설명하면 아래와 같다.

위의 그림과 같이 정렬할 배열이 주어졌다고 가정하면,

1. 분할 :  정렬할 배열을 27 10 12 20 과 25 13 15 22의 2개의 부분 배열로 나눈다.

2. 정복 :  부분 배열을 정렬하여 10 12 20 27 과 13 15 22 25를 얻는다.

3. 결합 :  부분 배열을 통합하여 10 12 13 15 20 22 25 27 을 얻는다.

 

각 각의 부분 배열들을 어떻게 정렬하여야 할까?

정답은 부분 배열들을 정렬할 때도 합병 정렬을 순환적으로 적용하면 된다.

즉, 위의 예에서 부분 배열인 27 10 12 20을 정렬할 때도 합병 정렬의 개념을 다시 적용한다.

이는 합병 정렬 함수의 순환적인 호출을 이용하여 구현하면 된다.

 

위의 합병 정렬의 전체 과정을 그림으로 그려보면 아래와 같다.

 

병합 정렬 알고리즘

알고리즘 설명

1. 만약 나누어진 구간의 크기가 1이상이면

2. 중간 위치를 계산한다.

3. 앞쪽 부분 배열을 정렬하기 위하여 MergeSort함수를 순환 호출한다.

4. 뒤쪽 부분 배열을 정렬하기 위하여 MergeSort함수를 순환 호출한다.

5. 정렬된 2개의 부분 배열을 통합하여 하나의 정렬된 배열로 만든다.

 

병합 정렬에서 실제로 정렬이 이루어지는 시점은 2개의 리스트를 합병(Merge)하는 단계이다.

정렬된 2개의 배열을 병합하는 알고리즘을 만들어보자.

병합에는 추가적인 리스트 (배열) 이 필요하다.

병합 알고리즘은 2개의 리스트의 요소들을 처음부터 하나씩 비교하여 두 개의 리스트의 요소 중에서

더 작은 요소를 새로운 리스트로 옮긴다.

둘 중에 하나가 끝날 때까지 이 과정을 되풀이 한다.

만약, 둘 중에서 하나의 리스트가 먼저 끝나게 되면, 나머지 리스트의 요소들을 전부 새로운 리스트로 복사하면 된다.

아래의 그림에서 먼저 배열A의 첫 번째 요소인 2와 배열B의 첫 번째 요소인 1을 비교하여

1이 더 작으므로 1을 배열C로 옮긴다.

다음으로 A의2와 B의 다음 숫자인 3을 비교한다.

이번에는 A의 2가 B의 3보다 작으므로, 이번에는 A의 2를 C로 이동한다.

이런식으로 두 개의 리스트 중에서 하나가 먼저 끝날 때까지 이 과정을 되풀이 한다.

두 개의 리스트 중 하나가 먼저 끝나면 나머지 요소들을 리스트 C로 복사한다.

 

병합 알고리즘

위의 병합 알고리즘에서는 하나의 배열 안에 두 개의 정렬된 부분 리스트가

저장되어 있다고 가정하였다.

즉, 첫 번째 부분 리스트는 _pArr[left] 부터 _pArr[mid]까지 이고

     두 번째 부분 리스트는 _pArr[mid+1] 부터 _pArr[right]까지이다.

합병된 리스트를 임시로 저장하기 위해 배열 pSort를 사용한다.

아래의 그림을 보자.

프로그램의 구현은 다음과 같은 흐름으로 작성을 하면 된다.

MergeSort함수에서 주어진 _pArr 배열을 2등분하여 각 각의 부분 배열에 대하여

다시 MergeSort 함수를 순환 호출한다.

이러한 과정은 결국, 부분 배열에 숫자가 하나 남을 때까지 계속된다.

분할 과정이 끝나면 정렬된 부분 배열을 Merge함수를 이용하여 합병하는 과정이 시작된다.

실제로 숫자들이 정렬되는 곳은 바로 이 합병 과정이다.

Merge함수는 부분 배열들의 숫자를 임시 배열에 정렬된 상태로 만든 다음,

다시 원래의 배열에 복사한다.

 

함수의 구현

재귀 함수를 분석할 때는 호출 스택을 통해 그려보는 것이 좋다고 생각.

함수부터 먼저 보면,

MergeSort함수에서 재귀 함수의 호출이 발생하는데, 이에 대한 호출 스택 그림은 아래와 같다.

즉, 재귀 함수가 탈출 조건이 되면, 두 정렬된 데이터를 하나로 병합하는 함수가 호출이 된다.

 

그리고, 아래는 메인 함수와 그 실행 결과

 

 

아래는 소스 파일

main.c

0.00MB