교재: C언어로 쉽게 풀어쓴 자료구조 개정 3판 (2019, 천인국 외)
12.1 정렬이란?
정렬(sorting)은 물건을 크기순으로 오름차순(ascending order)이나 내림차순(descending order)으로 나열하는 것을 의미한다. 정렬은 컴퓨터 공학에서 가장 기본적이고 중요한 알고리즘 중의 하나로 자료 탐색에 있어서 필수적이다. 정렬시켜야 할 대상은 레코드(record)라고 부른다. 레코드는 다시 필드(field)라고 하는 단위로 나누어진다. 여러 필드 중에서 특별히 레코드와 레코드를 식별해 주는 역할을 하는 필드를 키(key)라고 한다. 정렬이란 결국 레코드들을 키값의 순서로 재배열하는 것이다. 모든 경우에 있어서 최상의 성능을 보여주는 최적 알고리즘은 존재하지 않는다. 따라서 이들 중에서 현재의 프로그램 수행환경에서 가장 효율적인 정렬 알고리즘을 선택하여야 한다.
정렬 알고리즘은 대개 크게 2가지로 나누어진다.
- 단순하지만 비효율적인 방법 : 삽입 정렬, 선택 정렬, 버블 정렬 등
- 복잡하지만 효율적인 방법 : 퀵 정렬, 히프 정렬, 합병 정렬, 기수 정렬 등
정렬 알고리즘을 내부 정렬(internal sorting)과 외부정렬(external sorting)으로 구분할 수 도 있다. 내부 정렬은 정렬하기 전에 모든 데이터가 메인 메모리에 올라와 있는 정렬을 의미한다. 반면, 외부정렬은 외부 기억 장치에 대부분의 데이터가 있고 일부만 메모리에 올려놓은 상태에서 정렬을 하는 방법이다. 이 책에서는 내부 정렬만을 다루기로 한다.
정렬 알고리즘을 안정성(stability)의 측면에서 분류할 수 있다. 안정성이란 입력 데이터에 동일한 키값을 갖는 레코드가 여러 개 존재할 경우, 이들 레코드들의 상대적인 위치가 정렬 후에도 바뀌지 않음을 뜻한다.
12.2 선택 정렬
선택 정렬의 원리
입력 배열에서 최솟값을 발견한 다음, 이 최솟값을 배열의 첫 번째 요소와 교환한다. 다음에는 첫 번째 요소를 제외한 나머지 요소들 중에서 가장 작은 값을 선택하고 이를 두 번째 요소와 교환한다. 이 절차를 (n-1)만큼 되풀이하면 추가적인 배열을 사용하지 않고서도 전체 숫자들이 정렬된다.
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 10
#define SWAP(x, y, t) ( (t)=(x), (x)=(y), (y)=(t) )
int list[MAX_SIZE];
int n;
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);
}
}
//
int main(void)
{
int i;
n = MAX_SIZE;
srand(time(NULL));
for (i = 0; i < n; i++) // 난수 생성 및 출력
list[i] = rand() % 100; // 난수 발생 범위 0~99
selection_sort(list, n); // 선택정렬 호출
for (i = 0; i < n; i++)
printf("%d ", list[i]);
printf("\n");
return 0;
}
12.3 삽입 정렬
삽입 정렬(insertion sort)은 정렬되어 있는 리스트에 새로운 레코드를 적절한 위치에 삽입하는 과정을 반복한다. 입력 배열을 정렬된 부분과 정렬되지 않은 부분으로 나누어서 사용하면 된다. 정렬되어 있지 않은 부분의 첫 번째 숫자가 정렬된 부분의 어느 위치에 삽입되어야 하는가를 판단한 후 해당 위치에 이 숫자를 삽입하게 되면, 정렬된 부분의 크기는 하나 커지게 되고, 정렬되지 않은 부분의 크기는 하나 줄어들게 된다. 정렬되지 않은 부분이 없어질 때까지 반복하게 되면 전체 리스트가 정렬된다.
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;
}
}
12.4 버블 정렬
버블 정렬(bubble sort)은 인접한 2개의 레코드를 비교하여 크기가 순서대로 되어 있지 않으면 서로 교환하는 비교-교환 과정을 리스트의 왼쪽 끝에서 시작하여 오른쪽 끝까지 진행한다. 이 과정이 완료되면 가장 큰 레코드가 리스트의 오른쪽 끝으로 이동한다. 이러한 레코드의 이동 과정이 마치 물속에서 거품(bubble)이 보글보글 떠오르는 거소가 유사하여 버블정렬이라 부른다. 이러한 비교-교환 과정은 전체 숫자가 전부 정렬될 때까지 계속된다.
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);
}
}
12.5 쉘 정렬
삽입 정렬의 최대 문제점은 요소들이 삽입될 때, 이웃한 위치로만 이동한다는 것이다. 쉘정렬에서는 요소들이 멀리 떨어진 위치로도 이동할 수 있다. 쉘 정렬은 먼저 정렬해야 할 리스트를 일정한 기준에 따라 분류하여 연속적이지 않은 여러 개의 부분 리스트를 만들고, 각 부분 리스트를 삽입 정렬을 이용하여 정렬한다. 모든 부분 리스트가 정렬되면 다시 전체 리스트를 더 작은 개수의 부분 리스트로 만든 후에 알고리즘을 되풀이한다. 위의 과정은 부분 리스트의 개수가 1이 될 때까지 되풀이된다. 부분 리스트를 만드는 간격을 gap이라고 한다. 간격을 줄여가며 수행과정을 반복한다.
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) // n = size
{
int i, gap;
for (gap = n / 2; gap > 0; gap = gap / 2) {
if ((gap % 2) == 0) gap++;
for (i = 0; i < gap; i++) // 부분 리스트의 개수는 gap
inc_insertion_sort(list, i, n - 1, gap);
}
}
12.6 합병 정렬
합병 정렬(merge sort)은 하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트를 얻고자 하는 것이다. 합병 정렬은 분할 정복(divide and conquer) 기법에 바탕을 두고 있다.
분할(Devide): 입력 배열을 같은 크기의 2개의 부분 배열로 분할한다.
정복(Conquer): 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출을 이용하여 다시 분할 정복 기법을 적용한다.
결합(Combine): 정렬된 부분 배열들을 하나의 배열에 통합한다.
void merge(int list[], int left, int mid, int right)
{
int sorted[MAX_SIZE]; // 추가 공간이 필요
int i, j, k, l;
i = left; j = mid + 1; k = left;
// 분할 정렬된 list의 합병
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];
// 배열 sorted[]의 리스트를 배열 list[]로 복사
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); // 합병
}
}
12.7 퀵 정렬
퀵 정렬(quick sort)도 분할-정복법(divide and conquer)에 근거한다. 먼저 리스트 안에 있는 한 요소를 피벗(pivot)으로 선택한다. 피벗보다 작은 요소들은 모두 피벗의 왼쪽으로 옮겨지고 피벗보다 큰 요소들은 모두 피벗의 오른쪽으로 옮겨진다. 이 상태에서 피벗을 제외한 왼쪽 리스트와 오른쪽 리스트를 다시 저열하게 되면 전체 리스트가 정렬된다.
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 (low <= right && list[low] < pivot);
do
high--;
while (high >= left && 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);
}
}
12.9 기수 정렬
기수 정렬은 레코드를 비교하지 않고도 정렬하는 방법이다. 기수 정렬(radix sort)은 입력 데이터에 대해서 어떤 비교 연산도 실행하지 않고 데이터를 정렬할 수 있는 정렬 기법이다. 다만 문제는 기수 정렬이 추가적인 메모리를 필요로 하다는 것인데 이를 감안하더라도 기수 정렬이 다른 정렬 기법보다 빠르기 때문에 데이터를 정렬하는 상당히 인기 있는 정릴 기법 중의 하나이다. 기수 정렬의 단점은 정렬할 수 있는 레코드의 타입이 한정된다는 점이다.
각각의 버킷에서 먼저 들어간 숫자들은 먼저 나와야 한다. 따라서 각각의 버킷은 큐로 구현되너야 한다. n진법으로 표현하고 정렬한다면 버킷은 n개만 있으면 된다. 십진수의 경우 큐도 10개가 필요하다.
#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++) // 버켓에서 꺼내어 list로 합친다.
while (!is_empty(&queues[b]))
list[i++] = dequeue(&queues[b]);
factor *= 10; // 그 다음 자리수로 간다.
}
}
'CS과목 > 자료구조' 카테고리의 다른 글
| [CS과목/자료구조] 11 그래프 2 (0) | 2024.09.18 |
|---|---|
| [CS과목/자료구조] 10 그래프 1 (0) | 2024.09.18 |
| [CS과목/자료구조] 09 우선순위 큐 (0) | 2024.09.15 |
| [CS과목/자료구조] 08 트리 (0) | 2024.09.15 |
| [CS과목/자료구조] 07 연결 리스트 2 (0) | 2024.09.15 |