합병 정렬 (Merge Sort) 은 데이터 영역을 잘게 쪼개어 정렬을 하는 분할 정복 (Divide and Conquer) 에 기반한 정렬 방법으로, 잘게 쪼갠 데이터들을 하나씩 합병하여 정렬하는 방법이다.(분할 정복과 같은 알고리즘 방법에 대한 이야기는 간단한 알고리즘 정리 이후에 다룰 예정이다.) 구현이 어렵고, 재귀 함수 활용시 추가적인 메모리가 필요하지만, 기초적인 정렬 방법과 비교하여 정렬 속도가 매우 빠르다.
위의 그림과 같은 단계를 통해서 정렬이 진행된다. 먼저, 전체 데이터 영역을 최소 단위로 쪼갠다. 쪼갠 데이터들을 하나씩 합병할 때에, 정렬을 한다. 이 방식을 반복한다.
합병 정렬을 다음과 같이 구현하였다.
데이터 영역의 가운데 위치를 iTemp_CenterPosition 에 저장하고, 이를 기준으로 데이터 영역으로 두개로 나눈다. 두개의 영역을 합병 정렬하도록, 합병 정렬 함수를 재귀적으로 호출한다.(우선적으로 전체 데이터 영역이 최소 단위로 쪼개어진다.) 데이터 영역만큼의 메모리를 추가적으로 할당한뒤, 두개의 영역은 각각 정렬이 되어 있다고 가정하고, 순서대로 값을 비교하여, 합병, 정렬된 데이터 영역을 만든다. 이 방식을 반복한다. 이 정렬 사용하는 예제는 이전 글(링크 : [C] 거품 정렬 (Bubble Sort) 정의 / 코드 / 개선)에서 확인할 수 있다.
'Programming > Algorithm' 카테고리의 다른 글
| [C] 선택 정렬 (Selection Sort) 정의 / 코드 (0) | 2013.06.04 |
|---|---|
| [C] 삽입 정렬 (Insert Sort) 정의 / 코드 (0) | 2013.06.03 |
| [C] 칵테일 정렬 (Cocktail Sort) 정의 / 코드 (0) | 2013.05.17 |
| [C] 거품 정렬 (Bubble Sort) 정의 / 코드 / 개선 (0) | 2013.05.17 |
| 정렬 알고리즘 (Sort) 정의 (0) | 2013.05.17 |
