병합정렬
-
[알고리즘] 병합 정렬Stage/Computer Science 2021. 5. 29. 00:53
학습 목표 재귀를 활용한 병합 정렬을 구현할 수 있다. 1. 정렬 알고리즘 대표적인 정렬방법 중 하나이다. 전화번호부에서 mike를 찾기 위해 절반을 나눠서 탐색해나갔던 분할 정복 탐색처럼 데이터를 반으로 나누어간다는 공통점이 있다. 병합 정렬은 원소가 한 개가 될 때까지 반으로 나누다가 다시 합쳐나가며 정렬을 하는 방식이다. 2. 예시 임의로 나열된 8개의 숫자를 오름차순으로 정렬해보자. 7 4 5 2 6 3 8 1 먼저 숫자를 반으로 나누자. 7 4 5 2 | 6 3 8 1 나눠 놓은 덩어리를 한번 더 나눠보자. 7 4 | 5 2 | 6 3 8 1 또 나누자. 7 | 4 | 5 2 | 6 3 8 1 원소가 한 개가 남았으므로 더 이상 나눌 수가 없다. 두 숫자를 작은 숫자가 먼저 오도록 병합하자. 4..