쌍방합병(two-way merging)이란 2개의 정렬된 배열을 하나의 정렬된 배열로 합하는 것을 의미한다. 합병 프로시저를 반복 적용하여 배열을 정렬할 수 있다. 예를 들면 16개 아이템을 가진 배열을 정렬하기 위해서, 각각 크기가 8인 2개의 부분배열로 분할한다. 같은 방법으로 크기가 8인 부분배열은 각각 크기가 4인 2개의 부분배열로 분할되고 궁극적으로 부분배열의 크기는 1이 되며, 크기가 1인 배열을 정렬하여 분할 된 횟수만큼 합병한다. 이 절차를 합병정렬이라고 하며, n개의 아이템을 가진 배열이 주어지면 합병정렬은 다음과 같은 절차로 진행된다.
<그림 2.1> 합병정렬 알고리즘의 수동적인 정렬절차
표 2.1을 보면 크기가 4인 두 개의 배열을 합병할 때 mergy 알고리즘이 어떻게 작동하는 지 보여준다.
*비교되는 아이템은 붉게 표시
이 재현식은 다음과 같이 풀 수 있다.
1. 분할 : 배열을 n/2개 아이템을 가진 2개의 부분배열로 분할한다.
2. 정복 : 정렬함으로써 각 부분배열을 정복한다. 배열이 충분히 작지 않으면 재귀 호출을 한다.
3. 통합 : 부분배열에 대한 답들을 합병하여 하나의 정렬된 배열로 만든다.
알고리즘 2.1 합병정렬)------------------------------------------------------
문제 : n개 키를 오름차순으로 정렬
입력 : 양의 정수 n, 키의 배열 Array(첨자 1부터 n까지)
출력 : 키가 오름차순으로 정렬된 배열 Array
입력 : 양의 정수 n, 키의 배열 Array(첨자 1부터 n까지)
출력 : 키가 오름차순으로 정렬된 배열 Array
void merge_Sort( keyword n, keyword Array[] )
{
if ( n > 1 ) {
const keyword h = ↓[n / 2];
Keyword m = n - h;
keyword Left[h-1], Right[m-1];
for ( keyword i = 1; i <= h; i++)
Left[i] = Array[i];
for ( keyword i = 1; i <= m; i++)
Right[i] = Array[h+i];
merge_Sort(h, Left);
merge_Sort(m, Right);
merge(h, m, Left, Right, Array);
}
}
{
if ( n > 1 ) {
const keyword h = ↓[n / 2];
Keyword m = n - h;
keyword Left[h-1], Right[m-1];
for ( keyword i = 1; i <= h; i++)
Left[i] = Array[i];
for ( keyword i = 1; i <= m; i++)
Right[i] = Array[h+i];
merge_Sort(h, Left);
merge_Sort(m, Right);
merge(h, m, Left, Right, Array);
}
}
------------------------------------------------------------------------
알고리즘 2.2 합병)---------------------------------------------------------
문제 : 2개의 정렬된 배열을 하나의 정렬된 배열로 합병
입력 : 양의 정수 h 와 m, 정렬된 키의 배열 Left(첨자 1부터 h까지),
정렬된 키의 배열 Right(첨자 1부터 m까지), 정렬된 키의 배열
출력 : Left와 Right의 키들을 모두 포함하여 정렬한 배열 Array(첨자 1부터 h+m까지)
입력 : 양의 정수 h 와 m, 정렬된 키의 배열 Left(첨자 1부터 h까지),
정렬된 키의 배열 Right(첨자 1부터 m까지), 정렬된 키의 배열
출력 : Left와 Right의 키들을 모두 포함하여 정렬한 배열 Array(첨자 1부터 h+m까지)
void merge( keyword h, keyword m, const keyword Left[],
const keyword right[], keyword Array[] )
{
keyword i, j, k;
i = 1; j = 1; k = 1;
while ( i <= h && j <= m) {
if ( Left[i] < Right[i] ) Array[k] = Left[i++];
else Array[k] = Right[j++];
k++;
}
if ( i > h) {
for ( keyword a = k; a <= h+m; a++)
Array[a] = Right[j];
}
else {
for ( keyword a = k; a <= h+m; a++)
Array[a] = Left[i];
}
}
const keyword right[], keyword Array[] )
{
keyword i, j, k;
i = 1; j = 1; k = 1;
while ( i <= h && j <= m) {
if ( Left[i] < Right[i] ) Array[k] = Left[i++];
else Array[k] = Right[j++];
k++;
}
if ( i > h) {
for ( keyword a = k; a <= h+m; a++)
Array[a] = Right[j];
}
else {
for ( keyword a = k; a <= h+m; a++)
Array[a] = Left[i];
}
}
------------------------------------------------------------------------
표 2.1을 보면 크기가 4인 두 개의 배열을 합병할 때 mergy 알고리즘이 어떻게 작동하는 지 보여준다.
표 2.1 2개의 배열 Left와 Right를 하나의 배열 Array로 합병하는 예
키를 비교하여 정렬을 수행하는 알고리즘의 경우, 비교명령과 지정명령은 각각 단위연산으로 여길 수 있다. 이 알고리즘에서 비교횟수는 h와 m에 좌우된다. 따라서 이 알고리즘의 시간복잡도를 구하기 위해 단위연산과 입력크기는 다음과 같이 놓는다.
* 단위연산 : Left[i]와 Right[j]의 비교
* 입력크기 : 두 입력 배열 아이템의 수, h와 m
* 입력크기 : 두 입력 배열 아이템의 수, h와 m
최악의 경우는 루프를 빠져나갈 때가 된다. 인덱스 중 하나는 빠져나가는 값에 도달한 반면에 다른 인덱스는 빠져나가지 못하는 값에 머물러 있는 경우이다. 이럴 경우 알고리즘 2.2의 시간복잡도는 W(h, m) = h + m -1 이다.
이를 이용하여 알고리즘 2.1의 시간복잡도를 구할 때 단위연산은 merge 알고리즘에서 일어나는 비교연산이다. 비교횟수는 h, m과 함께 증가하고, h와 m은 n과 함께 증가하므로, 단위연산과 입력크기는 다음과 같이 정한다.
* 단위연산 : merge 알고리즘에서 일어나는 비교연산
* 입력크기 : 배열 Array의 아이템의 수, n
* 입력크기 : 배열 Array의 아이템의 수, n
총 비교횟수는 Left를 입력으로 merge_Sort를 재귀 호출하는 데 수행되는 비교연산의 횟수, Right를 입력으로 merge_Sort를 재귀 호출하는 데 수행되는 비교연산의 횟수, 그리고 merge를 호출하는 데 수행되는 비교연산의 횟수의 합이다. 따라서 다음과 같이 된다.
W(n) = W(h) + W(m) + h + m -1
배열 Left 배열 Right 합병하는 데
정렬 시간 정렬 시간 걸린 시간
배열 Left 배열 Right 합병하는 데
정렬 시간 정렬 시간 걸린 시간
먼저 n이 2의 거듭제곱인 경우를 분석해 보면 에 대한 표현식은 다음과 같다.
W(n) = W(n/2) + W(n/2) + n -1
= 2W(n/2)+n-1
= 2W(n/2)+n-1
입력 크기가 1이면, 종료조건이 만족되고 합병은 이루어지지 않는다. 따라서 은 0이기 때문에 다음과 같은 재현식을 얻는다.
W(n) = 2W(n/2)+n-1 n>1이고, n이 2의 거듭제곱인 경우
W(1) = 0
이 재현식은 다음과 같이 풀 수 있다.
W(n) = nlgn-(n-1) ∈ θ(lgn)
참고 : Foundations of Algorithm, using C++ Pseudocode - 3rd Edition
[출처] 분할정복법 (합병정렬)|작성자 조똥꼬
Prev
Rss Feed