[Date Structure] 정렬
1. 정렬
- 정렬 : 순서가 없는 사물들을 순서(오름차순 또는 내림차순)대로 재배열하는 것
- 정렬되어 있지 않은 자료에 대해서는 탐색의 효율성이 크게 떨어진다.
- 레코드 : 정렬시켜야 할 대상
- 키 : 여러 필드들 중에서 특정한 레코드를 식별해주는 역할을 하는 것
- 정렬 : 레코드들을 키 값의 순서로 재배열하는 것
정렬 알고리즘의 분류
정렬 장소에 따른 분류
- 내부 정렬 : 정렬하기 전에 모든 데이터가 메인 메모리에 올라와 있는 정렬
- 외부 정렬 : 외부 기억 장치에 대부분의 데이터가 일부만 메모리에 올려놓은 상태에서 정렬하는 방법
구현 복잡도와 알고리즘 효율성에 따른 분류
- 단순하지만 비효율적인 방법 : 삽입 정렬, 선택 정렬, 버블 정렬
- 복잡하지만 효율적인 방법 : 퀵 정렬, 힙 정렬, 병합 정렬, 기수 정렬
안정성에 따른 분류
- 안정성 : 입력 데이터에 동일한 키 값을 갖는 레코드가 여러 개 존재할 경우, 정렬 후에도 이들의 상대적인 위치가 바뀌지 않는 것
- 안정성을 총족하는 정렬 : 삽입 정렬, 버블 정렬, 병합 정렬
| 비교 유무 | 방식 | 정렬 알고리즘 |
|---|---|---|
| X | 키 값에 따라 레코드 분배 | 기수 정렬 |
| O | 항목 교환 | 선택 정렬, 버블 정렬, 퀵 정렬 |
| 적절한 삽입 | 삽입 정렬, 셸 정렬 | |
| 분할과 병합 | 병합 정렬 |
2. 선택 정렬
- 전체 숫자들 중에서 가장 작은 숫자를 반복적으로 선택해 앞쪽으로 옮기는 방법
- 제자리 정렬 : 입력 배열 이외에 추가적인 메모리가 필요하지 않는다.
- 전체 숫자들을 정렬된 부분(왼쪽 리스트)와 정렬되지 않은 부분(오른쪽 리스트)으로 나누고, 처음에는 모든 숫자를 오른쪽 리스트에 넣는다.
- 오른쪽 리스트에서 가장 작은 숫자를 선택하여 왼쪽 리스트로 순서대로 이동시킨다.
- 오른쪽 리스트가 공백 상태가 될 때까지 반복한다.
#include <stdio.h>
#define SWAP(x, y, t) ((t) = (x), (x) = (y), (y) = (t))
void printArray(int arr [], int n, int *str)
{
int i;
printf("%s = ", str);
for (i = 0; i < n; i++) printf("%3d", arr[i]);
printf("\n");
}
void printStep(int arr [], int n, int val)
{
int i;
printf(" Step %2d = ", val);
for (i = 0; i < n; i++) printf("%3d", arr[i]);
printf("\n");
}
void selection_sort(int list [], int n)
{
int i, j, least, tmp;
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], tmp);
printStep(list, n, i + 1);
}
}
int main()
{
int n = 9;
int list[9] = {5, 3, 8, 4, 9, 1, 6, 2, 7};
printArray(list, 9, "Original ");
selection_sort(list, n);
printArray(list, n, "Selection");
}
실행 결과
Original = 5 3 8 4 9 1 6 2 7
Step 1 = 1 3 8 4 9 5 6 2 7
Step 2 = 1 2 8 4 9 5 6 3 7
Step 3 = 1 2 3 4 9 5 6 8 7
Step 4 = 1 2 3 4 9 5 6 8 7
Step 5 = 1 2 3 4 5 9 6 8 7
Step 6 = 1 2 3 4 5 6 9 8 7
Step 7 = 1 2 3 4 5 6 7 8 9
Step 8 = 1 2 3 4 5 6 7 8 9
Selection = 1 2 3 4 5 6 7 8 9
3. 삽입 정렬
정렬이 안 된 부분의 숫자를 정렬된 부분의 적절한 위치를 찾아 삽입하는 과정을 반복한다.
- 전체 숫자들을 정렬된 부분(왼쪽 리스트)와 정렬되지 않은 부분(오른쪽 리스트)으로 나누고, 처음에는 모든 숫자를 오른쪽 리스트에 넣는다.
- 정렬이 안 된 부분의 숫자를 정렬된 부분의 적절한 위치를 찾는다.
- 삽입할 항목보다 큰 항목들을 모두 한 칸씩 뒤쪽으로 이동시킨다.
- 숫자를 삽입한다.
- 이 과정을 정렬되지 않은 요소가 하나도 없을 때까지 반복한다.
#include <stdio.h>
void printArray(int arr [], int n, int *str)
{
int i;
printf("%s = ", str);
for (i = 0; i < n; i++) printf("%3d", arr[i]);
printf("\n");
}
void printStep(int arr [], int n, int val)
{
int i;
printf(" Step %2d = ", val);
for (i = 0; i < n; i++) printf("%3d", arr[i]);
printf("\n");
}
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;
printStep(list, n, i);
}
}
int main()
{
int n = 9;
int list[9] = {5, 3, 8, 4, 9, 1, 6, 2, 7};
printArray(list, 9, "Original ");
insertion_sort(list, n);
printArray(list, n, "Insertion");
}
실행 결과
Original = 5 3 8 4 9 1 6 2 7
Step 1 = 3 5 8 4 9 1 6 2 7
Step 2 = 3 5 8 4 9 1 6 2 7
Step 3 = 3 4 5 8 9 1 6 2 7
Step 4 = 3 4 5 8 9 1 6 2 7
Step 5 = 1 3 4 5 8 9 6 2 7
Step 6 = 1 3 4 5 6 8 9 2 7
Step 7 = 1 2 3 4 5 6 8 9 7
Step 8 = 1 2 3 4 5 6 7 8 9
Insertion = 1 2 3 4 5 6 7 8 9
- 시간 복잡도 : $O(n^2)$
- 레코드 양이 많거나 레코드 크기가 클 경우에 적합하지 않으며며, 레코드의 수가 적거나 대부분의 레코드가 이미 정렬되어 있는 경우에 효율적이다.
4. 버블 정렬
인접한 2개의 레코드를 비교하여 크기가 순서대로 되어 있지 않으면 서로 교환하는 방법
- 인접한 2개의 레코드를 비교하여 크기가 순서대로 되어 있지 않으면, 서로 교환한다.
- 리스트의 왼쪽 끝에서 오른쪽 끝으로 비교-교환 과정을 진행한다. (비교-교환 과정(스캔)이 완료되면, 가장 큰 레코드가 리스트의 오른쪽 끝으로 이동한다.)
- 더 이상 교환이 일어나지 않을 때까지 게속한다.
#include <stdio.h>
#define SWAP(x, y, t) ((t) = (x), (x) = (y), (y) = (t))
void printArray(int arr [], int n, int *str)
{
int i;
printf("%s = ", str);
for (i = 0; i < n; i++) printf("%3d", arr[i]);
printf("\n");
}
void printStep(int arr [], int n, int val)
{
int i;
printf(" Step %2d = ", val);
for (i = 0; i < n; i++) printf("%3d", arr[i]);
printf("\n");
}
void bubble_sort(int list [], int n)
{
int i, j, bChanged, tmp;
for (i = n - 1; i > 0; i--) {
bChanged = 0;
for (j = 0; j < i; j++)
if (list[j] > list[j + 1]) {
SWAP(list[j], list[j + 1], tmp);
bChanged = 1;
}
if (!bChanged) break;
printStep(list, n, n - i);
}
}
int main()
{
int n = 9;
int list[9] = {5, 3, 8, 4, 9, 1, 6, 2, 7};
printArray(list, 9, "Original ");
bubble_sort(list, n);
printArray(list, n, "Bubble ");
}
살행 결과
Original = 5 3 8 4 9 1 6 2 7
Step 1 = 3 5 4 8 1 6 2 7 9
Step 2 = 3 4 5 1 6 2 7 8 9
Step 3 = 3 4 1 5 2 6 7 8 9
Step 4 = 3 1 4 2 5 6 7 8 9
Step 5 = 1 3 2 4 5 6 7 8 9
Step 6 = 1 2 3 4 5 6 7 8 9
Bubble = 1 2 3 4 5 6 7 8 9
- 시간 복잡도 : $O(n^2)$
5. 함수 포인터를 사용한 정렬
6. 셀 정렬
- 리스트를 일정한 기준에 따라 분류해 연속적이지 않은 여러 개의 부분 리스트로 만든다.
- 각 부분 리스트를 삽입 정렬을 이용하여 정렬한다.
- 모든 부분 리스트가 정렬되면, 셸 정렬은 다시 전체 리스트를 더 적은 개수의 부분 리스트로 만들어 앞의 과정을 반복한다.
- 이 과정을 부분 리스트의 개수가 1이 될 때까지 반복한다.
- 간격 : 각 부분 리스트가 전체 리스트보부터 떨어진 거리
삽입 정렬에 비하여 셸 정렬은 2가지 장점
- 삽입 정렬에서는 한 번의 한 칸씩만 이동하는 반면, 연속적이지 않은 부분 파일에서 자료의 교환이 일어나면 더 큰 거리를 이동한다. 따라서 교환되는 아이템들이 삽입 정렬보다는 최종 위치에 더 가까이 있을 가능성이 높아진다.
- 부분 리스트가 하나가 되면 셸 정렬은 전체 리스트를 정렬해야 하지만, 거의 정렬된 리스트에 대한 삽입 정렬이므로 매우 효율적을 수행할 수 있다.
시간 복잡도
- 최악의 경우 : $O(n^2)$
- 평균적인 경우 : $O(n^{1.5})$
7. 병합 정렬
8. 퀵 정렬
- 평균적으로 매우 빠르다.
- 분할-정복법을 사용한다.
- 리스트 안에 있는 한 요소를 피벗으로 선택한다.
- 피벗보다 작은 요소들은 모두 피벗의 왼쪽으로 옯기고, 피벗보다 큰 요소들은 모두 피벗의 오른쪽으로 옮긴다.
- 피벗을 제외한 왼쪽 리스트와 오른쪽 리스트를 다시 정렬한다.
int partition(int list [], int left, int right)
{
int tmp;
int low = left + 1;
int high = right;
int pivot = list[left];
while (low < high) {
for (; low <= right && list[low < pivot; low++]);
for (; high >= left && list[high] > pivot; high--);
if (SWAP(list[low], list[high] > pivot; high--))
SWAP(list[low], list[high], tmp);
}
SWAP(list[left], list[high], tmp);
return high;
}