합병 정렬(merge sort)
2개의 정렬된 리스트를 하나의 정렬된 리스트로 합병하여 정렬하는 정렬기법.
while 루프를 반복할 때 마다 k는 1씩 증가. k의 총 증가량 n-1+1
for 명령문은 최대 n-i+1 레코드를 복사한다.
레코드 길이 s 가 1보다 클 때 배열 대신 연결 리스트를 이용하면 이들 n-l+1 레코드를 포함한 새로운 정렬된 연결 리스트를 얻을 수 있다.
merge 함수에서 배열 mergedList 가 필요한 n-l+1 개의 레코드 공간이 필요 없게 된다. 대신 n-l+1 개의 링크에 대한 공간이 필요하다.
void merge(element initList[], element mergedList[], int i, int m, int n)
{
int j, k, t;
j = m + 1; // 2번째 배열의 인덱스
k = i; // 합병 리스트 인덱스
while (i <= m && j <= n) {
if (initList[i].key <= initList[j].key)
mergedList[k++] = initList[i++];
else
mergedList[k++] = initList[j++];
}
if (i > m)
/* mergedList[k:n] =initList[j:n]*/
for (t = j; t <= n; t++)
mergedList[t] = initList[t];
else
/*mergedList[k:n] = initList[i:m]*/
for (t = i; t <= m; t++)
mergedList[k + t - i] = initList[t];
}반복 합병 정렬(iterative merge sort)
입력 리스트를길이가 1인 n개의 정렬된 서브리스트로 간주하는 것으로 시작한다.
첫 번째 합병 단계에서는 이 리스트들을 쌍으로 합병하여 크기가 2인 n/2개의 리스트를 얻는다.
(n이 홀수이면 리스트 하나의 크기는 1이 된다.)
두 번째 합병 단계에서는 이 n/2개의 리스트를 다시 쌍으로 합병하여 n/4개의 리스트를 얻는다. 한번 합병할 때마다 서브리스트의 수는 반으로 줄어든다.
합병 단계는 하나의 서브리스트가 남을 때까지 계속한다.
합병 정렬은 여러 개의 합병 단계(pass)로 구현되기 때문에 합병 단계를 수행하는 함수를 작성해야한다.
패스 함수
void mergePass(element initLIst[], element mergedList[], int n, int s)
{
int i, j;
for (i = i; i <= n - 2 * s + 1; i += 2 * s)
merge(initLIst, mergedList, i, i + s - 1, i + 2 * s - 1);
if (i + s - 1 < n)
merge(initList, mergedList, i, i + s - 1, n);
else
for (j = i; j <= n; j++)
mergedList[j] = initLIst[j];
}합병 정렬 함수
void mergeSort(element a[], int n) { int s = 1; //현재 아규먼트 사이즈 element extra[MAX_SIZE]; while (s < n) { mergePass(a, extra, n, s); s *= 2;//반복 합병 정렬은 반씩 쪼개는 작업 mergePass(extra, a, n, a); a *= 2; } }
순환 합병 정렬(Recursive Merge Sort)
순환적 방법에서는 정렬할 리스트를 거의 똑같이 2개로 나누어 left 서브리스트와 right 서브리스트로 만든다. 이 서브리스트들은 순환적으로 정렬되고 정렬된 서브리스트들은 합병된다.
Downward 를 통해 큰 리스트를 작은 단위로 나눈다.
Downward 하여 나눠준 다음 upward 로 올라오면서 정렬해준다.
rmergeSort() 순환 합병 정렬
int rmergeSort(element a[], int link[], int left, int right)
{
if (left >= right) return left;
int mid = (left + right) / 2; 적당히 반으로 잘라준다.
return listMerge(a, link, //Downward 에 해당 부분
rmergeSort(a, link, left, mid),
/* 왼쪽 반 정렬*/
rmergeSort(a, link, mid + 1, right));
/* 오른쪽 반 정렬*/
}정렬된 체인의 합병
int listMerge(element a[], int link[], int start1, int start2)
{
int last1, last2, lastResult = 0;
for (last1 = start1, last2 = start2; last1 && last2;)
if (a[last1] <= a[last2]) {
link[lastResult] = last1;
lastResult = last1; last1 = link[last1]];
}
else {
link[lastResult] = last2;
lastResult = last2; last2 = link[last2];
}
if (last == 0) link[lastResult] = last2;
else link[lastResult] = last1;
return link[0];
}단점 : list 라는 추가적이 배열이 필요하므로 추가적인 작업이 필요하다.
시간 복잡도
O(nlogn)
실습 예제
주어진 데이터를 읽어 Iterative Merge Sort와 Recursive Merge Sort 를 각각 수행하라.
1) 입력 데이터는 다음과 같은 형식을 가지는 파일(input.txt)로부터 입력받는다.
N R 1,1 R 1,2
R 2,1 R 2,2
…
R N,1 R N,2
N: Record의 갯수이며, N≤1000라 가정한다.. Ri, j 는 정수이며, i번째 Record의 j번 field를 나타낸다.
2) Iterative Merge Sort를 이용하여 두개의 Key(K 1 , K 2 )에 대해 각각 오름 차순으로 정렬한다
.
3) Recursive Merge Sort를 이용하여 두개의 Key(K 1 , K 2 )에 대해 각각 오름 차순으로 정렬한다.
입력값
input.txt
8
-1 5
31 4
95 -9
82 3
1984 124
-78 -42
0 -154
525 195
코드
/*
Description : Iterative Merge Sort , Recursive Merge Sort 구현
*/
#include <stdio.h>
#include <stdlib.h>
#include <Windows.h>
#define KEY1 1
#define KEY2 2
#define MODE_ITER 0
#define MODE_RE 1
typedef struct element
{
int key1;
int key2;
}element;
void open();
void Init(element[], element[]);
int rmergeSort(element[], int[], int, int, int);
int listMerge(element[], int[], int, int, int);
void merges(element[], element[], int i, int m, int n, int);
void mergePass(element[], element[], int n, int s, int);
void mergeSort(element[], int n, int);
void Printarr(element[], int, int);
void COLOR(int);
element *matric;
int N;
int *link;
int main(void)
{
open();
element *temp1, *temp2;
temp1 = (element*)malloc(sizeof(element) * (N + 1));
temp2 = (element*)malloc(sizeof(element) * (N + 1));
link = (int*)malloc(sizeof(int)*(N + 1));
for (int i = 1; i <= N; i++) //link 0으로 초기화
link[i] = 0;
COLOR(14);
printf("Iterative Merge Sort\n");
Init(temp1, temp2); //초기화
mergeSort(temp1, N, KEY1);
Printarr(temp1, 1, MODE_ITER);
mergeSort(temp2, N, KEY2);
Printarr(temp2, 2, MODE_ITER);
Init(temp1, temp2); //초기화
COLOR(14);
printf("\nRecursive Merge Sort\n");
rmergeSort(temp1, link, 1, N, 1);
Printarr(temp1, 1, MODE_RE);
for (int i = 0; i <= N; i++) //link 0 으로 초기화
link[i] = 0;
rmergeSort(temp2, link, 1, N, 2);
Printarr(temp2, 2, MODE_RE);
return 0;
}
void open()
{
FILE *fp = fopen("input.txt", "r");
fscanf(fp, "%d", &N);
matric = (element*)malloc(sizeof(element) * (N + 1));
int i = 1;
while (fscanf(fp, "%d %d", &matric[i].key1, &matric[i].key2) != EOF)
i++;
fclose(fp);
}
void COLOR(int color)
{
SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), color);
}
void Init(element temp1[], element temp2[])
{
for (int i = 1; i <= N; i++)
{
temp1[i] = matric[i];
temp2[i] = matric[i];
}
}
int rmergeSort(element a[], int link[], int left, int right, int KEY)
{
if (left >= right) return left;
int mid = (left + right) / 2;
return listMerge(a, link, rmergeSort(a, link, left, mid, KEY), rmergeSort(a, link, mid + 1, right, KEY), KEY);
}
int listMerge(element a[], int link[], int start1, int start2, int KEY)
{
int last1, last2, lastResult = 0;
if (KEY == 1)
{
for (last1 = start1, last2 = start2; last1&&last2;)
if (a[last1].key1 <= a[last2].key1) {
link[lastResult] = last1;
lastResult = last1; last1 = link[last1];
}
else {
link[lastResult] = last2;
lastResult = last2; last2 = link[last2];
}
if (last1 == 0) link[lastResult] = last2;
else link[lastResult] = last1;
return link[0];
}
else
{
for (last1 = start1, last2 = start2; last1&&last2;)
if (a[last1].key2 <= a[last2].key2) {
link[lastResult] = last1;
lastResult = last1; last1 = link[last1];
}
else {
link[lastResult] = last2;
lastResult = last2; last2 = link[last2];
}
if (last1 == 0) link[lastResult] = last2;
else link[lastResult] = last1;
return link[0];
}
}
void Printarr(element arr[], int key, int mode)
{
if (mode == 0)
{
COLOR(13);
printf("\nKey : %d\n\n", key);
COLOR(15);
for (int i = 1; i <= N; i++)
printf("%d %d\n", arr[i].key1, arr[i].key2);
}
else
{
COLOR(13);
printf("\nKey : %d\n\n", key);
COLOR(15);
for (int i = link[0]; i != 0; i = link[i])
printf("%d %d\n", arr[i].key1, arr[i].key2);
}
}
void mergeSort(element a[], int n, int KEY)
{
int s = 1;
element *temp;
temp = (element*)malloc(sizeof(element)*N);
while (s < n) {
mergePass(a, temp, n, s, KEY);
s *= 2;
mergePass(temp, a, n, s, KEY);
s *= 2;
}
}
void mergePass(element initList[], element mergedList[], int n, int s, int KEY)
{
int i, j;
for (i = 1; i <= n - 2 * s + 1; i += 2 * s)
merges(initList, mergedList, i, i + s - 1, i + 2 * s - 1, KEY);
if (i + s - 1 < n)
merges(initList, mergedList, i, i + s - 1, n, KEY);
else
for (j = i; j <= n; j++)
mergedList[j] = initList[j];
}
void merges(element initList[], element mergedList[], int i, int m, int n, int KEY)
{
int j, k, t;
j = m + 1;
k = i;
if (KEY == 1)
{
while (i <= m && j <= n)
{
if (initList[i].key1 <= initList[j].key1)
mergedList[k++] = initList[i++];
else
mergedList[k++] = initList[j++];
}
}
else
{
while (i <= m && j <= n)
{
if (initList[i].key2 <= initList[j].key2)
mergedList[k++] = initList[i++];
else
mergedList[k++] = initList[j++];
}
}
if (i > m)
for (t = j; t <= n; t++)
mergedList[t] = initList[t];
else
for (t = i; t <= m; t++)
mergedList[k + t - i] = initList[t];
}출력 값
정렬 알고리즘 관련 글