합병
-
1. Merge SortC 자료구조/Sort Advanced 2020. 6. 21. 18:11
간단한 도식화 그림을 살펴보자. 위의 도식화 그림을 설명하면 아래와 같다. 위의 그림과 같이 정렬할 배열이 주어졌다고 가정하면, 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을 정렬할 때도 합병 정렬의 개념을 다시 적용한다. 이는 합병 정렬 함수의 순환적인 호출을 이용하여 구현하면 된다. 위의 ..