분할정복법(divide & conqver )
- 여러 알고리즘의 기본이 되는 해결방법으로, 기본적으로는 엄청나게 크고 방대한 문제를 조금씩 나눠가면서 용이하게 풀 수 있는 문제 단위로 나눈 다음 그것들을 다시 합쳐서 해결하자는 개념에서 출발했다.
- 합병정렬
-
하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트를 얻고자 하는 것
-
순환 호출의 깊이 k : logn ( 합병 단계수) / 하나의 합병단계 : n개의 비교연산
-
O(n) : n*logn
합병정렬 예시 코드는 다음과 같다.
#include <stdio.h>
int sorted[100],count;
void merge(int list[], int left,int mid, int right)
{
int i,j,k,l;
i=left;
j=mid+1;
k=left;
while(i<=mid && j<=right)
{
if(list[i]<=list[j])
{
sorted[k++]=list[i++];
}
else
{
sorted[k++]=list[j++];
}
}
if(i>mid)
{
for(l=j; l<=right; l++)
{
sorted[k++]=list[l];
}
}
else
{
for(l=i; l<=mid; l++)
{
sorted[k++]=list[l];
}
}
for(l=left; l<=right; l++)
{
list[l]=sorted[l];
}
}
void mergesort(int list[], int left,int right)
{
int mid;
if(left<right)
{
mid=(left+right)/2;
mergesort(list,left,mid);
mergesort(list,mid+1,right);
merge(list,left,mid,right);
}
}
int main()
{
int list[4]={27,12,20,25};
mergesort(list,0,3);
for(int i=0; i<4; i++)
{
printf("%d ",list[i]);
}
return 0;
}
mergesort 함수
mergesort 함수는 주어진 리스트를 재귀적으로 반씩 나누어 정렬하는 함수이다.
left는 현재 부분 리스트의 시작 인덱스, right는 끝 인덱스를 나타낸다.
left < right일 때, 중간 인덱스를 계산하고 (mid=(left+right)/2), 이를 기준으로 왼쪽과 오른쪽 부분 리스트를 나눠 각각 mergesort 함수를 호출하여 정렬한다.
나눈 리스트가 모두 정렬되면 merge 함수를 호출해 두 부분 리스트를 병합한다.
merge 함수
merge 함수는 두 개의 정렬된 부분 리스트를 하나의 정렬된 리스트로 병합하는 역할을 한다. 매개변수는 list (정렬할 배열), left (왼쪽 시작 인덱스), mid (중간 인덱스), right (오른쪽 끝 인덱스)이다.
i는 왼쪽 부분 리스트의 시작, j는 오른쪽 부분 리스트의 시작, k는 sorted 배열에 병합한 결과를 넣을 인덱스이다.
두 리스트의 현재 위치 값을 비교해 작은 값을 sorted에 넣고 인덱스를 증가시킨다.
한쪽 리스트가 다 채워졌으면 남은 다른 리스트의 값들을 sorted에 추가한다.
마지막으로 sorted 배열의 정렬된 값을 원래의 list에 복사한다.
따라서,이 코드는 합병 정렬 알고리즘을 사용하여 주어진 배열을 정렬한다. mergesort 함수로 배열을 재귀적으로 분할하고, merge 함수로 두 부분 리스트를 병합하여 정렬을 수행한다. 최종적으로 정렬된 배열을 출력한다.
