정렬
정렬은 자료 탐색에 있어서 필수적이다. 보통 정렬시켜야 될 대상은 레코드(record)라고 불린다. 레코드는 다시 필드(field)라고 하는 단위로 나뉘어진다. 여러 필드 중에서 특별히 레코드와 레코드를 식별해주는 역할을 하는 필드를 키(key)라고 한다. 정렬이란 결국 레코드들을 키값의 순서로 재배열하는 것이다.
대개 정렬 알고리즘을 평가하는 효율성의 기준으로는 정렬을 위해 필요한 비교 연산의 횟수와 이동 연산의 횟수이다. 이들 횟수를 정확하게 구하기는 힘들기 때문에 이들 횟수를 빅오 표기법을 이용하여 근사적으로 표현한다.
정렬 알고리즘은 대개 크게 2가지로 다음과 같이 나누어진다.
- 단순하지만 비효율적인 정렬 - 삽입 정렬, 선택 정렬, 버블 정렬 등
- 복잡하지만 효율적인 정렬 - 퀵 정렬, 힙 정렬, 합병 정렬, 기수 정렬 등
정렬 알고리즘을 안정성(stability)의 측면에서 분류할 수도 있다. 안정성이란 입력 데이터에 동일한 키값을 갖는 레코드가 여러 개 존재할 경우, 이들 레코드들의 상대적인 위치가 정렬 후에도 바뀌지 않음을 뜻한다. 정렬 알고리즘 중에서 안정성을 충족하는 정렬은 삽입 정렬, 버블 정렬, 합병 정렬 등이 있다.
1. 선택 정렬 (Selection Sort)
개념
선택 정렬은 입력 배열 이외에는 다른 추가 메모리를 요구하지 않는 제자리 정렬(in-place sorting) 알고리즘 중 하나이다.
입력 배열에서 최소값을 발견한 다음, 이 최소값을 배열의 첫번째 요소와 교환한다. 다음에는 첫번째 요소를 제외한 나머지 요소들 중에서 작은 값을 선택하고 이를 두번째 요소와 교환한다. 이 절차를 (숫자 개수 - 1)만큼 되풀이한다.
C언어 구현
#define SWAP(x, y, t) ( (t) = (x), (x) = (y), (y) = (t) )
void selection_sort(int list[], int n)
{
int i, j, least, temp;
for (i = 0; i < n - 1; i++)
{
least = i;
for (j = i + 1; j < n; j++)
if (list[j] < list[least])
least = j;
SWAP(list[i], list[least], temp);
}
}장점
- 이동횟수가 미리 결정된다. (그러나 이동횟수는 3(n - 1)로 상당히 큰 편)
단점
- 안정성을 만족하지 않는다. (값이 같은 레코드가 있는 경우 상대적 위치가 변경될 수 있음)
2. 삽입 정렬 (Insertion Sort)
개념
손안의 카드를 정렬하는 방법과 유사하다. 새로운 카드를 기존의 정렬된 카드 사이의 올바른 자리를 찾아 삽입함으로써 정렬이 유지되게 한다. 이 작업을 카드 수만큼 반복하게 되면 전체 카드가 정렬된다.
정렬되어 있는 리스트에 새로운 레코드를 적절한 위치에 삽입하는 과정을 반복하면 된다. 입력배열을 정렬된 부분과 정렬되지 않은 부분으로 나누어서 사용하면 된다.
C언어 구현
void insertion_sort(int list[], int n)
{
int i, j, key;
for (i = 1; i < n; i++)
{
key = list[i];
for (j = i - 1; j >= 0 && list[j] > key; j--)
list[j + 1] = list[j];
list[j + 1] = key;
}
}장점
- 안정성을 보장한다.
- 레코드 수가 적을 경우 알고리즘 자체가 매우 간단하므로 다른 복잡한 정렬 방법보다 유리하다.
- 대부분의 레코드가 이미 정렬되어 있는 경우에 매우 효율적이다.
단점
- 비교적 많은 레코드들의 이동을 포함한다.
- 레코드의 양이 많고 크기가 클 경우 적합하지 않다.
3. 버블 정렬 (Bubble Sort)
개념
인접한 2개의 레코드를 비교하여 크기가 순서대로 되어 있지 않으면 서로 교환하는 비교-교환 과정을 리스트의 왼쪽 끝에서 오른쪽 끝까지 진행한다. 비교-교환 과정(스캔)이 한번 완료되면 가장 큰 레코드가 리스트의 오른쪽 끝으로 이동된다. 이 과정이 전체 숫자가 전부 정렬될 때까지 반복된다.
C언어 구현
#define SWAP(x, y, t) ( (t) = (x), (x) = (y), (y) = (t) )
void bubble_sort(int list[], int n)
{
int i, j, temp;
for (i = n - 1, i > 0; i--)
{
for (j = 0; j < i; j++)
if (list[j] > list[j + 1])
SWAP(list[j], list[j + 1], temp);
}
}장점
- 구현이 매우 간단하다.
단점
- 순서에 맞지 않는 요소를 인접한 요소와 교환한다.
- 하나의 요소가 가장 왼쪽에서 가장 오른쪽으로 이동하기 위해서는 배열의 모든 다른 요소들과 교환되어야 한다.
- 특정 요소가 최종 정렬 위치에 있는 경우라도 교환되는 일이 일어난다.
- 일반적으로 자료의 교환(swap) 작업이 자료의 이동(move) 작업보다 복잡하기 때문에 버블 정렬은 거의 쓰이지 않는다.
4. 쉘 정렬 (Shell Sort)
개념
Donald L. Shell이라는 사람이 제안한 삽입 정렬을 보안한 정렬이다. 삽입 정렬이 어느 정도 정렬된 상태에서는 대단히 빠르다는 것에 착안한 방법이다. 삽입 정렬의 𝑂(𝑛²)보다 빠르다.
삽입 정렬의 최대 문제점은 요소들이 삽입될 때, 이웃한 위치로만 이동한다는 것인데 쉘 정렬에서는 이 부분을 보안하여 요소들이 멀리 떨어진 위치로도 이동할 수 있다. 삽입 정렬과는 다르게 전체의 리스트를 한 번에 정렬하지 않고 일정한 기준에 따라 분류하여 연속적이지 않은 여러 개의 부분 리스트를 만들고, 각 부분 리스트를 삽입 정렬을 이용하여 정렬한다. 모든 부분 리스트가 정렬되면 다시 전체 리스트를 더 적은 개수의 부분 리스트로 만드는 알고리즘을 부분 리스트의 개수가 1이 될 때까지 되풀이한다.
여기서 실제로 부분 리스트들이 만들어지는 것은 아니고 일정한 간격으로 삽입 정렬을 수행하는 것 뿐이다. 따라서 추가적인 공간은 필요 없다. 간격은 처음에는 𝑛/2정도로 하고 각 패스마다 간격을 줄이는 방식을 많이 사용한다.
C언어 구현
inc_insertion_sort(int list[], int first, int last, int gap)
{
int i, j, key;
for (i = first + gap; i <= last; i = i + gap)
{
key = list[i];
for (j = i - gap; j >= first && key < list[j]; j = j - gap)
list[j + gap] = list[j];
list[j + gap] = key;
}
}
void shell_sort(int list[], int n)
{
int i, gap;
for (gap = n / 2; gap > 0; gap = gap / 2)
{
if ((gap % 2) == 0)
gap++;
for (i = 0; i < gap; i++)
inc_insertion_sort(list, i, n - 1, gap);
}
}장점
- 연속적이지 않은 부분 리스트에서 자료의 교환이 일어나면 더 큰 거리를 이동한다. 따라서 교환되는 아이템들이 삽입 정렬보다는 최종 위치에 더 가까이 있을 가능성이 높아진다.
- 부분 리스트는 어느 정도 정렬이 된 상태이기 때문에 부분 리스트의 개수가 1이 되면 쉘 정렬은 기본적으로 삽입 정렬을 수행하는 것이지만 삽입 정렬보다 더 빠르게 수행된다.
5. 합병 정렬 (Merge sort)
개념
합병 정렬은 하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트를 얻고자 하는 것이다.
합병 정렬은 분할 정복(divide and conquer) 기법에 바탕을 두고 있다. 분할 정복 기법은 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략이다. 분할 정복 기법은 대게 순환 호출을 이용하여 구현된다.
- 분할(Divide) : 입력 배열을 같은 크기의 2개의 부분 배열고 분할한다.
- 정복(Conquer) : 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출을 이용하여 다시 분할 정복 기법을 적용한다.
- 결합(Combine) : 정렬된 부분 배열들을 하나의 배열에 통합한다.
합병 정렬에서 실제로 정렬이 이루어지는 시점은 2개의 리스트를 합병(merge)하는 단계이다. 합병 자체는 어렵지 않으나 추가적인 리스트를 필요로 한다.
C언어 구현
#define MAX_SIZE 10
int sorted[MAX_SIZE];
void merge(int list[], int left, int mid, int right)
{
int i, j, k, l;
i = left;
j = mid + 1;
k = left;
while (i <= mid && j <= right)
{
if (list[i] <= list[j])
sorted[k++] = list[i++];
else
sorted[k++] = list[j++];
}
if (i > mid)
for (l = j; l <= right; l++)
sorted[k++] = list[l];
else
for (l = i; l <= mid; l++)
sorted[k++] = list[l];
for (l = left; l <= right; l++)
list[l] = sorted[l];
}
void merge_sort(int list[], int left, int right)
{
int mid;
if (left < right)
{
mid = (left + right) / 2;
merge_sort(list, left, mid);
merge_sort(list, mid + 1, right);
merge(list, left, mid, right);
}
}장점
- 안정적인 정렬 방법이다.
- 데이터의 분포에 영향을 덜 받는다. 즉 입력 데이터가 무엇이든 간에 정렬되는 시간은 동일하다.
- 크기가 큰 레코드를 정렬할 경우, 연결 리스트를 사용한다면, 다른 어떤 정렬 방법보다 효율적일 수 있다.
단점
- 임시 배열이 필요하다.
- 레코드들의 크기가 큰 경우, 이동 횟수가 많으므로 큰 시간적 낭비를 초래한다.
6. 퀵 정렬 (Quick Sort)
개념
평균적으로 매우 빠른 수행 속도를 자랑하는 정렬 방법이다. 합병 정렬과 비슷하게 전체 리스트를 2개의 부분 리스트로 분할하고, 각각의 부분 리스트를 다시 퀵 정렬하는 분할-정복법을 사용한다.
퀵 정렬은 합병 정렬과는 달리 비균등하게 분할을 하는데 그 기준이 되는 피벗(pivot)을 선택한다. 피벗보다 작은 요소들은 모두 피벗 왼쪽으로 옮겨지고 피벗보다 큰 요소들은 모두 피벗의 오른쪽으로 옮겨진다. 이 상태에서 피벗을 제외한 왼쪽 리스트와 오른쪽 리스트를 다시 정렬하게 되면 전체 리스트가 정렬된다.
불균형 분할을 방지하기 위하여 피벗을 선택할 때 리스트의 중앙 부분을 분할할 수 있는 데이터를 선택한다. 많이 사용되는 방법은 리스트의 왼쪽, 오른쪽, 중간의 3개의 데이터 중에서 중간 값을 선택하는 방법이다.
퀵 정렬도 마찬가지로 부분 리스트에 대하여 순환 호출이되는 구조이고 부분 리스트들이 더 이상 분할이 불가능할 때까지 나누어진다.
C언어 구현
#define SWAP(x, y, t) ( (t) = (x), (x) = (y), (y) = (t) )
#define MAX_SIZE 10
int list[MAX_SIZE];
int partition(int list[], int left, int right)
{
int pivot, temp;
int low, high;
low = left;
high = right + 1;
pivot = list[left];
do
{
do
low++;
while (list[low] < pivot);
do
high--;
while (list[high] > pivot);
if (low < high)
SWAP(list[low], list[high], temp);
} while (low < high);
SWAP(list[left], list[high], temp);
return high;
}
void quick_sort(int list[], int left, int right)
{
if (left < right)
{
int q = partition(list, left, right);
quick_sort(list, left, q - 1);
quick_sort(list, q + 1, right);
}
}장점
- 속도가 빠르다.
- 추가 메모리 공간을 필요로 하지 않는다.
단점
- 정렬된 리스트에 대해서는 오히려 수행시간이 더 많이 걸린다.
7. 힙 정렬 (Heap Sort)
개념
힙은 우선순위 큐를 완전 이진 트리로 구현하는 방법으로 최댓값이나 최솟값을 쉽게 추출할 수 있는 자료구조이다. 힙에는 최소 힙과 최대 힙이 있고 정렬에서는 최소 힙을 사용하는 것이 더 쉽다. 최소 힙은 부모 노드의 값이 자식 노드의 값보다 작다. 따라서 루트 노드는 가장 작은 값을 가지게 된다.
힙 정렬은 최소 힙의 특성을 활용하여 정렬할 배열을 먼저 최소 힙으로 변환한 다음, 가장 작은 원소부터 차례대로 추출하여 정렬하는 방법이다. 힙은 1차원 배열로 쉽게 구현될 수 있다. 먼저 최소 힙을 만들고 숫자들을 차례대로 삽입한 다음, 최솟값부터 삭제하면 된다.
C언어 구현
#include <stdio.h>
#include <stdlib.h>
#define MAX_ELEMENT 200
typedef struct
{
int key;
} element;
typedef struct
{
element heap[MAX_ELEMENT];
int heap_size;
} HeapType;
HeapType *create()
{
return (HeapType *)malloc(sizeof(HeapType));
}
void init(HeapType *h)
{
h->heap_size = 0;
}
void insert_max_heap(HeapType *h, element item)
{
int i;
i = ++(h->heap_size);
while ((i != 1) && (item.key > h->heap[i / 2].key))
{
h->heap[i] = h->heap[i / 2];
i /= 2;
}
h->heap[i] = item;
}
element delete_max_heap(HeapType *h)
{
int parent, child;
element item, temp;
item = h->heap[1];
temp = h->heap[(h->heap_size)--];
parent = 1;
child = 2;
while (child <= h->heap_size)
{
if ((child < h->heap_size) && (h->heap[child.key] < h->heap[child + 1].key)
child++;
if (temp.key >= h->heap[child].key)
break ;
h->heap[parent] = h->heap[child];
parent = child;
child *= 2;
}
h->heap[parent] = temp;
return item;
}
void heap_sort(element a[], int n)
{
int i;
HeapType *h;
h = create();
init(h);
for (i = 0; i < n; i++)
insert_max_heap(h, a[i]);
for (i = (n - 1); i >= 0; i--)
delete_max_heap(h);
free(h);
}장점
- 효율이 좋은 정렬 방법 중 하나이다.
- 힙 정렬이 가장 유용한 경우는 전체 자료를 정렬하는 것이 아니라 가장 큰 값 몇 개만 필요할 때이다.
8. 기수 정렬 (Radix Sort)
개념
위의 정렬들은 모두 레코드들을 비교하여 정렬하지만 기수 정렬은 레코드들을 비교하지 않고 정렬한다.
기수(radix)는 숫자의 자리수이다. 기수 정렬은 다단계 정렬이다. 단계의 수는 데이터의 자리수의 개수와 일치한다.
0 ~ 9의 값만 가지는 십진수의 경우 10개의 버킷(bucket)을 만들어 입력 데이터를 각 자리수의 값에 따라 버킷에 넣는다. 순차적으로 버킷 안에 들어 있는 숫자를 순차적으로 읽으면 정렬된 숫자를 얻을 수 있다.
2자리 정수도 10개의 버킷만을 사용하여 정렬할 수 있다. 먼저 낮은 자리수로 정렬한 다음 차츰 높은 자리수로 정렬하면 된다.
각각의 버킷에서 먼저 들어간 숫자들은 먼저 나와야 한다. 따라서 각각의 버킷은 큐로 구현되어야 한다. 큐로 구현되어야 리스트 상에 있는 요소들이 상대적인 순서가 유지된다. 버킷에 숫자를 집어넣는 연산은 큐의 삽입 연산이 되고 숫자를 읽는 연산은 삭제 연산으로 대치하면 된다.
버킷의 개수는 키의 표현 방법과 밀접한 관계가 있다. 만약 키를 2진법을 사용하여 표현하고 정렬한다면 버킷은 2개만 있으면 된다. 키가 알파벳 문자로 되어 있다면 26개의 버킷이 필요하다. 숫자로 이루어진 키의 경우에는 10개의 버킷을 가지고 분류할 수 있다.
C언어 구현
#include <stdio.h>
#include <stdlib.h>
#define MAX_QUEUE_SIZE 100
typedef int element;
typedef struct
{
element data[MAX_QUEUE_SIZE];
int front, rear;
} QueueType;
void error(char *message)
{
fprintf(stderr, "%s\n", message);
exit(1);
}
void init_queue(QueueType *q)
{
q->front = q->rear = 0;
}
int is_empty(QueueType *q)
{
return (q->front == q->rear);
}
int is_full(QueueType *q)
{
return ((q->rear + 1) % MAX_QUEUE_SIZE == q->front);
}
void enqueue(QueueType *q, element item)
{
if (is_full(q))
error("큐가 포화상태입니다.");
q->rear = (q->rear + 1) % MAX_QUEUE_SIZE;
q->data[q->rear] = item;
}
element dequeue(QueueType *q)
{
if (is_empty(q))
error("큐가 공백상태입니다.");
q->front = (q->front + 1) % MAX_QUEUE_SIZE;
return q->data[q->front];
}
#define BUCKETS 10
#define DIGITS 4
void radix_sort(int list[], int n)
{
int i, b, d, factor = 1;
QueueType queues[BUCKETS];
for (b = 0; b < BUCKETS; b++)
init_queue(&queues[b]);
for (d = 0; d < DIGITS; d++)
{
for (i = 0; i < n; i++)
enqueue(&queues[(list[i] / factor) % 10], list[i]);
for(b = i = 0; b < BUCKETS; b++)
while (!is_empty(&queues[b]))
list[i++] = dequeue(&queues[b]);
factor *= 10;
}
}장점
- 정렬에 기초한 방법들은 절대 𝑂(𝑛log2𝑛)이라는 이론적인 하한선을 깰 수 없는데 반하여 기수 정렬은 이 하한선을 깰 수 있는 유일한 방법이다.
- 추가적인 메모리를 필요로 한다는 것을 감안하더라도 다른 정렬 기법보다 빠르기 때문에 상당히 인기 있는 정렬 기법 중 하나이다.
단점
- 정렬할 수 있는 레코드의 타입이 한정된다. 즉 기수 정렬을 사용하려면 레코드의 키들이 동일한 길이를 가지는 숫자나 문자열로 구성되어야 한다.
9. 정렬 알고리즘 시간 복잡도 비교
| 알고리즘 | 최선 | 평균 | 최악 | 실행 시간(정수 60,000개) 단위:sec) |
|---|---|---|---|---|
| 삽입 정렬 | 𝑂(𝑛) | 𝑂(𝑛²) | 𝑂(𝑛²) | 7.438 |
| 선택 정렬 | 𝑂(𝑛²) | 𝑂(𝑛²) | 𝑂(𝑛²) | 10.842 |
| 버블 정렬 | 𝑂(𝑛²) | 𝑂(𝑛²) | 𝑂(𝑛²) | 22.894 |
| 쉘 정렬 | 𝑂(𝑛) | 𝑂(𝑛^1.5) | 𝑂(𝑛^1.5) | 0.056 |
| 퀵 정렬 | 𝑂(𝑛log2𝑛) | 𝑂(𝑛log2𝑛) | 𝑂(𝑛²) | 0.014 |
| 힙 정렬 | 𝑂(𝑛log2𝑛) | 𝑂(𝑛log2𝑛) | 𝑂(𝑛log2𝑛) | 0.034 |
| 합병 정렬 | 𝑂(𝑛log2𝑛) | 𝑂(𝑛log2𝑛) | 𝑂(𝑛log2𝑛) | 0.026 |
| 기수 정렬 | 𝑂(d𝑛) | 𝑂(d𝑛) | 𝑂(d𝑛) |
References
