merged sort 혹은 합병정렬로 불리우는 이 정렬알고리즘은 O(nlogn)의 시간복잡도를 보여주는 정렬:::알고리즘(:12)이다. 기본적으로 합병정렬은 정렬이된 양쪽의 원소들을 합병하는 식으로 이루어진다. 이를 위해서 분할 정복 알고리즘을 사용한다.
아래의 visual:::sort(:12) 애플릿을 이용하면 합병정렬 알고리즘의 원리를 쉽게 이해할 수 있을 것이다. 아래의 애플릿을 보려면 JRE(:12)가 설치되어 있어야 한다.
합병정렬은 다음의 아이디어를 이용해서 실행시간을 줄이고 있다.
커다란 하나의 목록을 가진 정렬보다, 작은 목록을 가진 정렬이 더 빠르다.
이미 정렬된 두개의 목록을 정렬하는 데에는 매우 작은 시간이 소모된다. 왜냐하면 두개의 목록이 이미 정렬되어 있다면, 목록을 계속 증가시키면서, 다른 버퍼에 넣어주기만 하면 되기 때문이다.
만약 두개의 이미 정렬된 배열이 주어졌다면, 다음과 같은 방식으로 합병정렬을 구현할 수 있을 것이다. 아래는 C++(:12) 구현이다. 각각의 분할된 원소에 대해서 아래의 코드를 적용하면 될 것이다. 돌아가는데 큰 문제는 없는 코드이지만, 최적화 되지 않았다. 구현원리를 이해하는데 중점을 두었다.
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <vector>
using namespace std;
// Merged Sort에 사용될 데이터 객체
class Data
{
public:
int currentIdx;
int *data;
int size;
Data(int *indata, int insize = 0)
{
data = indata;
size = insize;
currentIdx = 0;
}
void Input(int a)
{
data[currentIdx] = a;
currentIdx++;
}
int Size()
{
if (size == 0)
return currentIdx;
return size;
}
};
// Merged Sort 클래스
class MergedSort
{
private :
int BUFSIZE;
int *buff;
Data *InputData;
int *buffIdx;
int flag;
int flagidx;
int inputsize;
Data *inputData;
Data *outputData;
vector<Data *> dataVector;
public :
MergedSort()
{
BUFSIZE = 30;
flag = 0;
flagidx = 0;
inputsize = 0;
};
void Sort(int *a, int *b, int sizea, int sizeb)
{
int bufsize;
int idx;
inputData = new Data(a, sizea);
dataVector.push_back(inputData);
inputData = new Data(b, sizeb);
dataVector.push_back(inputData);
buff = (int *)malloc(sizeof(int)*(sizea + sizeb));
memset(buff, 0x00, sizeof(int)*(sizea+sizeb));
outputData = new Data(buff);
bufsize = BUFSIZE - 1;
int topdoc = -1;
while(true)
{
idx = dataVector[flag]->currentIdx;
if (inputsize > bufsize)
{
printf("Input Buffer Excess\n");
break;
}
if (idx >= dataVector[flag]->size)
{
flagidx++;
flag = flagidx%2;
idx = dataVector[flag]->currentIdx;
int max = dataVector[flag]->size;
while(idx < max)
{
outputData->Input(dataVector[flag]->data[idx]);
idx++;
}
break;
}
if (dataVector[flag]->data[idx] > topdoc)
{
topdoc = dataVector[flag]->data[idx];
flagidx++;
flag = (flagidx)%2;
}
else if (dataVector[flag]->data[idx] == topdoc)
{
outputData->Input(dataVector[flag]->data[idx]);
dataVector[flag]->currentIdx++;
idx = dataVector[flag]->currentIdx;
topdoc = dataVector[flag]->data[idx];
flagidx++;
flag = flagidx%2;
dataVector[flag]->currentIdx++;
}
else
{
outputData->Input(dataVector[flag]->data[idx]);
dataVector[flag]->currentIdx++;
}
}
}
Data *get()
{
return outputData;
}
};
int main(int argc, char **argv)
{
MergedSort *DataSort;
Data *rtvData;
int a[] = {1, 5, 6, 8, 10, 22, 24, 29, 31, 33, 49, 50, 100, 200, 400, 410, 412, 413};
int b[] = {5, 10, 20, 30, 50, 51};
DataSort = new MergedSort();
DataSort->Sort(a, b, sizeof(a)/sizeof(int), sizeof(b)/sizeof(int));
rtvData = DataSort->get();
printf("Size is %d\n", rtvData->Size());
for (int i = 0; i < rtvData->Size(); i++)
{
printf("%d : %d\n", i, rtvData->data[i]);
}
}
합병정렬 (Merged Sort)
- 커다란 하나의 목록을 가진 정렬보다, 작은 목록을 가진 정렬이 더 빠르다.
- 이미 정렬된 두개의 목록을 정렬하는 데에는 매우 작은 시간이 소모된다. 왜냐하면 두개의 목록이 이미 정렬되어 있다면, 목록을 계속 증가시키면서, 다른 버퍼에 넣어주기만 하면 되기 때문이다.
만약 두개의 이미 정렬된 배열이 주어졌다면, 다음과 같은 방식으로 합병정렬을 구현할 수 있을 것이다. 아래는 C++(:12) 구현이다. 각각의 분할된 원소에 대해서 아래의 코드를 적용하면 될 것이다. 돌아가는데 큰 문제는 없는 코드이지만, 최적화 되지 않았다. 구현원리를 이해하는데 중점을 두었다.#include <stdlib.h> #include <stdio.h> #include <string.h> #include <vector> using namespace std; // Merged Sort에 사용될 데이터 객체 class Data { public: int currentIdx; int *data; int size; Data(int *indata, int insize = 0) { data = indata; size = insize; currentIdx = 0; } void Input(int a) { data[currentIdx] = a; currentIdx++; } int Size() { if (size == 0) return currentIdx; return size; } }; // Merged Sort 클래스 class MergedSort { private : int BUFSIZE; int *buff; Data *InputData; int *buffIdx; int flag; int flagidx; int inputsize; Data *inputData; Data *outputData; vector<Data *> dataVector; public : MergedSort() { BUFSIZE = 30; flag = 0; flagidx = 0; inputsize = 0; }; void Sort(int *a, int *b, int sizea, int sizeb) { int bufsize; int idx; inputData = new Data(a, sizea); dataVector.push_back(inputData); inputData = new Data(b, sizeb); dataVector.push_back(inputData); buff = (int *)malloc(sizeof(int)*(sizea + sizeb)); memset(buff, 0x00, sizeof(int)*(sizea+sizeb)); outputData = new Data(buff); bufsize = BUFSIZE - 1; int topdoc = -1; while(true) { idx = dataVector[flag]->currentIdx; if (inputsize > bufsize) { printf("Input Buffer Excess\n"); break; } if (idx >= dataVector[flag]->size) { flagidx++; flag = flagidx%2; idx = dataVector[flag]->currentIdx; int max = dataVector[flag]->size; while(idx < max) { outputData->Input(dataVector[flag]->data[idx]); idx++; } break; } if (dataVector[flag]->data[idx] > topdoc) { topdoc = dataVector[flag]->data[idx]; flagidx++; flag = (flagidx)%2; } else if (dataVector[flag]->data[idx] == topdoc) { outputData->Input(dataVector[flag]->data[idx]); dataVector[flag]->currentIdx++; idx = dataVector[flag]->currentIdx; topdoc = dataVector[flag]->data[idx]; flagidx++; flag = flagidx%2; dataVector[flag]->currentIdx++; } else { outputData->Input(dataVector[flag]->data[idx]); dataVector[flag]->currentIdx++; } } } Data *get() { return outputData; } }; int main(int argc, char **argv) { MergedSort *DataSort; Data *rtvData; int a[] = {1, 5, 6, 8, 10, 22, 24, 29, 31, 33, 49, 50, 100, 200, 400, 410, 412, 413}; int b[] = {5, 10, 20, 30, 50, 51}; DataSort = new MergedSort(); DataSort->Sort(a, b, sizeof(a)/sizeof(int), sizeof(b)/sizeof(int)); rtvData = DataSort->get(); printf("Size is %d\n", rtvData->Size()); for (int i = 0; i < rtvData->Size(); i++) { printf("%d : %d\n", i, rtvData->data[i]); } }참고 문헌
Recent Posts
Archive Posts
Tags