컴퓨터 알고리즘(합병정렬)

정렬문제(sorting problem)

 

알고리즘은 4단계에 걸쳐서 설명할 수 있다.

문제정의, 알고리즘 설명, 정확성 증명, 성능 분석

 

 - 입력 (input)

    n개의 숫자들의 배열 (a1, a2, a3......... an)

 

 - 출력 (output)

   입력된 숫자 위 배열이 오름차순 조건을 만족하도록 재 배열하는 것

 

합병 정렬(Merge Sort)

 - 합병을 이용한 정렬 알고리즘

 - 두 개의 정렬된 배열이 주어졌을 때, 정렬된 하나의 배열로 합병

 - 각 배열의 가장 왼쪽에 있는 값을 비교해보면 가장 작은 수를 알 수 있다.

 

정렬을 하기에는 너무 큰 배열을 쪼개어 정렬한 후 합병한다. 이를 위해 합병 정렬을 필요한 것이다.

 

 

A divide-and-conquer approach

 크기가 커서 풀기 어려운 하나의 문제를 크기가 작아서 풀기 쉬운 여러 개의 문제로 바꾸어서 푸는 방법

 

Divide

 -  n keys를 두 개의 n/2 keys로 나눈다.

 

Conquer

 - 합병 정렬을 사용하여 두 개의 배열을 정렬한다.

 

Combine 

 - 두 개의 정렬된 배열을 하나로 합치는 과정 

크기가 1이 될때까지 나눈다.

여기서 n log n 이 나오는 이유는 거꾸로 생각해보면 이해하기 쉽다.

1에서 2배씩 몇 번 해 n이 나올까?

 

1 * 2^2 = n

2^2 = n

log2(2x)=log2(n) log2⁡(2x)=log2⁡(n)(양 변에 로그를 취했습니다.)

x=log2(n) x=log2⁡(n)

 

여기서 1은 n개 이므로 nlog2(n) 간단하게 nlogn이 나오는 것이다.