1. 정렬이란
- 정렬(sorting)은 물건을 크기순으로 오름차순(ascending order)이나 내림차순(descending order)으로 나열하는 것을 의미한다.
- 어떤 형태의 것도 서로 비교만 가능하면 정렬할 수 있다.
- 정렬은 컴퓨터공학을 포함한 모든 과학 기술 분야에서 가장 기본적이고 중요한 알고리즘
- 정렬이란 레코드들을 키 값의 순서로 재배열하는 것이다.
- 정렬 알고리즘을 내부 정렬(internal sorting)과 외부 정렬(external sorting)로 구분할 수도 있다.
- 내부 정렬은 모든 데이터가 주기억장치에 저장된 상태에서 정렬하는 것, 외부 정렬은 외부기억장치(하드디스크)에 대부분의 데이터가 있고 일부만 주기억장치에 저장된 상태에서 정렬을 하는 방법
- 안정성(stability)은 같은 키 값을 갖는 레코드들이 정렬 후에 위치가 바뀌게 되면 안정하지 않다고 한다.
- 안정성을 충족하는 것에는 삽입 정렬, 합병 정렬 등이 있다.
2. 선택 정렬(selection sort)
- 선택 정렬은 오른쪽 리스트에서 가장 작은 숫자를 선택하여 왼쪽 리스트로 이동하는 작업을 되풀이한다.
- 다른 추가 메모리를 요구하지 않는 정렬 방법을 제자리 정렬(in-place sorting)이라고 한다.
- 선택 정렬 함수
#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);
}
}
- 선택 정렬의 시간복잡도는 외부 루프는 n-1번 내부 루프는 0에서 n-2까지 변하는 i에 대하여 (n-1)-i번 반복되므로 n(n-1)/2 = O(n2)
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;
}
}- 삽입 정렬의 시간복잡도는 외부 루프는 n-1번 실행되고 최악의 경우 외부 루프 안의 각 반복마다 i번의 비교가 수행되므로 n(n-1)/2 = O(n2)
- 삽입 정렬은 대부분의 레코드가 이미 정렬되어 있는 경우에 매우 효율적일 수 있다.
4. 버블 정렬(bubble sort)
- 버블 정렬은 인접한 2개의 레코드를 비교하여 크기가 순서대로 되어 있지 않으면 서로 교환하는 비교-교환 과정을 리스트의 왼쪽 끝에서 시작하여 오른쪽 끝까지 진행
- 비교-교환 과정(스캔)이 한 번 완료되면 가장 큰 레코드가 리스트의 오른쪽 끝으로 이동된다.
- 버블 정렬 함수
#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);
}
}- 버블 정렬의 비교 횟수는 최상, 평균, 최악의 어떠한 경우에도 항상 일정하고 다음과 같다.
- n(n-1)/2 = O(n2)
- 버블 정렬은 그 단순성에도 불구하고 거의 쓰이지 않고 있다.
5. 셸 정렬(shell sort)
- 삽입 정렬이 어느 정도 정렬된 배열에 대해서는 대단히 빠른 것에 착안한 방법이다.
- 정렬해야 할 리스트를 일정한 기준에 따라 분류하여 연속적이지 않은 여러 개의 부분 리스트를 만들고, 각 부분 리스트를 삽입 정렬을 이용하여 정렬한다.
- 간격은 처음에는 n/2으로 하고 각 패스마다 간격을 절반으로 줄이는 방식을 사용한다.
- gap은 홀수가 좋다.
- 셸 정렬 함수
// gap 만큼 떨어진 요소들을 삽입 정렬
// 정렬의 범위는 first에서 last
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);
}
}- 연속적이지 않은 부분 리스트에서 자료의 교환이 일어나면 더 큰 거리를 이동하므로 최종 위치에 더 가까이 있을 가능성이 높아진다.
- 시간복잡도는 평균적인 경우 O(n1.5)로 나타난다.
6. 합병 정렬(merge sort)
- 입력 데이터가 많으면서 자주 정렬해야 할 필요가 있을 때 앞의 방법들보다 훨씬 빠른 방법이다.
- 분할 정복(divide and conquer) 방법에 바탕을 두고 있다.
- 분할 정복 방법은 대개 순환 호출을 이용하여 구현된다.
- 합병 정렬에서 실제로 정렬이 이루어지는 시점은 2개의 리스트를 합병(merge)하는 단계이다.
- 합병 정렬 함수
int sorted[MAX_SIZE]; // 추가 공간이 필요
/* i는 정렬된 왼쪽리스트에 대한 인덱스
j는 정렬된 오른쪽리스트에 대한 인덱스
k는 정렬될 리스트에 대한 인덱스 */
void merge(int list[], int left, int mid, int right)
{
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); /* 합병 */
}
}- 합병 정렬의 시간복잡도 :
레코드의 개수 n이 2의 거듭제곱이라고 가정하고 n=2k이라고 하면 순환 호출의 깊이가 k가 될 것임을 쉽게 알 수 있다.
부분 배열로 나누어지는 단계에서는 비교나 이동 연산이 수행되지 않고 부분 배열이 합쳐지는 merge 함수에서 비교 연산과 이동 연산이 수행되는 것이다.
n=23인 경우 크기 1인 부분 배열 2개를 합병하는 데는 최대 2개의 비교 연산이 필요하고, 부분 배열의 쌍이 4개이므로 2*4=8번의 비교 연산이 필요하다.
마지막 합병 단계인 크기가 4인 부분 배열 2개를 합병하는 데는 최대 8번의 비교 연산이 필요하다.
일반적인 경우를 유추해보면 하나의 합병 단계에서는 최대 n번의 비교 연산이 필요함을 알 수 있다. 그러한 합병 단계가 k=log2n번만큼 있으므로 총 비교 연산은 최대 nlog2n번 필요하다.
- 크기가 큰 레코드를 정렬할 경우에 연결 리스트를 사용한다면, 합병 정렬은 퀵 정렬을 포함한 다른 어떤 정렬 방법보다 효율적일 수 있다.
7. 퀵 정렬(quick sort)
- 평균적으로 매우 빠른 수행 속도를 자랑하는 정렬 방법이다. 퀵 정렬도 분할 정복(divide and conquer) 방법에 근거한다.
- 리스트 안에 있는 한 요소를 피벗(pivot)으로 선택한다. 일단 리스트의 첫 번째 요소를 피벗으로 하기로 한다.
- 피벗보다 작은 요소들은 모두 피벗의 왼쪽으로 옮겨지고 피벗보다 큰 요소들은 모두 피벗의 오른쪽으로 옮겨진다.
- 피벗을 제외한 왼쪽 리스트와 오른쪽 리스트를 다시 정렬하게 되면 전체 리스트가 정렬된다.
- 합병 정렬과 마찬가지로 퀵 정렬 함수가 다시 부분 리스트에 대하여 순환 호출된다.
- 퀵 정렬 알고리즘
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);
}
}- 퀵 정렬에서 가장 중요한 함수가 partition 함수이다.
- partition 함수
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;
}- 퀵 정렬의 복잡도 분석 :
n이 2의 거듭제곱이라고 가정하고 합병 정렬과 마찬가지로 k=log2n개의 패스가 필요하게 된다.
평균 n번 정도의 비교가 이루어지므로 O(nlog2n)의 복잡도를 가지는 알고리즘이 된다.
최악의 경우는 리스트가 계속 불균형하게 나누어지는 경우이고 이 경우 레코드의 수만큼 총 n번의 패스가 실행되고, 각 패스에서 n번의 비교가 이루어져 O(n2)의 시간복잡도를 가지게 된다.
- 정렬된 리스트에 대해서는 오히려 수행시간이 더 많이 걸리는 등의 단점도 가진다.
- 불균형 분할을 방지하기 위해 중간 값을 피벗으로 선택하는 방법을 사용한다.
- 일반적으로 리스트의 왼쪽, 오른쪽, 중간의 3개의 데이터 중에 중간 값을 선택하는 방법(median of three)이 많이 사용된다.
8. 히프 정렬(heap sort)
- https://bottlesik.tistory.com/22
9. 기수 정렬(radix sort)
- 기수 정렬은 레코드를 비교하지 않고도 정렬하는 방법이다.
- 정렬에 기초한 방법들은 절대 O(nlog2n)이라는 이론적인 하한선을 깰 수 없는 데 반하여 기수 정렬은 이 하한선을 깰 수 있는 유일한 기법이다.
- 기수 정렬은 O(dn)의 시간 복잡도를 가지는데 대부분 d<10 이하이다. 다만 추가적인 메모리를 필요로 하지만 다른 정렬보다 빠르기 때문에 상당히 인기 있는 정렬 기법 중의 하나이다.
- 단점은 정렬할 수 있는 레코드의 타입이 한정된다는 것인데 기수 정렬을 사용하려면 레코드의 키들이 동일한 길이를 가지는 숫자나 문자열로 구성되어 있어야 한다.
- 십진수에서는 각 자릿수가 0에서 9까지의 값만 있으므로, 이것에 착안하여 10개의 버켓(bucket)을 만들어서 입력 데이터를 각 자릿수의 값에 따라 버켓에 넣는다.
- 여기서는 먼저 낮은 자릿수로 정렬한 다음 차츰 높은 자릿수로 정렬하면 된다.
- 기수 정렬 알고리즘
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
typedef int element; // 요소의 타입
typedef struct QueueNode { // 큐의 노드의 타입
element item;
struct QueueNode *link;
} QueueNode;
typedef struct { // 큐 ADT 구현
QueueNode *front, *rear;
} QueueType;
// 오류 함수
void error(char *message)
{
fprintf(stderr, "%s\n", message);
exit(1);
}
// 초기화 함수
void init(QueueType *q)
{
q->front = q->rear = 0;
}
// 공백 상태 검출 함수
int is_empty(QueueType *q)
{
return (q->front == NULL);
}
// 포화 상태 검출 함수
int is_full(QueueType *q)
{
return 0;
}
// 삽입 함수
void enqueue(QueueType *q, element item)
{
QueueNode *temp = (QueueNode *)malloc(sizeof(QueueNode));
if (temp == NULL)
error("메모리를 할당할 수 없습니다");
else {
temp->item = item; // 데이터 저장
temp->link = NULL; // 링크 필드를 NULL
if (is_empty(q)) { // 큐가 공백이면
q->front = temp;
q->rear = temp;
}
else { // 큐가 공백이 아니면
q->rear->link = temp; // 순서가 중요
q->rear = temp;
}
}
}
// 삭제 함수
element dequeue(QueueType *q)
{
QueueNode *temp = q->front;
element item;
if (is_empty(q)) // 공백상태
error("큐가 비어 있읍니다");
else {
item = temp->item; // 데이터를 꺼낸다.
q->front = q->front->link; // front를 다음노드를 가리키도록 한다.
if (q->front == NULL) // 공백 상태
q->rear = NULL;
free(temp); // 동적메모리 해제
return item; // 데이터 반환
}
}
// peek 함수
element peek(QueueType *q)
{
element item;
if (is_empty(q))
error("큐가 비어 있읍니다");
else {
item = q->front->item; // 데이터를 꺼낸다.
return item; // 데이터 반환
}
}
#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(&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; // 그 다음 자리수로 간다.
}
}
#define MAX_SIZE 10000
#define SWAP(x, y, t) ( (t)=(x), (x)=(y), (y)=(t) )
int list[MAX_SIZE];
int n;
//
void main()
{
int i;
n = MAX_SIZE;
for (i = 0; i<n; i++) /* 난수 생성 및 출력 */
list[i] = rand() % n; /*난수 발생 범위 0~n*/
radix_sort(list, n);
for (i = 0; i<n; i++)
printf("%d\n", list[i]);
}- 기수 정렬 분석 :
입력 리스트가 n개의 정수를 가지고 있다면 알고리즘 내부 루프는 n번 반복될 것이다.
만약 각 정수가 d개의 자리수를 가지고 있다고 하면 외부 루프는 d번 반복된다. 따라서 기수 정렬은 O(dn)의 시간 복잡도를 가진다.
일반적으로 컴퓨터 안에서는 정수의 크기가 제한된다. 32bit 컴퓨터의 경우 대개 10개 정도의 자릿수만을 가지게 된다. 따라서 d는 n에 비하여 아주 작은 수가 되므로 O(n)이라고 하여도 무리가 없다.
다만 문제점은 기수 정렬은 정렬에 사용되는 키 값이 숫자로 표현되어야만이 적용 가능하다는 것이다.
[Reference]
- 천인국, 공용해, 하상호, 「C언어로 쉽게 풀어쓴 자료구조」, 생능출판, 2009년
'DataStructure' 카테고리의 다른 글
| Graph(그래프) - 2 (0) | 2022.03.11 |
|---|---|
| Graph(그래프) - 1 (0) | 2022.03.11 |
| Priority Queue(우선순위 큐)와 Heap(힙) (0) | 2022.03.11 |
| Tree(트리) - 2 [Binary Search Tree] (0) | 2022.03.04 |
| Tree(트리) - 1 [Binary Tree] (0) | 2022.03.04 |