정렬 (sort)
- 정렬의 종류
◇ 삽입법 : 삽입정렬, 쉘정렬
◇ 선택법 : 선택정렬, 힙정렬
◇ 교환법 : 버블정렬, 힙정렬
◇ 병합법 : 병합정렬
◇ 기타 : 카운트 정렬
- 알고리즘별 속도 비교
|
|
최악 |
평균 |
최선 |
추가 메모리 |
|
버블 정렬 |
O(n^2) |
O(n^2) |
O(n^2) |
필요 없음 |
|
선택 정렬 |
O(n^2) |
O(n^2) |
O(n^2) |
필요 없음 |
|
삽입 정렬 |
O(n^2) |
O(n^2) |
O(n) |
필요 없음 |
|
퀵 정렬 |
O(n^2) |
O(n log n) |
O(n log n) |
필요 없음 |
|
합병 정렬 |
O(n log n) |
O(n log n) |
O(n log n) |
원소 수 만큼 |
|
힙 정렬 |
O(n log n) |
O(n log n) |
O(n log n) |
필요 없음 |
여기서 데이터 갯수가 5000개 일 때의 속도를 계산해보면
▷ 버블, 선택, 삽입 : O( n^2 ) = 25000000
▷ 쉘 정렬 : O(n^1.2) = 약 27464
▷ 퀵정렬 : O(n log n) = 약 18495
이론상 가장 빠른 속도는 O(n log n)이다.
위의 표를 보면 힙 정렬과 합병정렬이 모든 경우에 있어 가장 빠른 속도를 보이는 것을 알 수 있다.
하지만 추가적인 메모리 사용에 있어 힙 정렬이 더 유리하다. 그렇지만 힙 정렬이 모든 경우에
다 좋은 것은 아니다. 버블 정렬 같은 경우 간단한 알고리즘으로 인해 소스가 가장 짧지만
힙 정렬이나 합병정렬은 소스가 길어졌다.
(소스코드에서 힙정렬과 병합정렬을 제외하고)
위의 값에서 보면 알겠지만, 퀵정렬이 가장 빠르고 다음이 쉘정렬, 나머지가 이론상으로는 제일 느리다. 하지만 이 값들은 정렬할 자료의 양이나 초기의 배열상태에 따라 다를 수가 있다.
바꿔 말해서 자료의 양이 한 10이고 몇 개밖에 안 흐뜨러져 있으면 오히려 퀵정렬의 속도가
다른 것보다 느려질 수 있다. 그래서 자신이 사용할 자료의 성격을 잘 파악한 뒤에 가장 효율적인
알고리즘을 선택해야 한다.
참고로 프로파일링을 해본 결과는 다음과 같다.(자료는 랜덤으로 생성시켰고, 갯수는 5000개이다.)
|
Func Time |
Function |
|
1302.544 |
Bubble |
|
715.201 |
Select |
|
495.086 |
Select2 |
|
96.696 |
Insert |
|
0.226 |
Shell |
|
0.001 |
Quick |
- 힙 정렬 (Heap Sort)
void heap_sort(int *list, int n)
{
int i, temp;
for(i=(n/2); i>=1; i--) // 초기 히프 만들기
adjust(list, i, n);
for(i=(n-1); i>=1; i--) { // 히프 정렬의 두 번째 단계
temp = list[i+1]; // 마지막 노드와 뿌리 노드의 교환
list[i+1] = list[1];
list[1] = temp;
adjust(list, 1, i); // i개의 키에 대하여 adjust 적용
}
}
void adjust(int *list, int i, int n)
// i : adjust 알고리즘을 시작하는 노드의 인덱스
// n : 전체 노드의 개수
{
int j, k, done;
done = 0; // 아직 끝나지 않았음을 표시
k = list[i]; // 뿌리 노드의 값, 즉 옮겨야 할 원소의 값
j = 2 * i; // i 노드의 좌 자 노드
while ((j <= n) && (!done)) { // 자식노드가 있고 not done일 때까지 반복
if ( j < n) // j + 1 <= n 과 마찬가지인데 우 자 노드의 존재를 검사
if (list[j] < list[j + 1])
j ++; // 자 노드들 중 큰 노드를 선택
if (k >= list[j])
done = 1; // 자 노드보다 크므로 수행을 중단
else{
list[j / 2] = list[j]; // 자 노드를 부노드로 끌어 올림,
// 자 노드에 k 값을 쓰지 않는 이유는 나중에
// 수행이 다 끝난 다음에 쓰기 때문임.
j *= 2;
}
}
list[j / 2] = k; // 수행이 끝나면 찾아낸 위치에 맨 처음 저장한 뿌리 노드의 값을 저장
}
- 병합정렬 (Merge Sort)
#define MAXLENGTH 1024
void merge_sort(int *list, int n)
{
int len;
int temp[MAXLENGTH]; // 중간에 저장을 위해 사용하는 기억 장소
len = 1; // 처음 합병할 리스트들의 길이는 1이다.
while (len < n) { // 합병된 리스트의 길이가 n이 될 때까지 반복
merge_pass(list, temp, n, len); // x에 저장된 리스트를 y에 합병
// 이 과정이 끝나고 나면 리스트 전체가 y 에 들어가 있기 때문에 이를
// 다시 x로 옮겨야 한다. 이 때 그냥 복사하는 것이 아니고
// merge_pass를 통해서 한 단계 더 정렬을 시도한다.
len *= 2; // 한 번의 merge_pass 후에는 합병할 리스트의 길이가 2 배가 된다.
merge_pass(temp, list, n, len); // y에 저장된 리스트를 x에 합병
len *= 2;
// 다시 x에 저장이 된다.
}
}
void merge_pass (int *x, int *y, int n, int len)
{
int i, j;
i = 1;
while (i <= (n - 2 * len + 1)) {
// 윗 줄에서 n - 2 * len+ 1은 길이가 len인 두 개의 리스트가
// 존재할 때 까지를 의미한다. 만약 i 가 n - 2 * len+ 1 보다 크게 되면
// 처리하고 남아 있는 부분이 길이가 length인 두 개의 리스트를
// 형성하지 못한다. 이럴 경우는 다른 방식으로 처리해야하기 때문에
// while 루프의 조건문이 이렇게 형성되어 있다.
// i + len- 1은 첫번째 리스트의 마지막 인덱스이고,
// i + 2 * len- 1은 두번째 리스트의 마지막 인덱스이다.
twoway_merge (x, y, i, i + len- 1, i + 2 * len- 1);
i += 2 * len; // i 는 len의 2 배만큼씩 증가시킨다.
}
if ((i + len- 1) < n)
// 남은 두 리스트를 합병하는데 두 번째 리스트의 마지막 인덱스는
// n 이 된다. 따라서 두 번째 리스트는 길이가 len보다 작게 된다.
twoway_merge (x, y, i, i + len - 1, n);
else {
// 길이가 len보다 작은 리스트가 없는 경우는 그냥 복사한다
for (j = i; j <= n; j++)
y[j] = x[j];
}
}
void twoway_merge(int *x, int *z, int l, int m, int n)
{
int i, j, k, t;
i = l; // 첫 번째 리스트의 시작 인덱스
j = m + 1; // 두 번째 리스트의 시작 인덱스
k = l; // 합병 결과를 저장할 리스트의 시작 인덱스,
// 이 인덱스는 주어진 내용이 l 부터 n 까지를 합병하는 것이기
// 때문에 새로운 리스트에서도 l 부터 합병해야 한다.
while ((i <= m ) && ( j <= n)) { // 두 리스트 중 하나가 끝날 때까지 반복
if (x[i] <= x[j]) { // 첫 번째 리스트가 작은 경우
z[k] = x[i];
i++; // 인덱스 이동
} else { // 두 번째 리스트가 작은 경우
z[k] = x[j];
j++; // 인덱스 이동
}
k++;
}
if (i > m) // 첫 번째 리스트는 다 사용했음을 의미함
for (t = j; t <= n; t++)
z[k + t - j] = x[t]; // 두 번째 리스트를 복사
else
for (t = i; t <= m; t++)
z[k + t - i] = x[t]; // 두 번째 리스트를 복사
}
- 카운트 정렬
원리
정렬을 한다는 것은 사실상 원소를 재배치하는 작업을 말합니다. 즉 정렬하기 전에 있었던 위치에서
새로운 위치로 이동하는 것이죠. 그러데 그 이동하는 규칙은 무엇일까요? 바로 자신보다 작은 원소는
모두 자신 앞에 위치해야 하고, 큰 원소는 모두 뒤에 위치해야 한다는 것 아닐까요?
따라서 정렬이 끝난 후 새로 배치될 자신의 위치는 자신보다 작은 원소 개수에 의존한다는 것을 알 수
있죠. 여기서 '의존한다'라는 추상적인 단어를 사용했는데, 정확히 말하면 자신보다 작은 원소 개수에다
1을 더한 위치에 존재하는 것입니다. 이 카운트 정렬은 바로 앞서 설명한 원리를 이용한 것입니다.
typedef struct data_ {
int key;
int count;
} data;
void count_all(data *list, int n)
{
int i, j;
for(i=1; i<=n; i++)
for(j=1; j<i; j++) {
if(list[i].key > list[j].key)
list[i].count++;
else
list[j].count++;
}
}
// 메모리를 더 사용하는 알고리즘
void count_sort1(data *x, int n)
{
int i;
data y[MAXDATA];
for(i=1; i<=n; i++)
y[i] = x[i];
count_all(y, n);
for(i=1; i<=n; i++)
x[y[i].count+1] = y[i];
}
// 메모리를 더 사용하지 않는 방법
void count_sort2(data *list, int n)
{
int i, k;
count_all(list, n); // count를 한다.
for(i=1; i<n; i++) {
k = list[i].count+1; // i 번째 원소가 들어갈 위치 계산
while(k!=i) { // i 번째 원소가 제 위치에 있지 않을 경우
swap(list[i], list[k]); // 두 원소의 위치를 바꾼다.
k = list[i].count+1;
}
}
}
- 버블정렬 (Bubble Sort)
순서
1. 우선 맨 처음에 모든 원소들의 최대값을 찾으려면 맨 처음 원소와 둘째 원소를 비교한다.
만약 앞의 원소가 뒤의 원소보다 크면 두 원소의 자리를 바꾼다.
2. 둘째 원소와 셋째 원소를 비교해 자리를 바꾼다.
3. 이 과정을 마지막 원소까지 반복하면 맨 마지막 자리에 제일 큰 원소가 자리잡게 된다.
4. 최대값을 가진 원소를 제외하고 나머지에 대해서 이 과정을 반복하면 그 다음으로 큰 원소를
찾아내 마지막에서 둘째 자리에 넣게 된다.
5. 과정을 끝까지 반복하면 모든 원소가 오름차순으로 정리된다.
void Bubble(int item[], int count)
{
register int i, j, temp;
for(i=0; i<count-1; i++) {
for(j=0; j<count-i-1; j++) {
// 오름차순이 되게 비교를 하여 데이터 교환
if(item[j] > item[j+1]) {
temp = item[j];
item[j] = item[j+1];
item[j+1] = temp;
}
}
}
}
- 선택정렬 (Select Sort)
void Select(int item[], int count)
{
register int i, j, temp;
for(i=0; i<count-1; i++) {
for(j=i+1; j<count; j++) {
// 비교한 후 교환
if(item[i] > item[j]) {
temp = item[j];
item[j] = item[i];
item[i] = temp;
}
}
}
}
위의 함수를 보면 버블정렬과 거의 외관상 비슷하다. 하지만 위와 같이 만들면 좀 비합리적이다.
좀 유심히 살펴보면 알겠지만 킷값보다 작은 것이 나타나서 자리바꿈이 일어난 뒤에도 계속 비교를
하여 또 작은 것이 나타나면 같은 일(자리바꿈)을 반복하게 된다. 그래서 안쪽 루프를 돌면서 자리바꿈을
하지 말고, 단지 일어날 가장 최대치의 자리만 기억했다가 루프를 빠져나오면서 그 일을 하면 한번만
하게 되어 좀더 속도를 빠르게 할 수 있다. 그 개선된 함수는 다음과 같다.
- 개선된 선택정렬
void Select2(int item[], int count)
{
register int i, j, temp, k;
for(i=0; i<count-1; i++) {
k = i;
temp = item[i];
for(j=i+1; j<count; j++) {
if(temp > item[j]) {
// 자리바꿈할 위치를 기억
k = j;
temp = item[j];
}
}
// 기억한 자리에서 자리바꿈
item[k] = item[i];
item[i] = temp;
}
}
- 삽입정렬 (Insert Sort)
void Insert(int item[], int count)
{
register int i, j, temp;
for(i=0; i<count; i++) {
temp = item[i]; // 삽입할 키값을 기억
j = i-1; // j는 삽입시 뒤로 밀려나는 것의 위치
while(j >= 0 && item[j] > temp) {
item[j+1] = item[j];
j--;
} // 삽입할 위치 결정및 뒤로 이동시키는 작업을 함
item[j+1] = temp;
}
}
- 쉘정렬 (Shell sort)
void Shell(int item[], int count)
{
register int begin, inc=count;
do {
inc = inc/3+1; // 간격을 계산한다.
for(begin=0; begin<inc; begin++)
InsertSort(begin, inc, item, count);
// 계산된 간격으로 삽입정렬을 한다.
} while(inc>1);
}
// 쉘정렬에 사용된 삽입정렬
void InsertSort(int start, int inc, int item[], int count)
{
register int i, j, temp;
for(i=start; i<count; i+=inc) {
temp = item[i];
j = i-inc;
while(j >= 0 && item[j] > temp) {
item[j+inc] = item[j];
j-=inc;
}
item[j+inc] = temp;
}
}
- 퀵정렬 (Quick Sort)
순서
1. 어떤 특정 값을 기준으로 한 리스트를 두 개의 리스트로 분할한다. 그 중 한 리스트에는 그 기준값보다
작은 원소만 존재하고, 다른 리스트에는 그 기준값보다 큰 원소만 존재하도록 리스트를 분할한다.
2. 분할된 2개의 리스트를 또 다시 1과 같은 방식으로 분할한다.
3. 이 과정을 모든 리스트의 크기가 1이 될 때까지 반복하면 정렬이 완료된다.
void Quick(int item[], int count)
{
qs(item, 0, count-1);
}
void qs(int item[], int left, int right)
{
register int i=left, j=right+1, pivot, temp;
pivot = item[left]; // 비교할 중간의 값을 맨 왼쪽에서 따옴
// 재귀호출의 BASE CASE
if(left<right) {
do {
// 자리바꿈할 위치를 찾는다.
do i++; while(item[i] < pivot);
do j--; while(item[j] > pivot);
// 자리바꿈을 한다.
if(i<j) {
temp = item[i];
item[i] = item[j];
item[j] = temp;
}
} while(i<j);
item[left] = item[j];
item[j] = pivot;
// 나뉘어진 각각에 대해 다시 퀵정렬 실시
qs(item, left, j-1);
qs(item, j+1, right);
}
}
- 테스트 프로그램의 코드에 관해서
컴파일러는 VC++ 6.0을 사용하였다. 다음은 테스트 해본 프로그램의 소스에 대한 설명이다.
1. SDI, 프로젝트명은 Exam 으로 정했다.
2. 데이터 갯수를 임의로 바꾸어 보기 위해 다음을 뷰의 헤더파일에 추가한다.
#define DATA_NUM 5000
3. 다음 함수들을 뷰 클래스에 만든다.
void CExamView::Bubble(int item[], int count)
void CExamView::Select(int item[], int count)
void CExamView::Select2(int item[], int count)
void CExamView::Insert(int item[], int count)
void CExamView::Shell(int item[], int count)
void CExamView::InsertSort(int start, int inc, int item[], int count)
void CExamView::Quick(int item[], int count)
void CExamView::qs(int item[], int left, int right)
4. 뷰 클래스에 다음 변수들을 추가한다. 이 변수들은 각 정렬함수들의 속도를 받아 화면에 그 값들을 출력하기 위한 것이다.
CString StrBubble, StrSelect, StrSelect2;
CString StrInsert, StrShell, StrQuick;
5. 클래스 위저드에서 WM_INITIALUPDATE 메시지를 오버라이드하고, 다음과 같이 고친다.
간단히 설명하자면 srand(time(NULL)); 는 실행할 때마다 새로운 난수가 발생하도록 초기화해주는 것이다. 만약 이렇게 초기화 해주지 않으면 항상 같은 난수가 발생할 것이다. 그리고 각 정렬함수에 앞서 memcpy 함수를 사용한 것은 각 정렬함수가 앞의 정렬함수에 영향을 받지 않게 하기 위해서이다. 그러니까 각 정렬함수는 같은 값을 가지고 정렬을 하게 된다.
void CExamView::OnInitialUpdate()
{
CView::OnInitialUpdate();
// TODO: Add your specialized code here and/or call the base class
int num[DATA_NUM], origin_num[DATA_NUM];
clock_t start, finish;
double duration;
srand(time(NULL)); // 난수 발생 초기화
for(int i=0; i<DATA_NUM; i++)
num[i] = rand();
memcpy(origin_num, num, DATA_NUM); // 원래값 기억
// 버블정렬 검사
start = clock();
Bubble(num, DATA_NUM);
finish = clock();
duration = (double)(finish-start);
StrBubble.Format("Bubble Sort -> %f", duration);
memcpy(num, origin_num, DATA_NUM);
// 선택정렬 검사
start = clock();
Select(num, DATA_NUM);
finish = clock();
duration = (double)(finish-start);
StrSelect.Format("Select Sort -> %f", duration);
memcpy(num, origin_num, DATA_NUM);
// 개선된 선택정렬 검사
start = clock();
Select2(num, DATA_NUM);
finish = clock();
duration = (double)(finish-start);
StrSelect2.Format("Enhanced Select Sort -> %f", duration);
memcpy(num, origin_num, DATA_NUM);
// 삽입정렬 검사
start = clock();
Insert(num, DATA_NUM);
finish = clock();
duration = (double)(finish-start);
StrInsert.Format("Insert Sort -> %f", duration);
memcpy(num, origin_num, DATA_NUM);
// 쉘정렬 검사
start = clock();
Shell(num, DATA_NUM);
finish = clock();
duration = (double)(finish-start);
StrShell.Format("Shell Sort -> %f", duration);
memcpy(num, origin_num, DATA_NUM);
// 퀵정렬 검사
start = clock();
Quick(num, DATA_NUM);
finish = clock();
duration = (double)(finish-start);
StrQuick.Format("Quick Sort -> %f", duration);
}
6. 화면에 값들을 출력하는 onDraw 함수는 다음과 같이 고친다. 각 CString형 변수들은 프로그램이 처음 시작될 때 실행되는 onInitialUpdate 함수에서 값들이 입력된다.
void CExamView::OnDraw(CDC* pDC)
{
CExamDoc* pDoc = GetDocument();
ASSERT_VALID(pDoc);
// TODO: add draw code for native data here
pDC->TextOut(10, 10, StrBubble);
pDC->TextOut(10, 25, StrSelect);
pDC->TextOut(10, 40, StrSelect2);
pDC->TextOut(10, 55, StrInsert);
pDC->TextOut(10, 70, StrShell);
pDC->TextOut(10, 85, StrQuick);
}
- end of this article -
'IT_Architecture > 자료구조 · 알고리즘' 카테고리의 다른 글
| [펌] 해쉬 함수의 종류와 특징 (0) | 2010.12.27 |
|---|---|
| [펌] 기수 정렬(Radix Sort) (0) | 2009.04.22 |
| [펌_java를 이용한 자료구조] 힙(Heap) (0) | 2007.07.02 |
| [펌_java를 이용한 자료구조] 탐색(Searching) (0) | 2007.07.02 |
| [펌_java를 이용한 자료구조] 재귀(Recursion) (0) | 2007.07.02 |