병합정렬(merge sort)
병합 정렬에 대해서 설명드릴게요.
말 그대로 분할 해서 병합 시키는 정렬입니다.
총 3단계로 나누어 보면
- Divide : 분할 한다.
- Sol: 해결 한다.
- Combine: 결합 한다.
이런 3단계가 기본 원리입니다. 이를 알고리즘에 적용 시켜서 그림으로 보겠습니다.
8 2 3 7 1 5 4 6이라는 숫자가 무작위로 배열 되어 있습니다.
이를 반으로 나눠서 정렬을 해보도록 해보죠.
↓
1단계
우선 반으로 절반 쪼갰습니다. 분할을 했죠.
8 2 3 7 과 1 5 4 6으로 말이죠.
↓
2단계
그 다음 각 부분에서 정렬을 시도 합니다. 즉 문제를 해결 합니다.
↓
3단계
적절 하게 정렬을 하면서 결합을 완료 짓습니다.
정렬 완료입니다.
실제로는 훨씬 더 작게 분할을 해야합니다. 예를 보여주고자 큼직하게 보여준겁니다.
즉 데이터가 1개 남을 때 까지 분할을 하여 병합을 합니다. 데이터 2개는 정렬을 해야하지만 1개는 정렬을 하지 않아도 되기 때문입니다.
구체적인 그림을 보자면
이런 식으로 1개남을 때까지 분할 하고 정렬하면서 병합합니다.
즉 재귀적인 구현으로 병합 정렬은 진행이 됩니다. 따라서 2개씩 분리를 한거구요.
즉 MergeSort라는 함수를 재귀를 통해서 진행을 하게 됩니다.
MergeSort 함수에서는 배열의 중간 지점을 구하고 재귀함수 호출로 2개로 나눈 범위로 호출을 하고 또 호출합니다.
그러다 마지막 MergeArea라는 병합 함수로 두 배열을 합칩니다.
이것을 C언어로 짠 소스코드를 보시겠습니다.
MergeCombination(병합 함수)
MergeCombination 함수를 보면 복잡해 보이지만 간단합니다. 쉽습니다.
우선 인자를 보시죠.
첫 인자로 졍렬 할 배열은 전달합니다.
두 번째 인자로 left(배열의 왼쪽) 전달 합니다.
세 번째 인자로 mid(배열의 중간)을 전달 합니다.
네 번째 인자로 배열의 맨 오른쪽을 전달합니다.
fIdx 변수에는 맨 왼쪽 인덱스 값(left)를 담고 rIdx는 mid 이후 배열의 맨 왼쪽 인덱스 값(mid+1)을 담습니다.
sortArr는 정렬을 담을 배열입니다. 동적할당을 하죠.
while문에서는 fIdx<=mid 이고 rIdx<=right은 즉 fIdx가 mid를 넘지 않고 rIdx가 right를 넘지 않을 때 까지라는 의미입니다.
이게 무슨 소리냐면 병합 함수는 분할 된 배열의 앞 배열과 뒷 배열을 서로 비교하면서 인덱스를 증가시킵니다.
이때 fldx 와 rldx가 mid와 right를 넘는 다는 건 끝났다는 소리입니다.
따라서 끝나기 전까지 while문을 돌립니다.
while문 내용을 봅시다.
우선 fIdx와 rIdx에 들어있는 값들을 비교를 합니다. 만약에 rIdx의 값이 더 크다면 fIdx의 배열 값이 저장 될 배열sortArr에
앞 부분에 차례대로 들어가겠죠? 따라서 sortArr에 fldx의 배열 값을 넣습니다. 인덱스는 증가시킵니다.
else문은 반대로 생각하시면 됩니다.
이렇게 비교하시다가
fIdx가 mid를 넘는다!! 그말은 즉 앞 배열의 비교가 끝났다는 건 앞 배열이 이미 sortArr에 다 들어갔다는 겁니다. 그럼 남은 뒷 배열(정렬 이미 됨)을
sortArr 빈 자리에 다 집어넣습니다. else문도 마찬가지입니다.
그렇고 마지막 for문에서는 총 병합된 sortArr배열을 arr배열에 집어넣습니다.
MergeSort 함수
이 함수는 정렬을 담당하는 부분으로 분할을 하고 병합을 총괄하는 함수입니다.
원리는 재귀함수호출을 이용합니다.
우선 mid는 중간 지점입니다.
첫 if문에서 left가 right보다 작다는 것은 아직 덜 분할이 됐다는 소리입니다.
즉 더 분할 할 수 있다!!! 그 말이죠.
그래서 중간지점 mid를 계산을 합니다. left+right 나누기 2!! 이건 다들 아실겁니다
그렇고 MergeSort 함수를 left부터 중간지점까지 그 이후 mid+1부터 right까지
두 함수로 분할을 합니다. 재귀호출로 인해서죠.
그렇고 분할 된것을 마지막으로 병합합니다. 앞서 설명드렸던 MergCombination함수로 말이죠.
main함수에서는 MergSort함수만 호출 하시면 되겠씁니다.
이 것으로 병합정렬 설명을 마치도록 할게요 감사합니다.
