개론
정렬에는 여러가지 뜻이 있는데 대체로 "가지런히 줄지어 늘어섬. 또는 그렇게 함" 혹은 "영역, 항목, 데이터 따위를 미리 지정된 양식으로 맞추는 일." 등의 의미를 말한다.
어떻게 보면 우리가 정리하는 것과 같은 얘기를 하는 것이다.
우리가 현실 세계에서 책장을 정리한다고 했을 때 어떻게 정리하는가에 대해서 생각해보자.▼
책의 개수가 많지 않고 책장에 들어갈 자리가 넉넉하게 있다면, 크게 뭔가를 생각하지 않고 노동요를 틀고 하나씩 책장에 넣을 것이다.
그러면 컴퓨터에게 책 정리 시뮬레이팅을 시킨다고 해보자.▼
컴퓨터는 우리의 행동 하나하나를 전부 생각하고 있어야한다.
"책을 빼서 어디에 놓지?"
"책장의 전체 크기가 어느정도지?"
"이 책이 저 책보다 우선순위가 높은걸까?"
"이 책은 전체 책 중에서 우선순위가 어느정도 되는 거지?"
"이걸 먼저 1번칸에 넣었는데, 1번칸에 더 적합한 책을 발견한다면?"
이렇게 컴퓨터는 사람이 당연하게 여기는 모든 것들을 지정해줘야한다.
즉, 이런 모든 것들과 작동 방식에 대해서 정해주는 것을 정렬 알고리즘이라고 할 수 있다.
이번 포스트에서는 여러 정렬 알고리즘들에 대해서 알아볼 것이다.
거품 정렬
알고리즘 개념
거품 정렬은 두 인접한 원소를 검사하여 정렬하는 방법이다.
거품 정렬은 아래의 순서로 이루어진다.
- 첫 번째 원소와 두 번째 원소를 비교 후 크기 순으로 교환,
- 두 번째 원소와 세 번째 원소를 비교 후 크기 순으로 교환,
- 세 번째 원소와 네 번째 원소를 비교 후 크기 순으로 교환,
- 정렬이 될 때 까지 위의 과정을 반복한다.
알고리즘 예제
55, 07, 78, 12, 42라는 숫자를 거품 정렬 방식으로 정렬한다고 하면 아래와 같은 과정으로 진행된다.▼
장점과 단점
장점
- 구현이 굉장히 쉽고 간단하다.
- 배열 안에서 교환하는 방식(제자리 정렬, In-place Sort)이므로, 추가 메모리 공간이 필요하지 않다.
단점
- 현재 순서와 맞지 않은 원소도 인접한 원소와 교환한다.올바른 위치에 있는 원소가 교환될 수 도 있다.
- 왼쪽에서 오른쪽으로 이동할 때, 그 사이의 모든 원소와 교환한다.이 과정 때문에 연산 횟수가 많아진다.
- 시간복잡도가 O(n^2)으로 비효율적이다.
시간복잡도
O(n^2)의 시간복잡도로 굉장히 오래 걸린다.▼
| Name | Best | Avg | Worst | Run-time(n: 60,000) |
| 삽입 정렬 | $$ n^2 $$ | $$ n^2 $$ | $$ n^2 $$ | 7.438 |
| 선택 정렬 | $$ n^2 $$ | $$ n^2 $$ | $$ n^2 $$ | 10.842 |
| 버블 정렬 | $$ n^2 $$ | $$ n^2 $$ | $$ n^2 $$ | 22.894 |
| 셀 정렬 | $$ n $$ | $$ n^{1.5} $$ | $$ n^2 $$ | 0.056 |
| 퀵 정렬 | $$ n\log_2n $$ | $$ n\log_2n $$ | $$ n^2 $$ | 0.014 |
| 힙 정렬 | $$ n\log_2n $$ | $$ n\log_2n $$ | $$ n\log_2n $$ | 0.034 |
| 병합 정렬 | $$ n\log_2n $$ | $$ n\log_2n $$ | $$ n\log_2n $$ | 0.026 |
| 기수 정렬 | $$ - $$ | $$ n $$ | $$ - $$ | 0.041 |
구현 코드 (C, C++)
int* bubble_sort(int arr[], int n)
{
int i, j, temp;
for (i=n-1; i>0; i--)
{
for (j=0; j<i; j++)
{
if (arr[j] > arr[j+1])
{
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
return arr;
}
선택 정렬(Selection Sort)
알고리즘 개념
선택 정렬은 제자리 정렬 알고리즘의 하나이다.
해당 순서에 원소를 넣을 위치는 이미 정해져있고, 어떤 원소를 넣을 지 선택하는 방법이다.
선택정렬은 아래의 순서로 이루어진다.
- 주어진 리스트 중에 최소값을 찾는다.
- 그 값을 맨 앞에 위챃나 값과 교체한다.
- 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다.
알고리즘 예제
9, 1, 6, 8, 4, 3, 2, 0라는 숫자를 선택 정렬 방식으로 정렬한다고 하면 아래와 같은 과정으로 진행된다.▼
장점과 단점
장점
- 구현하기 쉽다.
- 자료의 이동 횟수가 미리 결정된다.
- 정렬을 위한 비교 횟수는 많은 편이지만, 거품 정렬에 비해 실제로 교환하는 횟수는 적기 때문에 많은 교환이 일어나야 하는 자료에서는 비교적 효율적이다.
- 배열 안에서 교환하는 방식(제자리 정렬, In-place Sort)이므로, 추가 메모리 공간이 필요하지 않다.
단점
- 불안정 정렬(Unstable Sort)이다.값이 같은 원소가 있는 경우에 상대적인 위치가 변경될 수 있다.
- 시간복잡도가 O(n^2)으로 비효율적이다.
시간복잡도
Big - O 표기법으로는 거품 정렬(버블 정렬)과 같지만, 실제로는 좀 더 빠르다.
하지만 거품 정렬보다 빠를 뿐 여전히 오래걸리는 정렬 방식이다.▼
| Name | Best | Avg | Worst | Run-time(n: 60,000) |
| 삽입 정렬 | $$ n^2 $$ | $$ n^2 $$ | $$ n^2 $$ | 7.438 |
| 선택 정렬 | $$ n^2 $$ | $$ n^2 $$ | $$ n^2 $$ | 10.842 |
| 버블 정렬 | $$ n^2 $$ | $$ n^2 $$ | $$ n^2 $$ | 22.894 |
| 셀 정렬 | $$ n $$ | $$ n^{1.5} $$ | $$ n^2 $$ | 0.056 |
| 퀵 정렬 | $$ n\log_2n $$ | $$ n\log_2n $$ | $$ n^2 $$ | 0.014 |
| 힙 정렬 | $$ n\log_2n $$ | $$ n\log_2n $$ | $$ n\log_2n $$ | 0.034 |
| 병합 정렬 | $$ n\log_2n $$ | $$ n\log_2n $$ | $$ n\log_2n $$ | 0.026 |
| 기수 정렬 | $$ - $$ | $$ n $$ | $$ - $$ | 0.041 |
구현 코드(C, C++)
void selectionSort(int *list, const int n)
{
int i, j, indexMin, temp;
for (i = 0; i < n - 1; i++)
{
indexMin = i;
for (j = i + 1; j < n; j++)
{
if (list[j] < list[indexMin])
{
indexMin = j;
}
}
temp = list[indexMin];
list[indexMin] = list[i];
list[i] = temp;
}
}
삽입 정렬(Insertion Sort)
알고리즘 개념
자료의 모든 원소를 앞에서부터 차례대로 이미 정렬된 부분과 비교하여, 자신의 위치를 찾아 삽입하는 방법이다.
삽입정렬은 아래의 순서로 이루어진다.
- 자료의 두 번째 원소부터 시작하여, 그 앞의 원소들과 비교하여 삽입할 위치를 지정한다.
- 위치를 정했다면 해당 위치부터 뒤의 모든 자료를 뒤로 이동하고 나온 빈 자리에 자료를 삽입한다.
- 두 번째 원소는 첫 번째 원소와, 세 번째 원소는 첫 번째와 두 번째 원소와, 네 번째는 첫 번째, 두번째, 세 번째 ...이렇게 반복해주면 된다.
알고리즘 예제
31, 25, 12, 22, 11 이라는 숫자를 삽입 정렬 방식으로 정렬한다고 하면 아래와 같은 과정으로 진행된다.▼
장점과 단점
장점
- 구현하기 쉽다.
- 원소의 대다수가 정렬되어 있다면, 효율적으로 수행된다.
- 배열 안에서 교환하는 방식(제자리 정렬, In-place Sort)이므로, 추가 메모리 공간이 필요하지 않다.
- 안정 정렬(Stable Sort)이다.
- 거품 정렬과 선택 정렬과 같은 시간복잡도O(n^2)를 가지고 있지만 두 정렬법보다 좀 더 빠르다.
단점
- 거품 정렬과 선택 정렬보다 빠른 것 뿐이지 시간복잡도 자체는 O(n^2)이므로, 비효율적이다.이로 인해 배열 크기가 커지면 연산 횟수가 크게 증가한다.
- 원소가 상대적으로 많이 이동하게 된다.
시간복잡도
거품 정렬, 선택 정렬과 같은 시간 복잡도이지만 실제 작동 시간으로는 조금 더 빠르다.
그러나 거품 정렬과 선택 정렬보다 조금 더 빠를 뿐이지 여전히 시간 복잡도는 O(n^2)으로 비효율적이다.▼
| Name | Best | Avg | Worst | Run-time(n: 60,000) |
| 삽입 정렬 | $$ n^2 $$ | $$ n^2 $$ | $$ n^2 $$ | 7.438 |
| 선택 정렬 | $$ n^2 $$ | $$ n^2 $$ | $$ n^2 $$ | 10.842 |
| 버블 정렬 | $$ n^2 $$ | $$ n^2 $$ | $$ n^2 $$ | 22.894 |
| 셀 정렬 | $$ n $$ | $$ n^{1.5} $$ | $$ n^2 $$ | 0.056 |
| 퀵 정렬 | $$ n\log_2n $$ | $$ n\log_2n $$ | $$ n^2 $$ | 0.014 |
| 힙 정렬 | $$ n\log_2n $$ | $$ n\log_2n $$ | $$ n\log_2n $$ | 0.034 |
| 병합 정렬 | $$ n\log_2n $$ | $$ n\log_2n $$ | $$ n\log_2n $$ | 0.026 |
| 기수 정렬 | $$ - $$ | $$ n $$ | $$ - $$ | 0.041 |
구현 코드(C, C++)
void insertion_sort ( int *data, int n )
{
int i, j, remember;
for ( i = 1; i < n; i++ )
{
remember = data[(j=i)];
while ( --j >= 0 && remember < data[j] )
data[j+1] = data[j];
data[j+1] = remember;
}
}
위 코드는 직접 자료를 밀었다면, 아래 코드는 memcpy()를 이용하여 자료를 밀어내는 방식으로 위 코드보다 더 빠르게 수행된다.
void insertion_sort ( int *data, int n )
{
int i, j, remember;
i = n-1;
while ( i-- > 0 )
{
remember = data[(j=i)];
while (++j < n && remember > data[j]);
if ( --j == i ) continue;
memcpy(data+i, data+i+1, sizeof(*data) * (j-i));
data[j] = remember;
}
}
퀵 정렬(Quick Sort)
알고리즘 개념
퀵 정렬은 분할 정복(dive and conquer)방법으로 다른 원소들과의 비교만으로 정렬을 수행하는 비교 정렬법이다.
퀵 정렬은 아래의 순서로 이루어진다.
- 리스트 가운데서 하나의 원소를 고른다. 이렇게 고른 원소를 피벗(pivot)이라고 한다.
- 피벗 앞에는 피벗보다 작은 모든 원소들이 오고, 피벗 뒤에는 피벗보다 값이 큰 모든 원소들이 오도록 피벗을 기준으로 리스트를 둘로 나눈다.
- 분할된 두 개의 작은 리스트에 대해 재귀적으로 이 과정을 반복한다.재귀는 리스트의 크기가 0이나 1이 될 때 까지 반복한다.
알고리즘 예제
5, 3, 7, 6, 2, 1, 4 라는 숫자를 퀵 정렬 방식으로 정렬한다고 하면 아래와 같은 과정으로 진행된다.▼
장점과 단점
장점
- 속도가 빠르다.
- 추가 메모리 공간을 필요로 하지 않는다.(퀵 정렬은 O(log n)만큼의 메모리를 필요로 한다.)
단점
- 정렬된 리스트일 경우 퀵 정렬의 불균형 분할에 의해 오히려 수행시간이 오래 걸린다.
퀵 정렬의 불균형 분할을 방지하기 위하여 피벗을 선택할 때 균등하게 분할 할 수 있는 데이터를 선택하면 해결되지만,그렇게 할 수 없다면 최악의 경우에 도달할 수 있으므로 다른 정렬법을 선택하는 것이 좋다.
시간복잡도
최선의 경우와 최악의 경우가 생길 수 있다.
| Name | Best | Avg | Worst | Run-time(n: 60,000) |
| 삽입 정렬 | $$ n^2 $$ | $$ n^2 $$ | $$ n^2 $$ | 7.438 |
| 선택 정렬 | $$ n^2 $$ | $$ n^2 $$ | $$ n^2 $$ | 10.842 |
| 버블 정렬 | $$ n^2 $$ | $$ n^2 $$ | $$ n^2 $$ | 22.894 |
| 셀 정렬 | $$ n $$ | $$ n^{1.5} $$ | $$ n^2 $$ | 0.056 |
| 퀵 정렬 | $$ n\log_2n $$ | $$ n\log_2n $$ | $$ n^2 $$ | 0.014 |
| 힙 정렬 | $$ n\log_2n $$ | $$ n\log_2n $$ | $$ n\log_2n $$ | 0.034 |
| 병합 정렬 | $$ n\log_2n $$ | $$ n\log_2n $$ | $$ n\log_2n $$ | 0.026 |
| 기수 정렬 | $$ - $$ | $$ n $$ | $$ - $$ | 0.041 |
최선의 경우
자료가 계속해서 균등하게 나뉘게 되면, 아래와 같이 계산할 수 있다.
원소의 개수 n이 2의 거듭제곱(2의 k승)이라고 하면, 계속 절반씩 균등하게 나뉘어 log2(n)번 재귀호출을 하게 된다.
각 재귀호출에서 원소 대부분을 비교해야하기 때문에 비교횟수는 n번이라고 하면,
nlog2(n)이라는 연산 횟수가 나온다.
이동 횟수는 비교횟수보다 적으므로 Big-O 표기법에서는 무시할 수 있다.
즉, 최선의 경우는 O(nlog2(n))이 된다.
최악의 경우
최선의 경우와는 반대로 자료가 계속 불균형하게 나뉘게 되면 하나씩 계속 남게 되어 n번 재귀호출을 하게 된다.
여기서도 마찬가지로 각 재귀호출에서 원소 대부분을 비교해야하기 때문에 비교횟수는 n번이라고 하면,
n * n 이라는 연산 횟수가 나온다.
이동 횟수는 비교횟수보다 적으므로 Big-O 표기법에서는 무시할 수 있다.
즉, 최악의 경우는 O(n^2)이 된다.
위의 두 경우와 같이 최악의 경우에는 앞에 봤던 정렬들과 같이 O(n^2)의 시간복잡도를 가지게 되지만, 평균적으로는 가장 빠른 모습을 보여준다.
최악의 경우만 피해준다면 압도적인 속도를 보여준다.
구현 코드(C, C++)
#include <algorithm>//swap
void quickSort(int A[], int low, int high)
{
if(low >= high) return;
// base condition
// divide processint
i = low, j = low;
int &pivot = A[high];
for (; j < high; ++j)
{
if (A[j] < pivot)
swap(A[i++], A[j]);
}
swap(A[i], pivot);
// conquer process
quickSort(A, low, i-1);
quickSort(A, i+1, high);
}
합병 정렬(Merge Sort)
알고리즘 개념
하나의 자료를 두 개의 균등하게 분할하여 각각을 정렬한 후, 두 개의 정렬된 부분 자료를 합하여 정렬하는 방법이다.
합병 정렬은 아래의 순서로 이루어진다.
- 리스트의 길이가 1이하이면 이미 정렬된 것으로 본다.그렇지 않은 경우에 아래의 과정을 수행한다.
- 분할(divide) : 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.
- 정복(conquer) : 두 부분 리스트를 합병 정렬을 이용해 정렬한다.
- 결합(combine) : 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다.이때 정렬 결과가 임시 배열에 저장된다.
- 임시 배열에 저장된 결과를 원래 배열에 복사한다.
알고리즘 예제
19, 99, 5, 3, 11, 13 이라는 숫자를 합병 정렬로 정렬한다고 하면 아래와 같은 순서로 정렬된다.▼
장점과 단점
장점
- 어떤 순서로 원소가 들어와도 개수만 같다면 정렬되는 시간은 동일하다.
- 연결리스트로 구현할 경우 원소의 이동을 거의 무시할 수 있다.제자리 정렬로 구현할 수 있다.
단점
- 배열로 합병 정렬을 구현하면 추가로 임시 배열을 만들어야한다.제자리 정렬로 구현할 수 없어진다.
- 원소의 개수가 많은 경우 이동 횟수도 비례하여 커지게 되어 시간이 오래걸리게 된다.
시간복잡도
합병 정렬은 분할과 합병으로 구분되지만, 분할 과정에서는 추가 연산이 없어서 무시해도 된다.
합병 과정에서의 시간만 구하면 O(nlog2(n))의 시간복잡도를 갖는다.
퀵 정렬보다는 느리지만 안정적이라는 장점이 있다.▼
| Name | Best | Avg | Worst | Run-time(n: 60,000) |
| 삽입 정렬 | $$ n^2 $$ | $$ n^2 $$ | $$ n^2 $$ | 7.438 |
| 선택 정렬 | $$ n^2 $$ | $$ n^2 $$ | $$ n^2 $$ | 10.842 |
| 버블 정렬 | $$ n^2 $$ | $$ n^2 $$ | $$ n^2 $$ | 22.894 |
| 셀 정렬 | $$ n $$ | $$ n^{1.5} $$ | $$ n^2 $$ | 0.056 |
| 퀵 정렬 | $$ n\log_2n $$ | $$ n\log_2n $$ | $$ n^2 $$ | 0.014 |
| 힙 정렬 | $$ n\log_2n $$ | $$ n\log_2n $$ | $$ n\log_2n $$ | 0.034 |
| 병합 정렬 | $$ n\log_2n $$ | $$ n\log_2n $$ | $$ n\log_2n $$ | 0.026 |
| 기수 정렬 | $$ - $$ | $$ n $$ | $$ - $$ | 0.041 |
구현 코드(C, C++)
// 2-way devide
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];
}
// merge
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);
}
}
힙 정렬(Heap Sort)
알고리즘 개념
최대 힙 트리나 최소 힙 트리를 구성해 정렬을 하는 방법으로 내림차 순 정렬을 위해서는 최대 힙을 구성하고, 오름차 순 정렬을 위해서는 최소 힙을 구성하면 된다.
힙 정렬은 아래의 순서로 이루어진다.
- n개의 노드에 대한 완전 이진 트리를 구성한다. 이 때 루트 노드부터 부모 노드, 왼쪽 자식 노드, 오른쪽 자식 노드 순으로 구성한다.
- 최대 힙을 구성한다. 최대 힙이란 부모 노드가 자식 노드보다 큰 트리를 말하는데, 단말 노드를 자식 노드로 가진 부모노드부터 구성하며 아래부터 루트까지 올라오며 순차적으로 만들어 갈 수 있다.
- 가장 큰 수 (루트에 위치)를 가장 작은 수와 교환한다.
- 2번과 3번 과정을 반복한다.
힙 정렬을 제대로 이해하려면 힙에 대해 자세히 알아야한다.
(힙은 다음 포스트에서 더 자세하게 다루는 것으로 하겠다.)
알고리즘 예제
6, 5, 3, 1, 8, 7, 2, 4 라는 숫자를 힙 정렬로 정렬한다고 하면 아래와 같은 순서로 정렬된다.▼
장점과 단점
장점
- 전체를 정렬하기 보다 가장 앞부분의 값들이나 가장 뒷부분의 값들 일부가 필요할 때 굉장히 유용하다.
- 정렬 시간이 빠른 편에 속한다.
단점
- 정렬을 위해서 힙을 구현해야한다. 구현하지 않더라도 힙 라이브러리를 가져다 써야한다.
시간복잡도
O(nlog2(n))으로 빠른편에 속한다.
하지만 병합 정렬과 퀵 정렬보다는 조금 느리다.
| Name | Best | Avg | Worst | Run-time(n: 60,000) |
| 삽입 정렬 | $$ n^2 $$ | $$ n^2 $$ | $$ n^2 $$ | 7.438 |
| 선택 정렬 | $$ n^2 $$ | $$ n^2 $$ | $$ n^2 $$ | 10.842 |
| 버블 정렬 | $$ n^2 $$ | $$ n^2 $$ | $$ n^2 $$ | 22.894 |
| 셀 정렬 | $$ n $$ | $$ n^{1.5} $$ | $$ n^2 $$ | 0.056 |
| 퀵 정렬 | $$ n\log_2n $$ | $$ n\log_2n $$ | $$ n^2 $$ | 0.014 |
| 힙 정렬 | $$ n\log_2n $$ | $$ n\log_2n $$ | $$ n\log_2n $$ | 0.034 |
| 병합 정렬 | $$ n\log_2n $$ | $$ n\log_2n $$ | $$ n\log_2n $$ | 0.026 |
| 기수 정렬 | $$ - $$ | $$ n $$ | $$ - $$ | 0.041 |
구현 코드(C, C++)
void downheap(int cur, int k)
{
int left, right, p;
while(cur < k)
{
left = cur * 2 + 1;
right = cur * 2 + 2;
if (left >= k && right >= k) break;
p = cur;
if (left < k && data[p] < data[left])
p = left;
if (right < k && data[p] < data[right])
p = right;
if (p == cur) break;
swap(&data[cur],&data[p]);
cur=p;
}
}
void heapify(int n)
{
int i,p;
for(i = (n-1)/2; i >= 0; i--)
{
downheap(i,n);
}
//for(i=0;i<size;++i)printf("%d ",data[i]);
//printf("\n");
}
void heap()
{
int k;
heapify(size);
for(k = size-1; k > 0; )
{
swap(&data[0],&data[k]);
//k--;
downheap(0,k);
k--;
}
}
기수 정렬(Radix Sort)
알고리즘 개념
기수정렬은 낮은 자리수부터 비교하여 정렬하는 정렬 알고리즘이다.
비교 연산을 하지 않으며 정렬 속도가 빠르지만 메모리가 추가로 많이 필요하다.
지금은 10진수를 기본으로 하지만, 몇 진수냐에 따라 데이터 형태가 달라진다.
그래도 10진수를 일상적으로 사용하니까 10진수를 기본으로 설명하겠다.
- 0부터 9까지의 큐(Queue)자료 구조를 만들어놓는다.
- 가장 끝 자리부터 아래의 정렬을 시작한다.
- 이전에 정렬한 것을 기준으로, 현재 자리수의 숫자에 맞게 큐 자료구조에 넣어준다.
(321인데 끝자리 기준이라면, 1번 큐에 넣어준다.) - 자리수를 한 칸 앞으로 옮겨준다.
만약에 맨 앞자리였다면 정렬을 종료한다.
알고리즘 예제
675, 369, 272, 095, 110, 853, 299, 571, 230, 474, 533, 278, 197, 693, 423, 168, 501, 068, 502, 187 의 순서대로 숫자들이 있다고 하자.
1. 끝자리 기준으로 정렬
끝자리를 기준으로 순서대로 아래의 2차원 배열에 넣어준다.
| 순서 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 0 | 110 | 571 | 272 | 853 | 474 | 675 | 197 | 278 | 369 | |
| 1 | 230 | 501 | 533 | 095 | 187 | 168 | 299 | |||
| 2 | 423 | 068 |
2. 두 번째 자리 기준으로 정렬
1번에서 정렬한 것을 바탕으로 두 번째 자리 기준으로 정렬한다.
| 순서 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 0 | 501 | 110 | 423 | 230 | 853 | 168 | 571 | 187 | 693 | |
| 1 | 502 | 533 | 068 | 272 | 095 | |||||
| 2 | 369 | 474 | 197 | |||||||
| 3 | 675 | 299 | ||||||||
| 4 | 278 |
3. 앞자리 기준으로 정렬
2번에서 정렬한 것을 바탕으로 앞자리 기준으로 정렬한다.
| 순서 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 0 | 068 | 110 | 230 | 369 | 423 | 501 | 675 | 853 | ||
| 1 | 095 | 168 | 272 | 474 | 502 | |||||
| 2 | 187 | 278 | 533 | |||||||
| 197 | 297 | 571 |
맨 앞자리 기준으로 정렬이 끝났다면 해당 표의 순서대로 배열에 담아주면 된다.
장점과 단점
장점
- 정수뿐만 아니라 문자열도 정렬할 수 있다.
- 안정 정렬이다.
- 굉장히 빠르게 정렬할 수 있다.
단점
- 자리수가 없다면 정렬할 수 없다.
- 추가적인 메모리가 필요하다.
시간복잡도
d자리, r진수의 수가 N개 있을 때 radix sort를 한다면,
바구니 갯수 r개
단계의 수 d단계
한 단계당 N번
이를 `Big-O notation`으로 표기하면, $$ O(d\cdot N) $$ 이다.
| Name | Best | Avg | Worst | Run-time(n: 60,000) |
| 삽입 정렬 | $$ n^2 $$ | $$ n^2 $$ | $$ n^2 $$ | 7.438 |
| 선택 정렬 | $$ n^2 $$ | $$ n^2 $$ | $$ n^2 $$ | 10.842 |
| 버블 정렬 | $$ n^2 $$ | $$ n^2 $$ | $$ n^2 $$ | 22.894 |
| 셀 정렬 | $$ n $$ | $$ n^{1.5} $$ | $$ n^2 $$ | 0.056 |
| 퀵 정렬 | $$ n\log_2n $$ | $$ n\log_2n $$ | $$ n^2 $$ | 0.014 |
| 힙 정렬 | $$ n\log_2n $$ | $$ n\log_2n $$ | $$ n\log_2n $$ | 0.034 |
| 병합 정렬 | $$ n\log_2n $$ | $$ n\log_2n $$ | $$ n\log_2n $$ | 0.026 |
| 기수 정렬 | $$ - $$ | $$ n $$ | $$ - $$ | 0.041 |
구현 코드(C, C++)
void Radix_Sort() {
int Radix = 1;
while (1) {
if (Radix >= Max_Value)
break;
Radix = Radix * 10;
}
for (int i = 1; i < Radix; i = i * 10) {
for (int j = 0; j < MAX; j++) {
int K;
if (Arr[j] < i)
K = 0;
else
K = (Arr[j] / i) % 10;
Q[K].push(Arr[j]);
}
int Idx = 0;
for (int j = 0; j < 10; j++)
{
while (Q[j].empty() == 0)
{
Arr[Idx] = Q[j].front();
Q[j].pop();
Idx++;
}
}
}
}
셸 정렬 (Shell Sort)
알고리즘 개념
도널드 셸이 만든 셸 정렬은 기본적으로 삽입정렬을 보완한 정렬법이다.
셸 정렬은 아래의 삽입 정렬의 특성을 이용, 보완한 정렬법이다.
- 삽입 정렬은 입력되는 초기리스트가 “거의 정렬”되어 있을 경우에 효율적이다.
- 삽입 정렬은 한 번에 한 요소의 위치만 결정되기 때문에 비효율적이다.
셸 정렬은 크게 다음과 같은 과정으로 나눈다.
- 데이터를 일정 개수로 나누어서 삽입 정렬한다.
- 데이터를 다시 잘게 나누어 삽입 정렬한다.
- 이 과정을 반복한다.
알고리즘 예제
2, 5, 3, 4, 3, 9, 3, 2, 5, 4, 1, 3로 리스트가 주어졌다고 해보자.
1. 이를 3행으로 구성하여 열 단위로 삽입정렬한다.
전
| 2 | 5 | 3 | 4 |
| 3 | 9 | 3 | 2 |
| 5 | 4 | 1 | 3 |
후
| 2 | 4 | 1 | 2 |
| 3 | 5 | 3 | 3 |
| 5 | 9 | 3 | 4 |
2. 정렬된 3행 행렬을 6행렬로 나열하여 열 단위로 정렬한다.
전
| 2 | 4 |
| 1 | 2 |
| 3 | 5 |
| 3 | 3 |
| 5 | 9 |
| 3 | 4 |
후
| 1 | 2 |
| 2 | 3 |
| 3 | 4 |
| 3 | 4 |
| 3 | 5 |
| 5 | 9 |
3. 이를 1열로 나열하여 삽입 정렬한다.
전
| 1 | 2 | 2 | 3 | 3 | 4 | 3 | 4 | 3 | 5 | 5 | 9 |
후
| 1 | 2 | 2 | 3 | 3 | 3 | 3 | 4 | 4 | 5 | 5 | 9 |
장점과 단점
장점
- 연속적이지 않은 부분 리스트에서 자료를 교환하게 되면 더 먼 거리를 이동한다.
- 부분 리스트는 어느 정도 정렬된 상태이다.
부분 리스트의 개수가 1개가 되면 셸 정렬은 삽입 정렬을 하긴 하지만 삽입 정렬보다 더 빠르게 수행된다. - 알고리즘이 간단하다.
단점
- 간격을 잘못 설정한다면 성능이 굉장히 안 좋아질 수 있다.
일반적으로 데이터를 나누는 값은 보통 전체에서 2로 나누는 값으로 진행한다. (N/2)
하지만 3을 나누고 1을 더하는 경우가 더 빠르다고 알려져 있다. (N/3 + 1)
시간복잡도
평균: $$ O(n^{1.5}) $$
최악의 경우: $$ O(n^2) $$
| Name | Best | Avg | Worst | Run-time(n: 60,000) |
| 삽입 정렬 | $$ n^2 $$ | $$ n^2 $$ | $$ n^2 $$ | 7.438 |
| 선택 정렬 | $$ n^2 $$ | $$ n^2 $$ | $$ n^2 $$ | 10.842 |
| 버블 정렬 | $$ n^2 $$ | $$ n^2 $$ | $$ n^2 $$ | 22.894 |
| 셀 정렬 | $$ n $$ | $$ n^{1.5} $$ | $$ n^2 $$ | 0.056 |
| 퀵 정렬 | $$ n\log_2n $$ | $$ n\log_2n $$ | $$ n^2 $$ | 0.014 |
| 힙 정렬 | $$ n\log_2n $$ | $$ n\log_2n $$ | $$ n\log_2n $$ | 0.034 |
| 병합 정렬 | $$ n\log_2n $$ | $$ n\log_2n $$ | $$ n\log_2n $$ | 0.026 |
| 기수 정렬 | $$ - $$ | $$ n $$ | $$ - $$ | 0.041 |
C/C++ 코드
void insertion_sort(int list[], int first, int last, int gap) {
int key;
for (int i = first + gap; i <= last; i += gap) {
key = list[i];
for (int j = i - gap; first <= j && key < list[j]; j -= gap)
list[j + gap] = list[j];
}
return ;
}
void shell_sort(int list[], int n) {
for (int gap = n / 2; gap > 0; gap /= 2) {
if (gap % 2 == 0)
gap++;
for (int i = 0; i < gap; i++)
insertion_sort(list, i, n - 1, gap);
}
}'Algorithm > Algorithm 개념' 카테고리의 다른 글
| 기본적인 자료구조 (0) | 2024.01.27 |
|---|---|
| 배열(array)과 연결 리스트(linked list) (0) | 2024.01.23 |
| 브루트 포스 (0) | 2024.01.20 |
| 간단한 수학(+ 약간의 정수론) (0) | 2024.01.19 |
| 알고리즘과 입출력 (0) | 2024.01.18 |
