정렬
> 물건을 크기순으로 오름차순이나 내림차순으로 나열하는 것
> 정렬시켜야 할 대상을 레코드라고 한다. 레코드는 다시 필드라고 하는 단위로 나누어진다.
- 정렬이란 레코드들의 키 값의 순서로 재배열하는 것이다.
- 정렬 알고리즘 종류
- 단순하지만 비효율적인 방법: 삽입정렬, 선택정렬, 버블정렬
- 복잡하지만 효율적인 방법: 퀵정렬, 히프정렬, 합병정렬, 기수정렬
> 자료의 개수가 적다면 단순한 정렬 방법을 사용하는 것도 괜찮지만 자료의 개수가 일정 개수를 넘어가면 반드시 효율적인 알고리즘을 사용해야 한다.
- 정렬 알고리즘은 내부정렬(internal sorting)과 외부정렬(external sorting)로 구분할 수 있다.
내부정렬> 정렬하기 전에 모든 데이터가 메인 메모리에 올라와 있는 정렬
외부정렬> 기억 장치에 대부분의 데이터가 있고 일부분만 메모리에 올려놓은 상태에서 정렬을 하는 방법
> 정렬 알고리즘은 안정성의 측면에서 분류할 수 도 있다. 정렬 알고리즘에서 안정성이란 입력 데이터에 동일한 키 값을 갖는 레코드가 여러 개 존재할 경우, 이들 레코드들의 상대적인 위치가 정렬 후에도 바꾸지 않음을 뜻한다. 같은 키값을 갖는 레코드들이 정렬 후에 위치가 바뀌게 되면 안정하지 않다고 한다.
> 정렬의 안정성이 필수적으로 요구되는 경우에는 정렬 알고리즘 중에서 안정성을 충적하는 삽입정렬, 버블정렬, 합병정렬 등을 사용해야 한다.
선택 정렬의 원리
> 정렬의 대상이 되는 것은 설명을 쉽게 하기 위하여 숫자 필드만을 가지고 있는 레코드라고 가정하고, 이 숫자들이 1차원 배열에 들어가 있다고 가정했다.
- 먼저 왼쪽 리스트와 오른쪽 리스트 2개의 리스트가 있다고 가정한다. 왼쪽 리스트에는 정렬이 완료된 숫자들이 들어가게 되며 오른쪽 리스트는 정렬되지 않은 숫자들이 들어있다
- 초기 상태에서 왼쪽 리스트는 비어있고 정렬되어야 할 숫자들은 모두 오른쪽 리스트에 들어있다
- 선택 정렬은 오른쪽 리스트에서 가장 작은 숫자를 선택하여 왼쪽 리스트로 이동하는 작업을 되풀이한다
- 선택 정렬은 오른쪽 리스트가 공백상태가 될 때까지 이 과정을 되풀이하는 정렬 기법이다
> 구현하기 위해서 입력 배열과는 별도로 똑같은 크기의 배열이 하나 더 필요하다. 입력 배열 외에 다른 추가 메모리를 요구하지 않는 정렬 방법을 제자리 정렬이라고 한다
- 입력 배열에서 최솟값을 발견한 다음 배열의 첫 번째 요소와 교환한다
- 첫 번째 요소를 제외한 나머지 요소들 중에서 가장 작은 값을 선택하고 이를 두 번째 요소와 교환한다
- 이 절차를 (숫자 개수-1)만큼 되풀이하면 추가적인 배열을 사용하지 않고서도 전체 숫자들이 정렬된다
- 선택 정렬의 알고리즘
selection_Sort(A,n):
for i<-0 n-2 do
least <- A[i],A[i+1],....,A[n-1] 중에서 가장 작은 값의 인덱스;
A[i]와 A[least]의 교환;
i++;> 여기서 주의할 점은 i값이 0에서 n-2까지만 변화된다는 점이다. 만약 list [0]부터 list [n-2]까지 정렬이 되었으면 이미 list [n-1]이 가장 큰 값이기 때문에 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;
}
- 선택 정렬의 시간 복잡도 -
> 선택 정렬의 성능 분석을 위해서 비교 횟수와 이동 횟수를 따로 구분하였다. 먼저 비교 횟수를 구하기 위해서 두 개의 for루프의 실행 횟수를 계산해 보면, 외부루프는 n-1번 실행될 것이며, 내부루프는 0에서 n-2까지 변하는 i에 대해서 (n-1)-i번 반복 된다. 키 값들의 비교가 내부 루프 안에서 이루어 지므로 전체 비교 횟수는(n-1+(n-2)+...+1=n(m-1)/2=O(n^2)이다. 레코드 교환 횟수는 외부 루프의 실행 횟수와 같으며 한번 교환하기 위해서 3번의 이동이 필요하므로 전체 이동 횟수는 3(n-1)이 된다.
삽입 정렬
> 삽입 정렬은 정렬되어 있는 리스트에 새로운 레코드를 적절한 위치에 삽입하는 과정을 반복한다. 입력배열을 정렬된 부분과 정렬되지 않은 부분으로 나누어서 사용한다
> 정렬되어 있지 않은 부분의 첫 번째 숫자가 정렬된 부분의 어느 위치에 삽입되어야 하는 가를 판단한 후에 해당 위치에 이 숫자를 삽입하게 되면, 정렬된 부분의 크기는 하나 커지게 되고, 정렬이 되지 않은 부분의 크기는 하나 줄어들게 된다. 이러한 삽입 연산을 정렬되지 않은 부분이 공백이 될 때까지 반복하게 되면 전체 리스트가 정렬된다.
insert_sort(A,n):
for i<-1 to n-1 do
key<-A[i];
j<-i-1;
while j>=0 and A[j]>key d
A[j+1]<-A[j];
j<<-1;
A[j+1]<-key- 인덱스 1부터 시작한다. 인덱스 0은 이미 정렬된 것으로 볼 수 있다
- 현재 삽입될 숫자인 i번째 정수를 key 변수로 복사한다
- 현재 정렬된 배열은 i-1까지 이므로 i-1번째부터 역순으로 조사한다
- j값이 음수가 아니어야 하고 key값보다 정렬된 배치에 있는 값이 크면 j번째를 j+1번째로 이동한다
- j를 하나 감소한다
- j번째 정수가 key 보다 작으므로 j+1번째가 key 값이 들어갈 위치가 된다
- 삽입정렬의 시간복잡도 -
> 삽입 정렬의 복잡도는 입력 자료의 구성에 따라서 달라진다. 먼저 입력 자료가 이미 정렬되어 있는 경우는 가장 빠르다. 삽입 정렬의 외부 루프는 n-1번 실행되고 각 단계에서 1번의 비교와 2번의 이동만 이루어지므로 총 비교 횟수는 n-1번, 총 이동 횟수는 2(n-1) 번이 되어 알고리즘의 시간 복잡도는 O(n)이다.
> 최악의 복잡도는 입력 자료가 역순을 경우이다. 각 단계에서 앞에 높인 자료들은 전부 한 칸씩 뒤로 이동해야 한다. 따라서 외부 루프 안의 각 반복마다 i번의 비교가 수행되므로 O(n^2)가 된다.
참고> 삽입정렬은 비교적 많은 레코드들의 이동을 포함한다. 결과적으로 삽입 정렬은 레코드 양이 많고, 크기가 클 경우에 적합하지 않다. 반면 삽입 정렬은 안정한 정렬 방법으로 레코드의 수가 적을 경우 알고리즘 자체가 매우 간단하므로 다른 복잡한 정렬 방법보다 유리하다. 그리고 삽입정렬은 대부분의 레코드가 이미 정렬되어 있는 경우에 매우 효율적이다
버블정렬(bouble sort)
> 버블정렬은 인접한 2개의 레코드를 비교하여 크기가 순서대로 되어 있지 않으면 서로 교환하는 비교-교환 과정을 리스트의 왼쪽 끝에서 시작하여 오른쪽 끝까지 진행한다. 이러한 리스트의 비교-교환 과정이 한번 완료되면 가장 큰 레코드가 리스트의 오른쪽 끝으로 이동한다. 이러한 비교-교환 과정은 전체 숫자가 전부 정렬될 때까지 계속된다
> 정렬이 안된 오른쪽 리스트를 한번 스캔하면 오른쪽리스트의 오른쪽 끝에 가장 큰 레코드가 위치하게 되고, 오른쪽 리스트는 추가된 레코드를 포함하여 정렬된 상태가 된다. 이러한 스캔 과정을 정렬이 안 된 왼쪽 리스트에서 반복하여 적용하면 정렬이 완료된다.
- 버블정렬 알고리즘
Bouble_Sort(A,n):
for i<-n to 1 do
for j<-0 to i-1 do
j와 j+1번째 요소가 크기순이 아니면 교환
j++;
i--;#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);
}
}
- 버블 정렬의 시간복잡도 -
> O(n^2)
참고 > 버블 정렬의 가장 큰 문제점은 순서에 맞지 않는 요소를 인접한 요소와 교환하는 것이다. 하나의 요소가 가장 왼쪽에서 가장 오른쪽으로 이동하기 위해서 배열에서 모든 다른 요소들과 교환되어야 한다. 특저 요소가 최종 정렬 위치에 이미 있는 경우라도 교환되는 일이 일어난다. 일반적으로 자료의 교환 작업이 자료의 이동 작업보다 더 복잡하기 때문에 버블 정렬은 단순성에도 불구하고 거의 쓰이지 않는다.
쉘 정렬(shell sort)
> 쉘정렬은 삽입정렬이 어느 정도 정렬된 배열에 대해서 빠르다는 것에서 착안된 방법이다.
> 삽입 정렬의 최대 문제점은 요소들이 삽입될 때, 이웃한 위치로만 이동한다는 것이다. 만약 삽입되어야 할 위치가 현재 위치에서 상당히 멀리 떨어진 곳이라면 많은 이동을 해야 만이 제자리로 돌아갈 수 있다. 쉘정렬에서는 요소들이 멀리 떨어진 위치로도 이동할 수 있다.
- 삽입 정렬과 다르게 쉘정렬은 전체의 리스트를 한 번에 정렬하지 않는다
- 먼저 정렬할 리스트를 일정한 기준에 따라 분류하여 연속적이지 않은 여러 개의 부분리스트를 만들고 각 부분리스트를 삽입 정렬을 이용해서 정렬한다
- 모든 부분리스트가 정렬되면 쉘정렬은 다시 전체 리스트를 더 적은 개수의 부분리스트로 만든 후에 알고리즘을 되풀이한다
- 이 과정을 부분리스트의 개수가 1이 될 때까지 반복한다
> 부분 리스트를 구성할 때 주어진 리스트의 각 k번째 요소를 추출하여 만드는데, 이 k를 (gap)이라고 한다. 쉘 정렬에서는 각 스텝마다 간격 k를 줄여가므로 수행과정이 반복될 때마다 하나의 부분 리스트에 속하는 레코드들의 개수는 증가한다. 마지막 스텝에서는 간격의 값이 1이 된다
> 쉘정렬의 첫 번째 패수가 끝나면 비슷한 방식으로 다시 부분 리스트를 구성하는데, 간격을 1/2 줄여서 입력 배열의 각 2번째 요소를 추출하여 부분 리스트를 만든다. 간격은 처음에는 n/2 정도로 하고 각 패스마다 간격을 절반으로 줄이는 방식을 사용한다.
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이 되게 되면 쉘정렬은 기본적으로 삽입 정렬을 수행하는 것이지만 빠르게 수행된다. 이것은 삽입정렬이 거의 정렬된 리스트에 대해서 빠르게 수행되기 때문이다.
- 쉘정렬의 시간복잡도 -
> 실험적인 연구를 통해서 쉘정렬의 시간 복잡도는 대략 최악의 경우에는 O(n^2)이지만 평균적인 경우에는 O(N^1.5)이다.
합병 정렬(merge sort)
- 합병정렬은 하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트를 얻고자 하는 방법이다
> 합병정렬은 분할정복기법에 바탕을 두며 분할정복기법은 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 방법이다. 분리된 문제가 해결하기 어렵다면(충분히 작지 않다면) 분할정복방법을 연속해서 다시 적용한다
- 분할(divide): 입력 배열을 같은 크기의 2개의 부분 배열로 분할한다
- 정복(conquer): 부분 배열을 정렬한다. 부분배열의 크기가 충분히 작지 않으면 순환 호출을 이용해서 다시 분할 정복 기법을 적용한다
- 결합(combine): 정렬된 부분 배열들을 하나의 배열에 통합한다
- 합병 알고리즘
merge_sort(list, left, right):
if left <right
mid=(left+right)/2;
merge_sort(list, left, mid);
merge_sort(list, mid+1, right);
merge(list, left, mid, right);- 나누어진 구간의 크기가 1 이상이면 중간 위치를 계산한다
- 앞쪽 부분 배열을 정렬하기 위해 merge_sort 함수를 순환호출한다
- 뒤쪽 부분 배열을 정렬하기 위해 merge_sort 함수를 순환호출한다
- 정렬된 2개의 부분 배열을 통합해서 하나의 정렬된 배열로 만든다
> 합병 정렬에서 실제로 정렬이 이루어지는 시점은 2개의 리스트를 합병하는 단계이다.
> 합병 알고리즘은 2개의 리스트의 요소들을 처음부터 하나씩 비교하여 두 개의 리스트의 요소 중에서 더 작은 요소를 새로운 리스트로 옮긴다. 둘 중에서 하나가 끝날 때까지 이 과정을 반복한다. 만약 둘 중에서 하나의 리스트가 먼저 끝나게 되면 나머지 리스트의 요소들을 전부 새로운 리스트로 복사한다.
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;
/* 분할 정렬된 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);
}
}
- 합병정렬의 시간복잡도 -
> k = log2 n
장점> 안정적인 정렬 방법이며 데이터의 분포에 영향을 덜 받는다. 입력 데이터가 어떤 것이든 정렬되는 시간은 동일하다. 최악, 평균, 최선의 경우가 동일한 O(n log2 n)인 정렬이다
단점> 합병정렬의 단점은 임시 배열이 필요하다는 것과 레코드의 크기가 큰 경우에는 이동 횟수가 많아져서 매우 큰 시간 낭비를 초래한다는 것이다. 그러나 레코드를 연결 리스트로 구성하여 합병정렬을 할 경우에는 링크 인덱스만 변경되므로 데이터의 이동은 무시할 수 있을 정도로 작아진다. 따라서 크기가 큰 레코드를 정렬할 경우, 연결 리스트를 사용한다면 합병 정렬은 퀵 정렬을 포함한 어떤 정렬보다 효율적일 것이다.
퀵 정렬(quick sort)
> 평균적으로 매우 빠른 속도를 자랑하는 정렬 방법이다. 퀵정렬은 분할 정복법에 근거한다. 퀼정렬은 합병정렬과 비슷하게 전체를 2개의 부분리스트로 분할하고, 각 부분 리스트를 다시 퀵정렬하는 전형적인 분할정복법을 사용한다
- 리스트 안에 있는 한 요소를 피벗(pivot)으로 선택한다.
- 피벗보다 작은 요소들은 모두 피벗의 왼쪽으로 옮기고 큰 요소들은 오른쪽으로 옮긴다
- 결과적으로 피벗을 중심으로 왼쪽은 피벗보다 작은 요소들로, 오른쪽은 큰 요소 들고 구성된다
- 이 상태에서 피벗을 제외한 왼쪽 리스트와 오른쪽 리스트를 다시 정렬하게 되면 전체 리스트가 정렬된다
> 퀵 정렬 함수는 다시 부분 리스트에 대하여 순환호출 된다. 부분 리스트에서도 다시 피봇을 정하고 피벗을 기준으로 2개의 부분 리스트로 나눠지는 과정을 되풀이한다. 부분 리시트들이 더 이상 분할이 불가능할 때까지 나눈다
- 퀵 정렬 알고리즘
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAX_SIZE 10
#define SWAP(x, y, t) ( (t)=(x), (x)=(y), (y)=(t) )
int list[MAX_SIZE];
int n;
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);
}
}
//
int main(void)
{
int i;
n = MAX_SIZE;
srand(time(NULL));
for (i = 0; i<n; i++)
list[i] = rand() % 100;
quick_sort(list, 0, n-1); // 퀵정렬 호출
for (i = 0; i<n; i++)
printf("%d ", list[i]);
printf("\n");
return 0;
}
- 퀵정렬 시간복잡도 -
> n이 2의 거듭제곱이라고 가정하고 퀵 정렬에서 리스트 분할이 항상 리스트의 가운데에서 이루어진다고 가정하면 합병 정렬의 복잡도 분석과 마찬가지로 n개의 레코드를 가지는 리스트는 n/2^k의 크기고 나누어진다. 크기가 1이 될 때까지 나누어지므로 k=log2n개의 패스가 필요하다. 각각의 패스에서는 전체 리스트의 대부분의 레코드를 비교해야 하므로 평균 n번 정도의 비교가 이루어지므로 퀵 정렬은 비교 연산을 총 n log2n번 실행하여 O(n log2 n)의 복잡도를 가진다
> 퀵정렬에서 최악의 경우는 리스트가 계속 불균형하게 나누어지는 것인데 이 경우 레코드의 수만큼 총 n번의 패스가 실행되고 각 패스에서 n번의 배교가 이루어지므로 연산을 n^2번 실행하게 된다. 따라서 최악의 경우 퀵정렬은 O(n^2)의 시간복잡도를 가진다
> 퀵정렬은 평균적인 경우의 시간복잡도가 O(n log2 n)로 나타난다. 특히 O(n log2 n)의 복잡도를 가지는 다른 알고리즘과 비교하였을 때도 가장 빠른 것으로 나타난다. 이것은 퀵정렬이 불필요한 데이터의 이동을 줄이고 먼 거리의 데이터를 교환할 뿐만 아니라, 한번 결정된 피벗들이 추후 연산에서 제외되는 특성에 기인한다고 본다
장점> 속도가 빠르고 추가 메모리 공간을 필요로 하지 않는다
단점> 정렬된 리스트에 대해서 수행시간이 더 많이 걸린다. 이러한 불균형 분할을 방지하기 위해서 피벗을 선택할 때 단순히 리스트의 왼쪽 데이터를 사용하는 대신에 보다 리스트의 중앙 부분을 분할할 수 있는 데이터를 선택한다.
히프정렬(heap)
- 우선순위 큐를 완전 이진트리로 구현하는 방법으로 히프는 최댓값이나 최솟값을 쉽게 추출할 수 있는 자료구조이다.
> 히프에는 최소 히프와 최대 히프가 있고 정렬에서 최소히프를 사용하는 것이 프로그램을 쉽게 만든다. 최소 히프는 부모노드의 값이 자식노드의 값보다 작다. 따라서 최소히프의 루트노드는 가장 작은 값을 가지게 된다. 최소히프의 이러한 특성을 이용해서 정렬한 배열을 먼저 최소 히프로 변환한 다음, 가장 작은 원소부터 차례대로 추출하여 정렬하는 방법이 히프정렬이다.
기수정렬(radix sort)
> 기수 정렬은 레코드를 비교하지 않고도 정렬하는 방법이다. 기수정렬은 입력 데이터에 대해서 어떤 비교 연산도 실행하지 않고 데이터를 정렬할 수 있는 정렬 기법이다. 정렬에 기초한 방법들은 절대 O(n log2 n)이라는 이론적인 하한선을 깰 수 없는데 반하여 기수 정렬은 이 하한선을 깰 수 있는 유일한 기법이다
> 기수 정렬은 O(k n)의 시간복잡도를 가지는데 대부분 k <4이다. 다만 문제는 기수 정렬이 추가적인 메모리를 필요로 하는 것인데 이를 감수해도 기수 정렬이 다른 정렬기법보다 빠르기 때문에 데이터를 정렬하는 기법 중에 인기가 많다
> 단점은 정렬할 수 있는 레코드의 타입이 한정된다는 것이다. 기수 정렬을 사용하려면 레코드의 키들이 동일한 값을 가지는 숫자나 문자열로 구성되어야 한다
> 기수정렬은 다단계정렬이며 단계의 수는 데이터의 자릿수의 개수와 일치한다.
- 기수정렬 알고리즘
RadixSort(list, n):
for d<-LSD의위치 to MSD의 위치 do{
d번째 자리수에 따라 0번부터 9번 버킷에 넣는다
버킷에서 숫자들을 순차적으로 읽어서 하나의 리스트로 합친다
d++;
}- 각각의 버킷에 먼저 들어간 숫자들은 먼저 나와야 한다. 따라서 각각의 버킷은 큐로 구현해야 한다. 큐로 구현되어야 리스트 상에 있는 요소들의 상대적인 숫자가 유지된다
- 버킷에 숫자를 집어넣는 연산은 큐의 삽입 연산이 되고 버킷에서 숫자를 읽는 연산은 삭제연산으로 대처된다
- 버킷의 개수는 키의 표현방법과 밀접한 관계가 있다. 만약 키를 2진법을 사용하여 표현해서 정렬했다면 버킷은 2개만 있으면 된다
- 키가 알파벳 문자로 되어있다면 26개의 버킷이 필요하다. 기수정렬은 숫자로 이루어진 키의 경우에는 10개의 버킷을 가지고 분류할 수 있지만, 숫자의 이진표현을 이용해서도 기수정렬을 할 수 있다.
#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;
}
}
#define SIZE 10
int main(void)
{
int list[SIZE];
srand(time(NULL));
for (int i = 0; i<SIZE; i++)
list[i] = rand() % 100;
radix_sort(list, SIZE);
for (int i = 0; i<SIZE; i++)
printf("%d ", list[i]);
printf("\n");
return 0;
}
- 기수 정렬의 시간복잡도 -
> 입력 리스트가 n개의 정수를 가지고 있다고 하면 알고리즘의 내부 루프는 n번 반복이 된다. 만약 각 정수가 d개의 자릿수를 가지고 있다면 외부 루프는 d번 반복된다. 따라서 기수정렬은 O(d x n)의 시간복잡도를 가진다
> 시간복잡도가 d에 비례하기 때문에 기수 정렬의 수행시간은 정수의 크기와 관련이 있다. 일반적으로 d는 n에 비해 아주 작은 수가 되므로 기수정렬은 O(n)이라고 해도 무리가 없다.
> 기수 정렬은 다른 정렬에 비해 비교적 빠른 수행시간 안에 정렬을 마칠 수 있다. 그러나 기수 정렬은 정렬에 사용되는 키 값이 숫자로 표현되어야만 적용이 가능하다.
알고리즘 비교
| 알고리즘 | 최선 | 평균 | 최악 |
| 삽입정렬 | O(n) | 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^2) | O(n^1.5) | O(n^1.5) |
| 퀵정렬 | O(n log2n) | O(n log2n) | O(n^2) |
| 히프정렬 | O(n log2n) | O(n log2n) | O(n log2n) |
| 합병정렬 | O(n log2n) | O(n log2n) | O(n log2n) |
| 기수정렬 | O(dn) | O(dn) | O(dn) |