티스토리 뷰

부경대 IT융합응용공학과 권오흠 교수님의 영리한 프로그래밍을 위한 알고리즘 강좌와 '쉽게 배우는 알고리즘: 관계중심의 사고법 - 문병로'등을 통한 알고리즘 학습 강좌 링크

3-2. 합병정렬(Merge sort)

  • simple, slow

    • Bubble sort

    • Insertion sort

    • Selection sort

  • fast

    • Quick sort

    • Merge sort

    • Heap sort

  • O(n)

    • Radix sort

분할 정복법 "Divide and Conquer"

  • merge sort와 quick sort는 분할 정복 알고리즘을 사용한다.

  • 기본적으로 resursion을 사용하여 문제를 해결하는 기법이다.

  • 아래의 세가지 단계를 거쳐서 문제를 해결한다.

  • 분할

    • 해결하고자 하는 문제를 작은 크기의 동일한 문제들로 분할

    • 크기는 작은 사이즈의 문제이지만, 문제 자체는 전체 문제와 동일한 문제들

  • 정복

    • 각각의 작은 문제를 순환적으로 해결

  • 합병

    • 작은 문제의 해를 합하여(merge) 원래 문제에 대한 해를 구함

합병정렬(Merge sort)

  • divide : 데이터가 저장된 배열을 절반으로 나눔

  • recursively sort : 각각을 순환적으로 정렬

  • merge : 정렬된 두 개의 배열을 합쳐 전체를 정렬

  • 주어진 배열을 계속해서 반으로 나누다 보면 결국 길이가 1인 리스트로 쭉 나뉘어진다.

  • 길이가 1인 리스트가 된 순간. 그 각각을 정렬된 리스트로 본다.

  • 이것을 한 단계식 merge하면서 다시 정렬된 리스트를 만드는 방식으로 정렬이 이루어진다.

  • merge sort에서 가장 중요한 과정이 다음과 같이 merge하는 과정이다. 정렬된 두 배열을 다시 하나의 정렬된 배열로 만드는 과정이다.

    • 정렬 된 두 배열을 합치기 위해, 추가배열을 이용한다.

    • 두개의 리스트에서 두 배열의 첫번째 값 중, 작은 값 하나가 추가배열의 가장 작은 값이 된다.

Merge sort Algorithm

  • recursive한 호출을 하기 위해서 recursion 함수를 기술할 때는, 매개변수를 명시적으로 지정하라.


mergeSort(A[], p, r) {
 base case 정의; //p>=r인 경우
 if (p < r) then {
   q <- (p + q) / 2; //p, q의 중간 지점 계산
   mergeSort(A, p, q); //전반부 정렬
   mergeSort(A, q+1, r); //후반부 정렬
   merge(A, p, q, r); //합병
}
}

merge(A[], p, q, r) {
 정렬되어 있는 배열 A[p...q] A[q+1...r] 합하여
 정렬된 하나의 배열A[p...r] 만든다.
}
  • 실제 merge() 작성


void merge(int[] data, int p, int q, int r) {
 int i = p;
 int j = q+1;
 int k = p;
 int[] tmp = new int[data.length];
 while (i <= q && j <= r) {
   if (data[i] <= data[j])
     tmp[k++] = data[i++];
   else
     tmp[k++] = data[j++];
}
 while (i <= q)
   tmp[k++] = data[i++];
 while (j <= r)
   tmp[k++] = data[j++];
 for (int i = p; i <= r; i++)
   data[i] = tmp[i];
}

시간복잡도

  • n개의 데이터를 정렬하는 시간을 T(n) 이라고 했을 때, N을 반으로 나누어서 정렬하는 시간은 T(n/2)이다. 따라서, 반으로 나눈 배열을 merge sort하는 시간 T(n/2)를 두번 더하고,

  • 다시 이 정렬된 두개의 배열을 merge하는 과정에서 두개의 정렬된 배열의 원소를 한번 비교할 때마다, 정렬된 원소를 저장할 추가 배열에 하나씩 원소가 추가되므로 비교연산의 횟수는 n을 넘지 않는다. 총 원소의 수는 n개이다.

  • 그리고 base case로, 정렬할 데이터가 1개라면 비교 연산의 횟수는 0이다.

  • 따라서 아래와 같이 시간복잡도를 표현할 수 있다.

  • T(n) =

    • if n =1

      • 0

    • otherwise

      • T(n/2) + T(n/2) + n

    • => O(nlogn)

O(nlogn)

  • 길이가 n인 배열을 둘로 쪼개서 다시 정렬된 배열로 병합할 때는 비교의 횟수가 n번을 넘지 않는다.

  • 길이가 n/2인 배열을 정렬하는데에는, n/4의 길이를 가지는 배열 두개를 정렬하므로, 이것의 비교연산 횟수는 n/2이다.

    • 전체로 보면 길이가 n/4인 배열을 두개씩 merge하여 정렬된 n/2배열을 두개 만드는 작업을 수행하는데 드는 비교연산의 횟수는, 2 * (n/2) = n이다.

  • 아래로 내려갈수록 똑같이 비교연산의 횟수는 n이다.

  • 길이가 n인 배열을 길이가 1인 각각의 리스트로 쪼개려면, 아래의 표에서 봤을때 트리의 레벨은 logN이 된다.

  • 따라서, merge sort에 필요한 비교연산의 횟수는 총 n * logn이다.

  • O(nlogn)






댓글
댓글쓰기 폼