분할정복법
merge sort
quick sort
= 분할 정복법
heap sort
분할 : 해결하고자 하는 문제를 작은 크기의 동일한 문제들로 분할
[더 작은 크기의 동일한 문제로 분할해야 한다]
정복 : 각각의 작은 문제를 순환적으로 해결
합병 : 작은 문제의 해를 합하여(merge) 원래 문제에 대한 해를 구함
합병정렬(merge sort)
분할 divide - 데이터가 저장된 배열을 절반으로 나눔
정복 recursively sort - 각각을 순환적으로 정렬
합병 merge - 정렬된 두 개의 배열을 합쳐 전체를 정렬
나누고 - 정렬하고 - 합치고 반복
제일 중요한 것이 merge 인데
이미 정렬된 두 개의 배열이 있을 경우
i와 j를 합치기 위해서는 추가적인 배열 k를 생성해서
i의 [0] 과 j의 [0] 중 가장 작은 값을 k의 [0]에 두고 (만약 i[0]이 j[0]보다 작다면)
i의 [1] 과 j의 [0] 중 가장 작은 값을 k의 [1]에 두고
...
이런 식으로 정렬을 한다.
만약 i 배열이 j 배열보다 먼저 완료될 경우에는 j의 나머지를 k에 붙인다.
수도코드
mergesort(A[], p, r) { //A[p...r] 을 정렬한다
if (p<r) then{
q <- (p+q)/2; ...1) p,q의 중간 지점 계산
mergesort(A, p, q); ...2) 전반부 정렬
mergesort(A, q+1, r); ...3) 후반부 정렬
merge(A, p, q, r); ...4) 합병
}
}
merge(A[], p, q, r){
정렬되어 있는 두 배열 A[p...q]와 A[q+1...r]을 합하여
정렬된 하나의 배열 A[p...r]을 만든다.
}
코드
void merge(int data[], int p, int q, int r){
int i = p, j=q+1, k=p;
int tmp[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];
}
}
시간 복잡도
T(n) = 0 if n =1
T(┌n/2┐) + T(└n/2┘) + n otherwise.
n개의 데이터를 정렬하기 위해서 n개의 데이터를 /2 해야 하니까
n + n/2 + n/2 (두번 잘라서 사용해야 하니까)
T(n) = 2T(n/2) + n
mergesort가 일어나는 과정을 생각해 보면
n 길이를 n/2 n/2로 나누고 나서 merge 해서 전체를 정렬하는 방식인데
n/2 를 정렬하는데 걸리는 시간은 n을 넘지 않음
그런데 n/2는 또 n/4로 쪼개야 하니까 n/4 n/4가 됨
n/4 를 정렬하는데 걸리는 시간은 n/2를 넘지 않음
이렇게 전체적으로 아래로 내려갈수록 똑같이 비교 연산의 횟수가 n으로 되는데
길이가 n인 배열을 길이가 1인 각각 배열로 쪼개려면 트리 레벨이 logN이 된다.
그러므로 merge sort에 필요한 비교연산의 횟수가 총 n * log n이 된다.
시간 복잡도 : O(nLogn)
댓글
댓글 쓰기