Merging Sort   병합 정렬

(2019-12-23)
1. 병합 정렬 (Merging Sort)

  ㅇ 자료를 여러 부분 집합으로 나누고 이를 병합하면서 정렬하는 방식
     - 정렬 대상을 2개(거의 같은 크기)로 분할해가면서, 더이상 분할되지 않으면,
       분할된 그룹들을 병합해가며 정렬 함
     - 즉, 배열을 이등분한 다음, 각각을 재귀적으로 병합 정렬하고, 이들을 병합하여 정렬 함 
  ㅇ 계산 효율성 : 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. 퀵 정렬

 
        최근수정     요약목록     참고문헌