반응형
Merge Sort 합병정렬
- 개념
- 분할 정복(divide and conquer) 방법의 하나의 예
-> 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략.
- 합병정렬은 하나의 리스트를 두 개의 균등한 크기로 분할하고, 분할된 부분 리스트를 정렬한 다음
두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트를 얻고자 하는 것.
- bottom-up 방식 (아래에서 위로 올라가서 결과가 됨)
- 1단계 : n개의 데이터를 1개로 다 자른다.
2단계 : 토너먼트 형식으로 데이터 두 개를 하나로 붙인다. 붙일 때 정렬을 하며 붙임.
반복 : 데이터의 원소가 2개 있는 각각의 2개의 데이터를 하나로 붙인다.
반복 : 데이터의 원소가 4개 있는 부분집합을 8개로 붙인다.
- 시간복잡도
비교횟수를 카운트해서 시간 복잡도를 계산해보자!
- 비교연산 횟수 계산 과정 :
아래에서 위로 올라가면서 계산해보자. bottom-up 방식
크기 n/8인 부분배열 2개를 합병하는 데 최대 (n/8)번의 비교 연산이 필요하고, 8쌍의 부분배열에 반복한다.
따라서 총 (n/8)번 *8쌍 = n번의 비교를 한다.
크기 n/4인 부분배열 2개를 합병하는 데 최대 (n/4)번의 비교 연산이 필요하고, 4쌍의 부분배열에 반복한다.
따라서 총 (n/4)번 *4쌍 = n번의 비교를 한다.
크기 n/2인 부분배열 2개를 합병하는 데 최대 (n/2)번의 비교 연산이 필요하고, 2쌍의 부분배열에 반복한다.
따라서 총 (n/2)번 *2쌍 = n번의 비교를 한다.
이를 일반화하면 한 회 merge할 때마다 최대 n번의 비교 연산을 수행함을 알 수 있다.
그러면 이 횟수를 몇 차례 반복하면 정렬은 끝날까? 부분집합의 원소가 하나에서부터 n개가 될 때까지.
총 log_2_n 횟수 반복한다.(순한 호출의 깊이, 합병 단계의 수)
따라서 전체 비교 횟수는 n*log_2_n으로 O(nlog(n)) 이라고 표현할 수 있다.
- 합병정렬은 최적, 최악, 평균 속도를 가리지 않고 항상 일정한 속도를 낸다.
- 그러나 단점으로 추가적인 리스트(저장공간)이 필요하다. -> 제자리 정렬(in-place sorting)이 아니다.
- 레코드들의 크기가 큰 경우에는 이동 횟수가 많으므로 매우 큰 시간적 낭비를 초래한다.
- C언어 구현코드
#include<stdio.h>
#include<stdlib.h>
#include<string.h> // memcpy
#define SZ 10
int data[SZ] = {34, 32, 2, 3, 0, 1, 8, 10, 99, 7};
void showDate(int *_data) {
for (int i = 0; i < SZ; i++) {
printf("%d ",_data[i]);
}
printf("\n");
}
// first_start
// second_start
int doMerge(int *copied_data, int f_s, int f_e, int s_s, int s_e, int dst_idx) {
int f = f_s; // first_start
int s = s_s; // second_start
while (f<=f_e && s<=s_e) {
if (data[f] <= data[s]) {
copied_data[dst_idx] = data[f];
f++;
dst_idx++;
}
else {
copied_data[dst_idx] = data[s];
s++;
dst_idx++;
}
}
// 앞의 블럭에 숫자가 남아 있는 경우,
// 남은 것을 모두 복사해서 붙인다.
while (f<=f_e) {
copied_data[dst_idx] = data[f];
f++;
dst_idx++;
}
// 뒤의 블럭에 숫자가 남아 있는 경우,
// 남은 것을 모두 복사해서 붙인다.
while (s <= s_e) {
copied_data[dst_idx] = data[s];
s++;
dst_idx++;
}
// 종료할 때는, 다음 붙일 위치를 반환한다.
return dst_idx;
}
int main(void) {
printf("------------------before merge sorting---------------------\n");
showDate(data);
// data의 copy본을 하나 만든다.
int *copied_data = (int*)malloc(sizeof(int)*SZ);
memcpy(copied_data, data, sizeof(int)*SZ);
int step = 1; // 길이 1개 짜리 블럭부터 시작
int dst_idx = 0; // 복사 위치는 0부터 시작
while (1) {
//탈출조건
if (step gt; =SZ) {
break;
}
// step1: 0,2,4
// step2 : 0,4,
// step4 : 0,8
// step의 2배수씩 커짐
for (int i = 0; i < SZ; i=i+2*step) { // 0, 0+2, 0+2+4, 0+2+4+8
int _f_s = i;
int _f_e = i + step-1;
int _s_s = i + step; // _f_e + 1;
int _s_e = i + step + step - 1; // _s_s + step;
//
if (_f_e >= SZ-1) { // merge할 것이 1덩어리 밖에 없음.
break;
}
if (_s_e > SZ-1) { // 한 쪽 덩어리가 step사이즈보다 작으면 _s_e를 다시 지정해줌.
_s_e = SZ - 1;
}
dst_idx = doMerge(copied_data,_f_s,_f_e,_s_s,_s_e,dst_idx);
}
step = step * 2;
dst_idx = 0;
memcpy(data,copied_data,sizeof(int)*SZ);
}
printf("------------------after merge sorting---------------------\n");
showDate(copied_data);
return 0;
}
- 실행 결과
반응형