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. 퀵 정렬
  1.   기술공통
  2.   기초과학
  3.   진동/파동
  4.   방송/멀티미디어/정보이론
  5.   전기전자공학
  6.   통신/네트워킹
  7.   정보기술(IT)
        1. 정보기술
    1.   전산기초
    2.   컴퓨터구조
    3.   프로그래밍
          1. 프로그램, 프로그래밍
      1.   프로그래밍 언어론
      2.   프로그래밍 방법론
      3.   객체지향 프로그래밍
      4.   자료표현코드
      5.   자료구조
      6.   알고리즘
            1. 알고리즘
            2. 순서도
            3. 재귀 호출
        1.   알고리즘 효율성
        2.   알고리즘 종류
              1. 알고리즘 분류
              2. 그래프 알고리즘
          1.   기초 알고리즘
          2.   정렬 알고리즘
            1.   1. 정렬 알고리즘
                2. 버블 정렬
                3. 선택 정렬
                4. 삽입 정렬
                5. 병합 정렬
                6. 퀵 정렬
          3.   검색 알고리즘
        3.   알고리즘 전략
        4.   (기타 알고리즘)
      7.   시스템 소프트웨어
      8.   프로그래밍언어 종류
      9.   프로그래밍 기타일반
    4.   데이터베이스
    5.   소프트웨어 공학
    6.   운영체제
    7.   정보보호/보안
    8.   IT 기타기술
  8.   공업일반(기계,재료등)
  9.   표준/계측/품질
  10.   기술경영

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