1. 병합 정렬 (Merging Sort)
ㅇ 자료를, 부분 집합으로 나누고, 이를 병합하면서, 정렬하는 방식
- 정렬 대상을 2개(거의 같은 크기)로 분할해가면서, 더이상 분할되지 않으면,
분할된 그룹들을 병합해가며 정렬 함
- 즉, 배열을 이등분한 다음, 각각을 재귀적으로 병합하여 정렬 함
ㅇ 1945년 존 폰 노이만이 고안함
ㅇ 계산 효율성 : O(nlogn)
ㅇ 특징
- 명시적으로 재귀 호출을 사용
- 퀵 정렬 처럼 분할 정복 전략을 사용
- 안정 정렬
- 고른 성능을 보임
ㅇ 알고리즘 표현 例
mergeSort(Data[],p,r) {
q = (p+r)/2; // 이등분
mergeSort(Data[],p,q) // 전반부 정렬 (재귀호출)
mergeSort(Data[],q+1,r) // 후반부 정렬 (재귀호출)
merge(Data[],p,q,r) // 병합
}
merge(Data[],p,q,r) {
// 정렬된 두 부분 배열을 합쳐 하나의 큰 배열을 만들어 반환하는 루틴
}
1.
2.
3.
4.
5.
6.