정렬(Sorting)
- 정렬(sorting) : 물건을 크기순으로 오름차순(ascending order)이나 내림차순(descending order)으로 나열하는 것.
- 정렬은 컴퓨터공학을 포함한 모든 과학 기술 분야에서 가장 기본적이고 중요한 알고리즘 중의 하나로 일상생활에서 많이 사용됨.
- 정렬은 자료 탐색에 있어서 필수적임.
- 일반적으로 정렬시켜야 될 대상은 레코드(record)라고 불림.
- 레코드는 다시 필드(field)라고 하는, 더 작은 단위로 나누어짐.
- 여러 필드 중에서 특별히 레코드와 레코드를 식별해주는 역할을 하는 필드를 키(key)라고 함.
레코드 { [필드][필드][필드][필드][필드][필드][필드][필드][필드][필드]
레코드 { [필드][필드][필드][필드][필드][필드][필드][필드][필드][필드]
↖
키
- 정렬이란 결국 레코드들을 키 값의 순서로 재배열하는 것을 의미함.
- 지금까지 개발된 정렬 알고리즘은 매우 많음. 그러나 아직까지도 모든 경우에 있어서 최상의 성능을 보여주는 최적 알고리즘은 존재하지 않음. 따라서 이들 방법들 중에서 현재의 프로그램 수행 환경에 가장 효율적인 정렬 알고리즘을 선택하여야 함.
- 대개 정렬 알고리즘을 평가하는 효율성의 기준으로는 정렬을 위해 필요한 비교 연산의 횟수와 이동 연산의 횟수. -> 빅오 표기법을 이용하여 근사적으로 표현함
-> 자료의 초기화 여부에 의존적임.
- 일반적으로 이동 횟수와 비교 횟수가 서로 비례하지 않음. -> 어떤 알고리즘은 비교 횟수는 많지만 이동 횟수는 작을 수 있고 또 그 반대도 가능함.
- 숫자와 숫자를 비교하는 것은 시간이 걸리지 않지만 문자열과 문자열을 비교하는 것은 상당히 시간이 걸리는 작업임.
- 숫자를 이동시키는 것은 간단하지만 큰 구조체를 이동시키려면 상당한 시간이 걸림.
- 따라서 현재 개발 중인 응용에 맞추어서 가장 적절한 정렬 알고리즘을 선택해야 함.
- 정렬 알고리즘은 크게 2가지로 나누어짐.
1. 단순하지만 비효율적인 방법 - 삽입 정렬, 선택 정렬, 버블 정렬 등
2. 복잡하지만 효율적인 방법 - 퀵 정렬, 히프 정렬, 합병 정렬, 기수 정렬 등
- 자료의 개수가 적다면 단순한 정렬 방법을 사용하는 것도 괜찮지만, 자료의 개수가 일정 개수를 초과하면 반드시 효율적인 알고리즘을 사용해야 함.
- 정렬 알고리즘을 내부 정렬(internal sorting)과 외부 정렬(external sorting)로 구분할 수도 있음.
- 내부 정렬 : 모든 데이터가 주기억장치에 저장된 상태에서 정렬하는 방법.
- 외부 정렬 : 외부기억장치(하드디스크)에 대부분의 데이터가 있고 일부만 주기억장치에 저장된 상태에서 정렬하는 방법.
- 정렬 알고리즘을 안정성(stability)의 측면에서 분류할 수도 있음.
- 정렬 알고리즘에서 안정성이란 입력 데이터에 동일한 키 값을 갖는 레코드가 여러 개 존재할 경우, 이들 레코드들의 상대적인 위치가 정렬 후에도 바뀌지 않음을 뜻함.
- 이와 반대로 같은 키 값을 갖는 레코드들이 정렬 후에 위치가 바뀌게 되면 안정하지 않다고 함.
- 정렬의 안정성이 필수적으로 요구되는 경우에는 정렬 알고리즘 중에서 안정성을 충족하는 삽입 정렬, 합병 정렬 등을 사용해야 함.
[선택 정렬]
- 선택 정렬(selection sort) : 가장 이해하기가 쉬운 정렬 방법
- 먼저 왼쪽 리스트와 오른쪽 리스트의 두 개의 리스트가 있다고 가정.
- 왼쪽 리스트에는 정렬이 완료된 숫자들이 들어 있고, 오른쪽 리스트에는 정렬되지 않은 숫자들이 들어 있음.
- 선택 정렬은 오른쪽 리스트에서 가장 작은 숫자를 선택하여 왼쪽 리스트로 이동하는 작업을 되풀이함.
- 선택 정렬은 오른쪽 리스트가 공백 상태가 될 때까지 이 과정을 되풀이하는 정렬 기법.
| 왼쪽 리스트 | 오른쪽 리스트 | 설명 |
| () | (5, 3, 8, 1, 2, 7) | 초기 상태 |
| (1) | (5, 3, 8, 2, 7) | 1선택 |
| (1, 2) | (5, 3, 8, 7) | 2선택 |
| (1, 2, 3) | (5, 8, 7) | 3선택 |
| (1, 2, 3, 5) | (8, 7) | 4선택 |
| (1, 2, 3, 5, 7) | (8) | 5선택 |
| (1, 2, 3, 5, 7, 8) | () | 6선택 |
- 이를 구현하기 위해서는 입력 배열과는 별도로 똑같은 크기의 배열이 하나 더 필요함.
- 메모리를 절약하기 위하여 입력 배열 외에 추가적인 공간을 사용하지 않는 선택 정렬 알고리즘을 고려함.
- 제자리 정렬(in-place sorting) : 입력 배열 이외에는 다른 추가 메모리를 요구하지 않는 정렬 방법
-> 입력 배열에서 최솟값을 발견한 다음, 이 최솟값을 배열의 첫 번째 요소와 교환함.
-> 그 다음에는 첫 번째 요소를 제외한 나머지 요소들 중에서 가장 작은 값을 선택하고 이를 두 번째 요소와 교환함.
-> 이 절차를 (숫자 개수 - 1)만큼 되풀이하면 추가적인 배열을 사용하지 않고서도 전체 숫자들이 정렬됨.
- 선택 정렬 프로그램
// 선택 정렬 프로그램
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 10000
#define SWAP(x, y, t) ( (t) = (x), (x)=(y), (y)=(t) ) // 레코드와 레코드를 서로 교환하기 위해 SWAP 매크로 사용
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);
}
}
void main() {
int i;
n = MAX_SIZE;
for (i = 0; i < n; i++) { // 난수 생성 및 출력
list[i] = rand() % n; // 난수 발생 범위 0~n
}
selection_sort(list, n); // 선택 정렬 호출
for (i = 0; i < n; i++) {
printf("%d\n", list[i]);
}
}
- 외부 루프는 n-1번 실행될 것이며, 내부 루프는 0에서 n-2번까지 변하는 i에 대하여 (n-1)-i번 반복됨.
- 키 값들의 비교가 내부 루프 안에서 이루어지므로 전체 비교 횟수는 다음과 같이 됨.
(n-1) + (n-2) + … + 1 = n(n-1) / 2 = O(n²)
- 레코드 교환 횟수는 외부 루프의 실행 횟수와 같으며 한 번 교환하기 위하여 3번의 이동이 필요하므로 전체 이동 횟수는 3(n-1)이 됨.
- 선택 정렬의 장점 : 자료 이동 횟수가 미리 결정됨.
- 하지만 자료가 정렬된 경우에는 불필요하게 자기 자신과의 교환을 하게 됨.
- 따라서 이 문제를 계선하려면 다음과 같은 if문을 추가하면 됨.
if (i != least)
SWAP(list[i], list[least], temp);
- 즉, 최솟값이 자기 자신이면 자료 이동을 하지 않음.
- 일반적으로 비교 연산 1개가 이동 연산 3개보다 시간이 적게 걸리므로 효과적임.
- 선택 정렬의 문제점 : 안정성을 만족하지 않음. -> 값이 같은 레코드가 있는 경우에 상대적인 위치가 변경될 수 있음.
[삽입 정렬]
- 삽입 정렬(insertion sort) : 손안의 카드를 정렬하는 방법과 유사함.
- 정렬되어 있는 리스트에 새로운 레코드를 올바른 위치에 삽입하는 과정을 반복함.
- 선택 정렬과 마찬가지로 입력 배열을 정렬된 리스트와 정렬되지 않은 리스트로 나누어서 사용하면 됨.
- 정렬되어 있지 않은 리스트의 첫 번째 숫자가 정렬된 리스트의 어느 위치에 삽입되어야 하는가를 판단한 후 해당 위치에 이 숫자를 삽입하게 되면, 정렬된 리스트의 크기는 하나커지게 되고, 정렬이 되지 않은 리스트의 크기는 하나 줄어들게 됨.
- 이러한 삽입 연산을 정렬되지 않은 리스트가 없어질 때까지 반복하게 되면 전체 리스트가 정렬됨.
- 삽입 정렬 프로그램
// 삽입 정렬 프로그램
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 10000
int list[MAX_SIZE];
int 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;
}
}
void main() {
int i;
n = MAX_SIZE;
for (i = 0; i < n; i++) { // 난수 생성 및 출력
list[i] = rand() % n; // 난수 발생 범위 0~n
}
insertion_sort(list, n); // 삽입 정렬 호출
for (i = 0; i < n; i++) {
printf("%d\n", list[i]);
}
}
- 삽입 정렬의 복잡도는 입력 자료의 구성에 따라서 달라짐.
- 먼저 입력 자료가 이미 정렬되어 있는 경우는 가장 빠름.
- 이 경우 삽입 정렬의 외부 루프는 n-1번 실행되고 각 단계에서 이동 없이 1번의 비교만 이루어지므로 총 비교 횟수는 n-1번이 되어 알고리즘의 시간 복잡도는 O(n).
- 최악의 복잡도는 입력 자료가 역순일 경우로서 각 단계에서 앞에 높인 자료들은 전부 한 칸씩 뒤로 이동하여야 함.
- 최악의 경우 외부 로프 안의 각 반복마다 i번의 비교가 수행되므로 총 비교 횟수는 다음과 같음.
- 총 이동 횟수는 외부 루프의 각 단계마다 i+2번의 이동이 이루어지므로 다음과 같음.
- 삽입 정렬은 비교적 많은 레코드들의 이동을 포함함.
- 결과적으로 삽입 정렬은 레코드 수가 많고 레코드 크기가 클 경우에 적합하지 않음을 알 수 있음.
- 반면에 삽입 정렬은 안정한 정렬 방법으로서 레코드의 수가 적을 경우 알고리즘 자체가 매우 간단하므로 다른 복잡한 정렬 방법보다 유리할 수 있음.
- 또한 삽입 정렬은 대부분의 레코드가 이미 정렬되어 있는 경우에 매우 효율적일 수 있음.
[버블 정렬]
- 버블 정렬(bubble sort) : 인접한 2개의 레코드를 비교하여 크기가 순서대로 되어 있지 않으면 서로 교환하는 비교-교환 과정을 리스트의 왼쪽 끝에서 시작하여 오른쪼 끝까지 진행함.
- 이러한 리스트의 비교-교환 과정(스캔)이 한 번 완료되면 가장 큰 레코드가 리스트의 오른쪽 끝으로 이동됨.
- 이러한 레코드의 이동 과정이 마치 물속에서 거품(bubble)이 보글보글 떠오르는 것과 유사하여 버블 정렬이라 부름.
- 이러한 비교-교환 과정은 전체 숫자가 정렬될 때까지 계속됨.
- 정렬이 안 된 오른쪽 리스트를 한 번 스캔하면 오른쪽 리스트의 오른쪽 끝에 가장 큰 레코드가 위치하게 되고, 오른쪽 리스트는 추가된 레코드를 포함하여 정렬된 상태가 됨.
- 이러한 스캔 과정을 정렬이 안 된 왼쪽 리스트에서 반복하여 적용하면 정렬이 완료됨.
- 버블 정렬 프로그램
// 버블 정렬 프로그램
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 10000
#define SWAP(x, y, t) ( (t) = (x), (x)=(y), (y)=(t) )
int list[MAX_SIZE];
int n;
// 버블 정렬
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);
}
}
}
}
void main() {
int i;
n = MAX_SIZE;
for (i = 0; i < n; i++) { // 난수 생성 및 출력
list[i] = rand() % n; // 난수 발생 범위 0~n
}
bubble_sort(list, n); // 버블 정렬 호출
for (i = 0; i < n; i++) {
printf("%d\n", list[i]);
}
}
- 버블 정렬의 비교 횟수는 최상, 평균, 최악의 어떠한 경우에도 항상 일정하고 다음과 같음.
- 최악의 이동 횟수는 입력 자료가 역순으로 정렬되어 있는 경우에 발생하고 그 횟수는 비교 연산의 횟수에 3을 곱한 값임.
- 왜냐하면 하나의 SWAP 함수가 3개의 이동을 포함하고 있기 때문.
- 최상의 경우는 입력 자료가 이미 정렬이 되어 있는 경우이고, 이런 경우에는 자료 이동이 한 번도 발생하지 않음.
- 평균적인 경우에는 자료 이동이 0번에서 i번까지 같은 확률로 일어날 것.
- 따라서 이를 기반으로 게산하여 보면 O(n²)의 알고리즘임을 알 수 있음.
- 버블 정렬의 가장 큰 문제점은 순서에 맞지 않은 요소를 인접한 요소와 교환한다는 점.
- 하나의 요소가 가장 왼쪽에서 가장 오른쪽으로 이동하기 위해서는 배열에서 모든 다른 요소들과 교환되어야 함.
- 특히 특정 요소가 최종 정렬 위치에 이미 있는 경우라도 교환되는 일이 일어남.
- 일반적으로 자료의 교환(swap) 작업이 자료의 이동(move) 작업보다 더 복잡하기 때문에 버블 정렬은 그 단순성에도 불구하고 거의 쓰이지 않고 있음.
[셸 정렬]
- 셸 정렬(shell sort) : Donald L. Shell이라는 사람이 제안한 방법으로 삽입 정렬이 어느 정도 정렬된 배열에 대해서는 대단히 빠른 것에 착안한 방법.
- 셸 정렬은 삽입 정렬의 O(n²)보다 빠름.
- 삽입 정렬의 최대 문제점은 요소들이 삽입될 때, 이웃한 위치로만 이동한다는 것.
- 만약 삽입되어야 할 위치가 현재 위치에서 상당히 멀리 떨어진 곳이라면 많은 이동을 해야만 제자리로 갈 수 있음.
- 셸 정렬에서는 요소들이 멀리 떨어진 위치로도 이동할 수 있음.
- 삽입 정렬과는 다르게 셸 정렬은 전체의 리스트를 한 번에 정렬하지 않음.
- 대신에 먼저 정렬해야 할 리스트를 일정한 기준에 따라 분류하여 연속적이지 않은 여러 개의 부분 리스트를 만들고, 각 부분 리스트를 삽입 정렬을 이용하여 정렬함.
- 모든 부분 리스트가 정렬되면 셸 정렬은 다시 전체 리스트를 더 적은 개수의 부분 리스트로 만든 후에 알고리즘을 되풀이함.
- 위의 과정은 부분 리스트의 개수가 1이 될 때까지 되풀이됨.
- 부분 리스트를 구성할 때는 주어진 리스트의 각 k번째 요소를 추출하여 만듦.
- 이 k를 간격(gap)이라고 함.
- 셸 정렬에서는 각 스텝마다 간격 k를 줄여가므로 수행 과정이 반복될 때마다 하나의 부분 리스트에 속하는 레코드들의 개수는 증가됨.
- 마지막 스텝에서는 간격의 값이 1이 됨.
- 셸 정렬의 전체 과정
| 입력 배열 | 10 | 8 | 6 | 20 | 4 | 3 | 22 | 1 | 0 | 15 | 16 |
| 간격 5일 때의 부분 리스트 | 10 | 3 | 16 | ||||||||
| 8 | 22 | ||||||||||
| 6 | 1 | ||||||||||
| 20 | 0 | ||||||||||
| 4 | 15 | ||||||||||
| 부분 리스트 정렬 후 | 3 | 10 | 16 | ||||||||
| 8 | 22 | ||||||||||
| 1 | 6 | ||||||||||
| 0 | 20 | ||||||||||
| 4 | 15 | ||||||||||
| 간격 5 정렬 후의 전체 배열 | 3 | 8 | 1 | 0 | 4 | 10 | 22 | 6 | 20 | 15 | 16 |
| 간격 3일 때의 부분 리스트 | 3 | 0 | 22 | ||||||||
| 8 | 4 | 6 | |||||||||
| 1 | 10 | 20 | |||||||||
| 부분 리스트 정렬 후 | 0 | 3 | 15 | 22 | |||||||
| 4 | 6 | 8 | 16 | ||||||||
| 1 | 10 | 20 | |||||||||
| 간격 3 정렬 후의 전체 배열 | 0 | 4 | 1 | 3 | 6 | 10 | 15 | 8 | 20 | 22 | 16 |
| 간격 1 정렬 후의 전체 배열 | 0 | 1 | 3 | 4 | 6 | 8 | 10 | 15 | 16 | 20 | 22 |
- 셸 정렬 프로그램
// 셸 정렬 프로그램
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 10000
int list[MAX_SIZE];
int n;
// gap만큼 떨어진 요소들을 삽입 정렬
// 정렬의 범위는 first에서 last
void 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);
}
}
}
void main() {
int i;
n = MAX_SIZE;
for (i = 0; i < n; i++) { // 난수 생성 및 출력
list[i] = rand() % n; // 난수 발생 범위 0~n
}
shell_sort(list, n); // 셸 정렬 호출
for (i = 0; i < n; i++) {
printf("%d\n", list[i]);
}
}
- 삽입 정렬에 비하여 셸 정렬은 2가지의 장점이 있음.
1. 연속적이지 않은 부분 리스트에서 자료의 교환이 일어나면 더 큰 거리를 이동함.
반면 삽입 정렬에서는 한 번에 한 칸씩만 이동됨.
따라서 교환되는 요소들이 삽입 정렬보다는 최종 위치에 더 가까이 있을 가능성이 높아짐.
2. 부분 리스트는 어느 정도 정렬이 된 상태이기 때문에 부분 리스트의 개수가 1이 되게되면 셸 정렬은 기본적으로 삽입 정렬을 수행하는 것이지만 더욱 빠르게 수행됨.
이것은 삽입 정렬이 거의 정렬된 파일에 대해서는 빠르게 수행되기 때문.
- 실험적인 연구를 통하여 셀 정렬의 시간 복잡도는 대략 최악의 경우에는 O(n²)이지만 평균적인 경우에는 O(n^1.5)로 나타남.
// 비효율적이지만 간단한 정렬 방법들은 입력 데이터가 많지 않을 때는 충분한 방법임.
// 그러나 입력 데이터가 많으면서 자주 정렬해야 할 필요가 있으면 이들 방법은 충분하지 못함.
// 밑의 정렬 방법부터는 앞의 정렬 방법보다 훨씬 빠른 방법임.
[합병 정렬]
- 합병 정렬(merge sort) : 하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법.
- 합병 정렬은 분할 정복(divide and conquer) 방법에 바탕을 두고 있음.
- 분할 정복 방법은 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략임.
- 분리된 문제가 아직도 해결하기 어렵다면, 즉 충분히 작지 않다면 분할 정복 방법을 연속하여 다시 적용함.
- 분할 정복 방법은 대개 순환 호출을 이용하여 구현함.
- 합병 정렬은 다음의 단계들로 이루어짐.
1.. 분할(Divide) : 입력 배열을 같은 크기의 2개의 부분 배열로 분할함.
2. 정복(Conquer) : 부분 배열을 정렬함. 부분 배열의 크기가 충분히 작지 않으면 순환 호출을 이용하여 다시 분할 정복 방법을 적용함.
3. 결합(Combine) : 정렬된 부분 배열들을 하나의 배열에 합병함.
예) 다음과 같은 배열이 있다고 가정.
27 10 12 20 25 13 15 22
1. 분할(Divide) : 배열을 27 10 12 20과 25 13 15 22의 2개의 부분 배열로 나눔.
2. 정복(Conquer) : 부분 배열을 정렬하여 10 12 20 27과 13 15 22 25를 얻음.
3. 결합(Combine) : 부분 배열을 통합하여 10 12 131 15 20 22 25 27을 얻음.
- 분할된 2개의 부분 배열들을 정렬하는 방법 -> 각 부분 배열을 정렬할 때도 합병 정렬을 순환적으로 적용하면 됨. (합병 정렬 함수의 순환적인 호출을 이용함.)
- 합병 정렬에서 실제로 정렬이 이루어지는 시점은 2개의 리스트를 합병(merge)하는 단계.
- 합병 자체는 어렵지 않으나 추가적인 리스트를 필요로 함.
- 합병 알고리즘은 2개의 리스트의 요소들을 처음부터 하나씩 비교하여 두 개의 리스트의 요소 중에서 더 작은 요소를 새로운 리스트로 옮김.
- 둘 중에서 하나가 끝날 때까지 이 과정을 되풀이함.
- 만약 둘 중에서 하나의 리스트가 먼저 끝나게 되면 나머지 리스트이 요소들을 전부 새로운 리스트로 복사하면 됨.
- 합병 정렬 프로그램
// 합병 정렬 프로그램
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100
int sorted[MAX_SIZE]; // 추가 공간이 필요
int list[MAX_SIZE];
int n;
// 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); // 합병
}
}
void main() {
int i;
n = MAX_SIZE;
for (i = 0; i < n; i++) { // 난수 생성 및 출력
list[i] = rand() % n; // 난수 발생 범위 0~n
}
merge_sort(list, 0, n); // 합병 정렬 호출
for (i = 0; i < n; i++) {
printf("%d\n", list[i]);
}
}- 합병 정렬은 순환 호출 구조로 되어 있음.
- 따라서 레코드의 개수 n이 2의 거듭제곱이라고 가정하고 순환 호출의 깊이가 얼마나 되는지를 분석.
- 만약 n = 2³인 경우에는 부분 배열의 크기가 2^3->2^2->2^1->2^0순으로 줄어들어 순환 호출의 깊이가 3임을 알 수 있음.
- 따라서 일반적으로 n=2^k이라고 하면 부분 배열의 크기는 2^k->2^k-1->...->2^0이 되어 순환 호출의 깊이가 k가 될 것임을 쉽게 알 수 있음.
- 여기서 k=log₂n임을 쉽게 알 수 있음.
- 배열이 부분 배열로 나누어지는 단계에서는 비교 연산이나 이동 연산은 수행되지 않음.
- 부분 배열이 합쳐지는 merge 함수에서 비교 연산과 이동 연산이 수행되는 것임.
- 순환 호출의 깊이만큼의 합병 단계가 필요함.
- 일반적인 경우를 유추해보면 하나의 합병 단계에서는 최대 n번의 비교 연산이 필요함을 알 수 있음.
- 그러한 합병 단계가 k=log₂n번만큼 있으므로 총 비교 연산은 최대 nlog₂n번이 필요함.
- 하나의 합병 단계에서 보면 임시 배열에 복사했다가 다시 가져와야 되므로 이동 연산은 총 부분 배열에 들어 있는 요소의 개수가 n인 경우, 레코드의 이동이 2n번 발생함.
- 총 log₂n개의 합병 단계가 필요하므로 총 2nlog₂n개의 이동 연산이 필요함.
- 결론적으로 합병 정렬은 비교 연산과 이동 연산의 경우 O(nlog₂n)의 복잡도를 가지는 알고리즘.
- 합병 정렬의 장점은 안정적인 정렬 방법으로 데이터의 분포에 영향을 덜 받는다는 것임.
-> 입력 데이터가 무엇이든 간에 정렬되는 시간은 동일함.
-> 최악, 평균, 최선의 경우가 다같이 O(nlog₂n)인 정렬 방법.
- 합병 정렬의 단점은 임시 배열이 필요하다는 것과 만약 레코드들의 크기가 큰 경우에는 이동 횟수가 많으므로 매우 큰 시간적 낭비를 초래한다는 것.
- 그러나 만약 레코드를 연결 리스트로 구성하여 합병 정렬할 경우, 링크 인덱스만 변경되므로 데이터의 이동은 무시할 수 있을 정도로 작아짐.
- 따라서 크기가 큰 레코드를 정렬할 경우에 연결 리스트를 사용한다면, 합병 정렬은 퀵 정렬을 포함한 다른 어떤 정렬 방법보다 효율적일 수 있음.
[퀵 정렬]
- 퀵 정렬(quick sort) : 평균적으로 매우 빠른 수행 속도를 자랑하는 정렬 방법.
- 퀵 정렬도 분할 정복(divide and conquer) 방법에 근거함.
- 퀵 정렬은 합병 정렬과 비슷하게 전체 리스트를 2개의 부분 리스트로 분할하고, 각각의 부분 리스트를 다시 퀵 정렬하는 전형적인 분할 정복 방법을 사용함.
- 그러나 합병 정렬과는 달리 퀵 정렬은 리스트를 다음과 같은 방법에 의해 비균등하게 분할함.
1. 먼저 리스트 안에 있는 한 요소를 피벗(pivot)으로 선택함. (여기서는 리스트의 첫 번째 요소를 피벗으로 하기로 함.)
2. 피벗보다 작은 요소들은 모두 피벗의 왼쪽으로 옮겨지고 피벗보다 큰 요소들은 모두 피벗의 오른쪽으로 옮겨짐.
3. 결과적으로 피벗을 중심으로 왼쪽은 피벗보다 작은 요소들로 구성되고, 오른쪽은 피벗보다 큰 요소들로 구성됨.
4. 이 상태에서 피벗을 제외한 왼쪽 리스트와 오른쪽 리스트를 다시 정렬하게 되면 전체 리스트가 정렬됨.
- 합병 정렬과 마찬가지로 퀵 정렬 함수가 다시 부분 리스트에 대하여 순환 호출됨.
- 부분 리스트에서도 다시 피벗을 정하고 피벗을 기준으로 2개의 부분 리스트로 나누는 과정이 되풀이됨.
- 이러한 반복 과정은 부분 리스트들이 더 이상 분할이 불가능할 때까지 계속됨.
- 퀵 정렬 프로그램
// 퀵 정렬 프로그램
#include <stdio.h>
#define MAX_SIZE 100
#define SWAP(x, y, t) ( (t) = (x), (x)=(y), (y)=(t) )
int n = 9;
int list[MAX_SIZE] = { 5, 3, 8, 4, 9, 1, 6, 2, 7 };
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);
}
}
int main() {
int i;
quick_sort(list, 0, n - 1); // 퀵 정렬 호출
for (i = 0; i < n; i++) {
printf("%d\n", list[i]);
}
}
- 퀵 정렬은 비교 연산을 총 nlog₂n번 실행하게 되어 O(nlog₂n)의 복잡도를 가지는 알고리즘이 됨.
- 퀵 정렬은 최악의 경우 O(n²)의 시간 복잡도를 가짐.
- 퀵 정렬의 평균적인 경우의 시간 복잡도는 O(log₂n)
- 특히 O(log₂n)의 복잡도를 가지는 다른 정렬 알고리즘과 비교하였을 때도 가장 빠른 것으로 나타남.
- 이는 퀵 정렬이 불필요한 데이터의 이동을 줄이고 먼 거리의 데이터를 교환할 뿐만 아니라, 한 번 결정된 피벗들이 추후 연산에서 제외되는 특성 등에 기인함을 보임을 알 수 있음.
- 퀵 정렬은 속도가 빠르고 추가 메모리 공간을 필요로 하지 않는 등의 장점이 있음.
- 하지만 정렬된 리스트에 대해서는 오히려 수행시간이 더 많이 걸리는 등의 단점도 있음.
- 이러한 불균형 분할을 방지하기 위해 피벗을 선택할 때 단순히 리스트의 왼쪽 데이터를 사용하는 대신에 더욱 리스트를 균등하게 분할할 수 있는 데이터를 선택하곤 함.
- 많이 사용되는 방법은 리스트 내의 몇 개의 데이터 중에서 크기순으로 중간 값(median)을 피벗으로 선택하는 것.
- 일반적으로 리스트의 왼쪽, 오른쪽, 중간의 3개의 데이터 중에서 크기 순으로 중간 값을 선택하는 방법(median of three)이 많이 사용됨.
cf) 퀵 정렬 라이브러리 함수의 사용
- 대개의 C언어 실행 시간 라이브러리에 퀵 정렬 함수가 제공됨.
- 대개 qsort란 이름으로 제공되며 다음과 같은 함수 원형을 가짐.
- qsort 함수는 일반적인 구조체 배열을 정렬하기 위하여 제작됨.
* 함수의 원형
void qsort (
void *base,
size_t num,
size_t width,
int (*compare)(const void *, const void *)
);
* 함수의 파라미터 설명
base : 배열의 시작 주소
num : 배열 요소의 개수
width : 배열 요소 하나의 크기 (바이트 단위)
compare : 비교 함수. 포인터를 통하여 두 개 요소를 비교하여 비교 결과를 정수로 반환함. 사용자가 제공하여야 함.
* 함수의 설명
- 이 함수는 각 요소가 width바이트인 num개의 요소를 가지는 배열에 대하여 퀵 정렬을 수행함.
- 입력 배열은 정렬된 값으로 덮어 씌어짐.
- compare는 배열 요소 2개를 서로 비교하는 사용자 제공 함수로 qsort 함수가 요소들을 비교할 때마다 다음과 같이 호출하여 사용함.
compare( (void *) elem1, (void *) elem 2 );
반환 값 설명 < 0 elem1이 elem2보다 작으면 0 elem1이 elem2와 같으면 > 0 elem1이 elem2보다 크면
* 함수의 사용 예
// 퀵 정렬 프로그램 (qsort 이용) #include <stdio.h> #include <string.h> #include <stdlib.h> int compare(const void *arg1, const void *arg2) { if (*(double *)arg1 > *(double *)arg2) return 1; else if (*(double *)arg1 == *(double *)arg2) return 0; else return -1; } int main() { int i; double list[5] = { 2.1, 0.9, 1.6, 3.8, 1.2 }; qsort((void *)list, (size_t)5, sizeof(double), compare); for (i = 0; i < 5; i++) { printf("%f ", list[i]); } }
[히프 정렬]
- 히프는 우선순위 큐를 완전 이진 트리로 구현하는 방법으로 히프는 최댓값이나 최솟값을 쉽게 추출할 수 있는 자료 구조임.
- 히프에는 최소 히프와 최대 히프가 있고 정렬에는 최소 히프를 사용하는 것이 프로그램이 더 쉬워짐.
- 최소 히프는 부모 노드의 값이 자식 노드의 값보다 작음.
- 따라서 최소 히프의 루트 노드는 가장 작은 값을 가지게 됨.
- 히프 정렬(heap sort) : 최소 히프의 이러한 특성을 이용하여 정렬한 배열을 먼저 최소 히프로 변환한 다음, 가장 작은 원소부터 차례대로 추출하여 정렬하는 방법.
- 히프는 1차원 배열로 쉽게 구현될 수 있음에 유의.
- 먼저 최소 히프를 만들고 숫자들을 차례대로 삽입한 다음, 최솟값부터 삭제하면 됨.
- 히프 정렬 프로그램
// 히프 정렬 프로그램
#include <stdio.h>
#define MAX_SIZE 100
#define SWAP(x, y, t) ( (t) = (x), (x)=(y), (y)=(t) )
int n;
int list[MAX_SIZE];
int heap[MAX_SIZE + 1];
void adjust(int heap[], int root, int n)
{
int child, temp;
temp = heap[root]; // 루트 값 저장
child = 2 * root; // 왼쪽 자식 노드
while (child <= n) { // 마지막 노드까지 반복
if (child < n && heap[child] < heap[child + 1]) {//더 작은 자식노드
child++;
}
if (temp > heap[child]) { // 부모 노드와 자식 노드 비교
break;
}
else { // 자식 노드 값을 부모 노드로 복사
heap[child / 2] = heap[child];
}
child = child * 2; // 한 레벨 아래로 이동
}
heap[child / 2] = temp; // temp가 child보다 작은 위치
}
// 히프 정렬
void heap_sort(int list[], int n)
{
int i, temp;
for (i = 0; i < n; i++) {
heap[i + 1] = list[i];
}
for (i = n / 2; i > 0; i--) { // 주어진 리스트를 최대 히프로 변환
adjust(heap, i, n);
}
for (i = n - 1; i>0; i--) { // 루트 노드와 마지막 노드 교환
SWAP(heap[1], heap[i + 1], temp);
adjust(heap, 1, i); // 축소된 리스트를 루트 노드부터 재조정
}
for (i = 0; i < n; i++) {
list[i] = heap[i + 1];
}
}
void main() {
int i;
n = MAX_SIZE;
for (i = 0; i < n; i++) { // 난수 생성 및 출력
list[i] = rand() % n; // 난수 발생 범위 0~n
}
heap_sort(list, n); // 히프 정렬 호출
for (i = 0; i < n; i++) {
printf("%d\n", list[i]);
}
}
- 히프 정렬에 대한 자세한 내용은 '우선순위 큐' 글 참고. (http://starrykss.tistory.com/268)
// 지금까지의 정렬 방법은 레코드를 비교하여 정렬하는 방법이었음.
[기수 정렬]
- 기수 정렬(radix sort) : 레코드를 비교하지 않고도 정렬하는 방법.
- 기수 정렬은 입력 데이터에 대해서 어떤 비교 연산도 실행하지 않고 데이터를 정렬할 수 있는 색다른 정렬 기법임.
- 정렬에 기초한 방법들은 절대 O(nlog₂n)이라는 이론적인 하한선을 깰 수 없는 데 반하여 기수 정렬은 이 하한선을 깰 수 있는 유일한 기법임.
- 사실 기수 정렬은 O(dn)의 시간 복잡도를 가지는데 대부분 d < 10 이하임.
- 다만 문제는 기수 정렬이 추가적인 메모리를 필요로 한다는 것인데, 이를 감안하더라도 기수 정렬이 다른 정렬 기법보다 빠르기 때문에 상당히 인기 있는 정렬 기법 중의 하나임.
- 기수 정렬의 단점은 정렬할 수 있는 레코드의 타입이 한정된다는 점임.
-> 기수 정렬을 사용하려면 레코드의 키들이 동일한 길이를 가지는 숫자나 문자열로 구성되어 있어야 함.
- 기수(radix) : 숫자의 자릿수
예) 숫자 42는 4와 2의 두 개의 자릿수를 가지고 이것이 기수가 됨.
- 기수 정렬은 이러한 자릿수의 값에 따라서 정렬하기 때문에 기수 정렬이라는 이름을 얻음.
- 기수 정렬은 다단계 정렬임.
- 단계의 수는 데이터의 자릿수 개수와 일치함.
예) (8, 2, 7, 3, 5) 정렬
- 십진수에서는 각 자릿수가 0에서 9까지의 값만 있으므로 이것에 착안하여 10개의 버켓(bucket)을 만들어서 입력 데이터를 각 자릿수의 값에 따라 버켓에 넣음.
- 그리고 위에서부터 아래로 순차적으로 버켓 안에 들어 있는 숫자들을 읽음으로써 정렬된 숫자 리스트를 얻을 수 있음.
- 주의할 점은 여기서는 비교 연산을 전혀 사용하지 않았다는 점.
예) (28, 93, 39, 81, 62, 72, 38, 26) (여러 자리로 이루어진 수)
- 0에서 99번까지 번호가 매겨진 100개의 버켓을 사용하여 앞에서와 마찬가지로 정렬을 할 수 있음.
- 그러나 더 효과적인 방법이 있음.
- 즉 1의 자릿수와 10의 자릿수를 따로따로 사용하여 정렬하면 10개의 버켓만을 사용하여 2자리 정수도 정렬할 수 있음.
- 먼저 낮은 자릿수로 정렬한 다음 차츰 높은 자릿수로 정렬해야 함.
- LSD(least significant digit) : 가장 낮은 자릿수
- MSD(most significant digit) : 가장 높은 자릿수
- 기수 정렬 프로그램
// 기수 정렬 프로그램
#include <stdio.h>
#include <stdlib.h>
#define MAX_QUEUE_SIZE 100
#define MAX_SIZE 100
#define BUCKETS 10
#define DIGITS 4
int n;
int list[MAX_SIZE];
typedef int element;
typedef struct {
element queue[MAX_QUEUE_SIZE];
int 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 == q->rear); // front == rear이면 공백 상태
}
// 포화 상태 검출 함수
int is_full(QueueType *q) {
return ((q->rear + 1) % MAX_QUEUE_SIZE == q->front); // front == (rear + 1)이면 포화 상태
}
// 삽입 함수
void enqueue(QueueType *q, element item) {
if (is_full(q)) {
error("큐가 포화상태입니다.");
}
q->rear = (q->rear + 1) % MAX_QUEUE_SIZE;
q->queue[q->rear] = item;
}
// 삭제 함수
element dequeue(QueueType *q) {
if (is_empty(q)) {
error("큐가 공백상태입니다.");
}
q->front = (q->front + 1) % MAX_QUEUE_SIZE;
return q->queue[q->front];
}
// 피크 함수
element peak(QueueType *q) {
if (is_empty(q)) {
error("큐가 공백상태입니다.");
}
return q->queue[(q->front + 1) % MAX_QUEUE_SIZE];
}
// 기수 정렬
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; // 그 다음 자릿수로 간다.
}
}
void main() {
int i;
n = BUCKETS;
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)의 시간 복잡도를 가짐.
- 시간 복잡도가 d에 비례하기 때문에 기수 행렬의 수행 시간은 정수의 크기와 관련이 있음.
- 그러나 일반적으로 컴퓨터 안에서는 정수의 크기가 제한됨.
- 32비트 컴퓨터의 경우에는 대개 10개 정도의 자릿수만을 가지게 됨.
- 따라서 일반적으로 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) | O(n^1.5) | O(n^1.5) |
| 퀵 정렬 | O(nlog₂n) | O(nlog₂n) | O(n^2) |
| 히프 정렬 | O(nlog₂n) | O(nlog₂n) | O(nlog₂n) |
| 합병 정렬 | O(nlog₂n) | O(nlog₂n) | O(nlog₂n) |
| 기수 정렬 | O(dn) | O(dn) | O(dn) |
- 정렬 알고리즘별 실험 결과 (정수 : 60,000개)
| 알고리즘 | 실행 시간(단위: sec) |
| 삽입 정렬 | 7.438 |
| 선택 정렬 | 10.842 |
| 버블 정렬 | 22.894 |
| 셸 정렬 | 0.056 |
| 히프 정렬 | 0.034 |
| 합병 정렬 | 0.026 |
| 퀵 정렬 | 0.014 |
내용 출처 : C언어로 쉽게 풀어쓴 자료구조 (천인국 외 지음, 생능출판사)
'Computer Science > Data Structure' 카테고리의 다른 글
| [C++] 트리 순회(Tree Traversal) (0) | 2021.05.15 |
|---|---|
| [C] 탐색(Search) (0) | 2017.06.21 |
| [C] 해싱(Hashing) (0) | 2017.06.20 |
| [C] 그래프(Graph) (0) | 2017.06.19 |
| [C] 우선순위 큐(Priority Queue) (0) | 2017.06.17 |
| [C] 트리(Tree) (0) | 2017.06.01 |
| [C] 큐(Queue) (0) | 2017.05.23 |
| [C] 스택(Stack) (0) | 2017.05.11 |
