병합 정렬 (Merge Sort)
병합 정렬은 분할 정복(Divide & Conquer)의 대표적인 예로 배열을 잘게 나누어서 다시 합칠 때 정렬하는 방법입니다. {8, 4, 6, 2, 1, 3, 5, 9, 10, 7} 인 배열을 병합 정렬 보겠습니다. 크기가 1인 배열이 될 때 까지 반으로 분할 하고, 이를 다시 합치면서(정복) 정렬하는 것이 병합 정렬입니다. 합치면서 정렬하는 방법에 대해 좀 더 상세히 알아보도록 하겠습니다. 배열 A : {4, 8} 과 B: {1, 2, 6}을 합쳐보도록 하겠습니다. 일단 배열의 크기가 1일 때부터 정렬하면서 합쳐주었으므로 배열 {4, 8}과 {1, 2, 6}은 정렬된 상태입니다. 그러므로 가장 앞에 수가 최솟값입니다. 각 배열을 인덱스 0부터 비교해가면서 작은 값을 배열의 0번째 값에 넣어줍니다. ..
2019. 4. 23.
