자료 구조 : Selection Sort, Merge Sort(2)

이번 포스팅에서는 Merge Sort (합병정렬) 에 대해 알아보자. 

지난 번에 Selection Sort 보다 좀 더 생각하기 쉬운 정렬 방법으로 생각한다.

우선 Merge Sort에 대해 알아 보기 전에 Merge에 대해 알아보자.

Merge 와 Merge Sort 는 서로 같은 뜻 같지만 실제로는 둘이 조금 다르다.

 

그럼 Merge Algorithm에 대해 그림으로 설명하겠다.

 

배열 1 과 배열 2의 Merge 초기 과정이다.

배열 1의 맨 왼쪽 값과 배열2의 맨 왼쪽 값을 비교해서 작은 값을 복사해 결과 배열에 넣는다.

배열 2의 1의 값은 넣었으니 배열1의 맨 왼쪽값과 배열2의 그다음값을 비교해서 작은 값을 복사해서 집어넣는다.

위와 같은 흐름을 반복하는것이 Merge Algorithm의 흐름이다. 이러한 Merge Algorithm을 이용한것이 Merge Sort 이다.

Merge Sort에 대한 그림을 보면서 설명 해보겠다.

어떤 배열을 하나씩 하나씩 따로 따로 나눈다음에 서로 2그룹씩 합치면서 점점 올라오면서 정렬하는 것이

Merge Sort의 기본적인 흐름이다. 그렇다면 이 알고리즘을 코드로 짜려면 어떻게 짜야할까?

Merge Sort는 지난번에 다룬 코드들과 달리 재귀적으로 짠 것으로 생각해 보기로 한다. 루프 형식으로 merge sort를 나타 낼수 있지만 이는 매우 귀찮은 작업들이 많아지고, 코드 또한 지저분해지기 때문이다. 

 

재귀적으로 짠 Merge Sort 코드는 다음과 같다.(재귀로 짜면 생각보다 간단하게 코드로 나타낼수 있다.)

 

Recursive Merge Sort

int sort(int a[], int n) 
{
    int h;
    int b[n];
    h = n / 2;
    // copy a[] to b[]
    
    sort(b,h); 
    sort(b+h,n-h); 
    
    //Merge two halves in b to a
    
    return; 
 
}

 

a 는 입력 배열 n은 배열의 크기 이고 MergeSort 특성상 Selection Sort와 같은 제자리 교환이 불가능하므로

배열 b를 따로 선언해서 a의 내용을 copy 하는 과정이 필요하다. 이 과정이 MergeSort의 단점이라고 할 수 있을 것이다.

 

h는 n을 2로 나눈 값으로 배열을 반으로 자르기 위함이다. h 가 홀수여도 돌아가는데 문제는 없다. 그렇지만 보다 빠른 이해를 위해 짝수라고 생각하자. 그 다음으로 h크기의 배열(b 배열의 절반크기 ) Sort 하고 나머지 배열도 Sort 한뒤 두개의 정렬된 배열은 merge해서 a에 넣으면 결과적으로 a배열은 sorting된 배열이 된다. 

 

그렇다면 정확성을 한번 따져보자.

 

Proof by Induction 

• 집합 조건을 깰 수 있는 코드는 지금도 없음.
• Base : n =1 . 할일이 없음
• Step:
  • n/2 일 때 sort()함수가 성공한다면
  • => 즉, 재귀 호출이 끝난 후 a[0] < a[2] < .... <a[n/2-1] and a[n/2]<a[n/2+1]< ... <a[n-1] 이라면
  • n일때 sort()함수가 성공한다.
  • => 함수가 끝날떄 a[0]<a[1]<a[2] < ... < a[n-1] 성립

집합 조건을 깰 수 있는 코드는 없다. 코드를 보면 merge도 그렇고 배열 원소의 복사와 이동만 하기 때문에 전체적은 집합을 깰만한 조건은 보이지 않는다. 

 

n/2 일때 (짝수라고 생각) sort() 함수가 성공한다면 두개의 배열로 나눈 배열은 sorting 이 되어있는 상태다.

n일 때 sort 함수가 성공하는가? n/2 일때 성공한 두개의 배열을 결국 merge를 하고 합쳐서 a로 복사하게 된다

그래서 a[0]<a[1]<a[2] < ... < a[n-1] 이 성립하게 된다. merge의 정확성은 이미 알고 있으므로 따라서 정확하다고 

설명할 수 있다.

 

MergeSort의 시간 복잡도는 어떻게 될까?

 

The Complexity

 

 T(n) = n+ 2T(n/2)

       = n + 2(n/2 + 2T(n/4))

       = n + 2(n/2 + 2T(n/4+2T(n/8)))

       = ... = nlogn

따라서 T(n) = O(nlogn)

 

 

이렇게 MergeSort 에 대해 알아보는 시간을 가졌다. 다음 포스팅에서는 실제 배열로 무엇을 할수 있는지에 대한 내용을 다루겠다.