7.1 정렬이란?
정렬은 데이터를 크기 순으로 오름차순 혹은 내림차순으로 나열하는 것을 의미한다. 컴퓨터 공학에서 정렬은 가장 기본적인 알고리즘이면서, 다양한 연산의 성능을 결정할 수 있어 메우 중요하다. 실제로 컴퓨터가 하는 일 중 많은 부분을 정렬이 차지한다. 앞으로 간단히 생각해볼 수 있는 정렬 알고리즘부터 복잡하지만 효율적으로 동작하는 정렬 알고리즘에 대해 알아보려고 한다. 정렬 알고리즘의 성능을 평가하기 위해 비교 연산과 이동 연산의 시간복잡도를 빅오표기법을 이용하여 근사적으로 표현하겠다.
7.2 Selection Sort
선택 정렬은 남은 집합 중 최솟값을 선택하여 집합의 첫 요소와 교체하는 정렬 알고리즘이다. 시간복잡도를 고려해보자. 비교 연산의 경우 최솟값을 찾을 때 수행된다. 선택 정렬의 단계를 살펴보면 비교 횟수의 시간복잡도는 가 된다. 이동 연산의 경우는 최솟값과 첫 요소 간의 교체이므로 시간복잡도는 이다.
7.3 Insertion Sort
삽입 정렬은 정렬된 부분과 정렬되지 않은 부분을 나누어 정렬되지 않은 부분의 첫 요소를 정렬된 부분의 적절한 장소에 삽입하는 정렬 알고리즘이다. 우선 일반적인 경우를 가정하고 시간복잡도를 고려해보자. 정렬되지 않은 첫 요소와 정렬된 부분을 순차적으로 비교하면서 선택된 요소의 크기가 작을 때 정렬된 요소를 한 칸씩 이동시켜 삽입될 위치를 찾는다. 이러한 방식은 위에서 소개했던 선택 정렬에 비해 많은 양의 이동 연산을 요구한다. 평균적인 경우, 비교 연산 , 이동 연산 의 시간복잡도로 수행된다. 하지만 정렬되어 있는 배열이 입력된다면, 각 단계에서 비교 연산은 바로 앞의 요소와의 비교로 종료되고, 이동 연산은 수행되지 않는다. 이를 통해 최선의 경우 비교 연산 , 이동 연산 의 시간복잡도를 갖는다는 것을 알 수 있다.
7.4 Heap Sort
앞서 5장에서 히프에 대해 알아보았다. 히프를 통해서도 정렬을 수행할 수 있다. 만약 max heap을 구성하였다면 내림차순 정렬, min heap을 구성하였다면 오름차순 정렬이 가능하다. min heap의 상황을 가정해 보자. N개의 요소를 히프에 삽입한다면 의 시간이 걸리고, N개의 요소를 히프에서 삭제한다면 마찬가지로 의 시간이 소요된다. 이미 눈치를 챘을 수도 있지만 단순히 N개의 요소를 히프에 삽입, 삭제한다면 정렬된 순서로 각 요소가 출력된다.
히프 정렬은 위에서 알아본 두 정렬에 비해 상당히 빠른 으로 수행된다. 앞으로 살펴 볼 비교 기반 정렬은 모두 으로 수행되는 알고리즘이다.
7.5 Merge Sort
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N 50
void merge(int arr[], int left, int mid, int right){
int buffer[N];
int i, j, k;
i = left, j = mid+1, k = left;
while(i<=mid && j<=right){
if(arr[i] <= arr[j])
buffer[k++] = arr[i++];
else
buffer[k++] = arr[j++];
}
if(i>mid){
while(j<=right)
buffer[k++] = arr[j++];
}
else{
while(i<=mid)
buffer[k++] = arr[i++];
}
for(i=left; i<=right; i++)
arr[i] = buffer[i];
}
void merge_sort(int arr[], int l, int r){
int m;
if(l<r) // 재귀 종료 조건 (l=r이면 요소 하나인 경우)
{
m = (l+r)/2;
merge_sort(arr, l, m);
merge_sort(arr, m+1, r);
merge(arr, l, m, r);
}
}
int main(){
int i;
int data[N];
srand(time(NULL));
for(i=0; i<N; i++){
data[i] = rand() % 1000;
}
merge_sort(data, 0, N-1);
printf("MergeSort:\n");
for(i=0; i<N; i++){
printf("%3d ", data[i]);
if((i + 1) % 10 == 0)
printf("\n");
}
}-실행결과-
MergeSort:
12 28 40 42 49 112 148 159 165 169
169 172 183 191 218 225 250 291 321 328
394 420 442 475 477 481 487 487 492 518
535 552 571 594 603 613 624 632 649 732
737 753 761 810 811 894 923 928 936 975 7.6 Quick Sort
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <limits.h> // to use INT_MAX as a sentinel
#define N 50
void swap(int *x, int *y){
int tmp;
tmp = *x;
*x = *y;
*y = tmp;
}
int partition(int arr[], int left, int right){
int pivot = arr[left];
int i = left+1;
int j = right;
while(1){
while(arr[i] <= pivot) i++; // pivot 초과값 탐색
while(arr[j] > pivot) j--; // pivot 이하값 탐색
// without sentinel we need a bound check
// while(arr[i] <= pivot && i <= right)
if(i<j){
swap(&arr[i], &arr[j]);
i++; j--;
}
else // i, j 교차하면 break
break;
}
swap(&arr[left], &arr[j]);
return j;
}
void quick_sort(int arr[], int l, int r){
int p;
if(l<r) // 재귀 종료 조건 (l=r이면 요소 하나인 경우)
{
p = partition(arr, l, r);
quick_sort(arr, l, p-1);
quick_sort(arr, p+1, r);
}
}
int main(){
int i;
int data[N+1]; // N+1 for sentinel
srand(time(NULL));
for(i=0; i<N; i++){
data[i] = rand() % 1000;
}
data[i] = INT_MAX; // set sentinel
quick_sort(data, 0, N-1);
printf("QuickSort:\n");
for(i=0; i<N; i++){
printf("%3d ", data[i]);
if((i + 1) % 10 == 0)
printf("\n");
}
}QuickSort:
0 24 48 64 67 146 148 188 210 211
255 260 263 280 299 315 335 345 346 418
448 462 462 475 490 504 530 540 587 600
628 635 654 662 747 753 754 794 819 825
850 873 893 914 917 922 937 967 971 978 