거품 정렬
바로 옆 원소끼리의 비교· 대입만 죽어라고 하는 무식한 노가다 알고리즘. 비교도 많고 대입도 많은 상당히 비효율적인 알고리즘이지요. 그나마 대입 여부를 플래그로 저장하면, 루프를 다 돌기 전에 정렬 작업을 끝낼 수는 있습니다. 이 알고리즘의 동작 모습을 그래픽 (x, y)->(x, 배열의 x째 원소)로 시연해 보면 대각선 부위에서 점들이 거품처럼 부글부글 움직이는 모습을 볼 수 있습니다.
선택 정렬
가장 큰 값부터 차례대로 리스트의 끝으로 옮겨서 정렬하는 방법으로, 실제 상황에서 가장 코딩하기 쉽고 직관적인 알고리즘입니다. 수행 시간이 데이터 상태의 영향을 잘 받지 않고, 데이터의 대입 횟수가 적은 게 특징입니다.
삽입 정렬
삽입 정렬과 거품 정렬을 비교해 보면, O(n^2)이라고 다 같은 O(n^2) 알고리즘은 아니라는 걸 알 수 있습니다. 평균적인 성능이 O(n^2) 알고리즘들 중에서 뛰어난 축에 들기 때문에, 이 정렬은 다른 정렬 알고리즘의 일부로도 자주 인용됩니다. 이 방법은 데이터의 상태, 데이터 한 개의 크기에 따라 성능 편차가 심한 편입니다.
쉘 정렬
삽입 정렬을 응용한 것 뿐인데 삽입 정렬과는 비교할 수 없을 정도로, O(n log n) 알고리즘에 버금가는 성능을 자랑하는 알고리즘입니다. 부가적인 메모리도 전혀 필요없죠. 비용 대 성능이 가장 뛰어난 알고리즘임이 틀림없습니다. 시간 복잡도도 O(n^2)나 O(n log n)처럼 정확하게 계산하기 힘든 신비로운(?) 알고리즘이기도 합니다.
퀵 정렬
가장 유명하고, 정렬 알고리즘의 표준이다시피 한 방법입니다. 이 알고리즘을 보면 정말 사기-_-라는 생각이 듭니다. 실제로 코딩을 해 보면, 퀵 정렬이 코드가 가장 긴데, 실행 시간은 퀵 정렬이 다른 알고리즘들보다 기막힐 정도로 짧습니다. 중간값이라는 뭔가 적당한(모호한-_-) 값을 선택해야 하고, 최악의 경우 시간 복잡도가 O(n^2)에 메모리 복잡도가 O(n)이 될 가능성까지 있는 알고리즘이 어쩜 이럴 수 있는지... 퀵 정렬만치 자료 상태에 민감한 알고리즘이 또 있을까 하는 생각이 듭니다.
하지만, 중간값을 기준으로 데이터를 반으로 갈라 놓고, 양측에 대해서 재귀적으로 정렬을 또 수행한다는 발상은 깔끔하고 멋집니다. 이런 걸 분할 정복법이라고 하지요. 이게 '퀵 정렬'이 아니었으면 '이분 검색'을 따라 '이분 정렬'이라는 이름이 붙었을 것입니다.
퀵 정렬은 본디 재귀적으로 정의되지만, 사용자 정의 스택을 구현해서 비재귀적으로 만들 수도 있습니다. 또한, 원소 개수가 한 자리 수로 떨어졌을 때는 또 재귀호출을 하는 게 아니라 삽입 정렬을 해서 능률을 극대화하기도 합니다.
병합 정렬
O(n log n)인 정렬 알고리즘 중에 가장 간단하고 쉽게 떠올릴 수 있는 방법입니다. 퀵 정렬이 큰 리스트를 반씩 쪼갠다면, 이 방법은 이미 정렬이 된 리스트를 하나 둘씩 합쳐서 작업을 수행합니다. 이 알고리즘은 소요 시간이 데이터 상태에 별 영향을 받지 않고, 시간 복잡도가 O(n log n)인 알고리즘 중에 유일하게 안정성이 있다는 데 의미를 둘 수 있습니다. O(n^2) 알고리즘들은 모두 안정성이 있지만.. 쿨럭~
병합 정렬의 큰 결점은 데이터 전체 크기만한 메모리가 더 필요하다는 점입니다. 아주 현학적인 방법으로 한 배열 안에서 병합을 구현하는 방법도 있긴 하지만, 밀고 당기고 하는 과정으로 인해 속도가 크게 떨어지기 때문에, 메모리를 아끼려면 차라리 아래에 나오는 힙 정렬을 쓰는 게 더 낫습니다.
무조건 2의 배수씩 리스트를 합치는 게 병합 정렬의 기본 원리지만, 리스트에서 오름차순인 부분만 골라내서 지능적으로 병합을 하는 방법도 생각할 수 있습니다. 또한 퀵 정렬과 비슷한 원리로 재귀판을 만들 수도 있지요.
힙 정렬
이진 완전 나무를 배열에다 접목시킨 절묘한 알고리즘입니다. 이 알고리즘을 뜯어 보면 절로 감탄이 나옵니다. 처음에는 나무 아래에서 위(뿌리)로 각 원소들을 최대값 힙 조건에 맞게 정리한 뒤, 나무 뿌리에 있는 자료를 차례차례 나무 뒤로 옮기면서 힙을 정렬된 배열로 바꿉니다. 뿌리에는 힙 나무 맨 뒤에 있던 원소가 왔다가, 다시 힙 조건에 맞는 위치로 내려가지요.
시간 복잡도가 O(n log n)인 정렬 알고리즘 중에서는 부가적인 메모리가 전혀 필요없다는 게 힙 정렬의 큰 장점이지만, 하지만 수행 속도가 동급 O(n log n) 알고리즘들에 비해서는 약간(아주...) 낮은 편입니다.
- 버블정렬 (Bubble Sort)
순서
1. 우선 맨 처음에 모든 원소들의 최대값을 찾으려면 맨 처음 원소와 둘째 원소를 비교한다. 만약 앞의 원소가 뒤의 원소보다 크면 두 원소의 자리를 바꾼다.
2. 둘째 원소와 셋째 원소를 비교해 자리를 바꾼다.
3. 이 과정을 마지막 원소까지 반복하면 맨 마지막 자리에 제일 큰 원소가 자리잡게 된다.
4. 최대값을 가진 원소를 제외하고 나머지에 대해서 이 과정을 반복하면 그 다음으로 큰 원소를 찾아내 마지막에서 둘째 자리에 넣게 된다.
5. 과정을 끝까지 반복하면 모든 원소가 오름차순으로 정리된다.
void Bubble(int item[], int count)
{
register int i, j, temp;
for(i=0; i<count-1; i++) {
for(j=0; j<count-i-1; j++) {
// 오름차순이 되게 비교를 하여 데이터 교환
if(item[j] > item[j+1]) {
temp = item[j];
item[j] = item[j+1];
item[j+1] = temp;
}
}
}
}
- 선택정렬 (Select Sort)
void Select(int item[], int count)
{
register int i, j, temp;
for(i=0; i<count-1; i++) {
for(j=i+1; j<count; j++) {
// 비교한 후 교환
if(item[i] > item[j]) {
temp = item[j];
item[j] = item[i];
item[i] = temp;
}
}
}
}
위의 함수를 보면 버블정렬과 거의 외관상 비슷하다. 하지만 위와 같이 만들면 좀 비합리적이다. 좀 유심히 살펴보면 알겠지만 킷값보다 작은 것이 나타나서 자리바꿈이 일어난 뒤에도 계속 비교를 하여 또 작은 것이 나타나면 같은 일(자리바꿈)을 반복하게 된다. 그래서 안쪽 루프를 돌면서 자리바꿈을 하지 말고, 단지 일어날 가장 최대치의 자리만 기억했다가 루프를 빠져나오면서 그 일을 하면 한번만 하게 되어 좀더 속도를 빠르게 할 수 있다. 그 개선된 함수는 다음과 같다.
- 삽입정렬 (Insert Sort)
void Insert(int item[], int count)
{
register int i, j, temp;
for(i=0; i<count; i++) {
temp = item[i]; // 삽입할 키값을 기억
j = i-1; // j는 삽입시 뒤로 밀려나는 것의 위치
while(j >= 0 && item[j] > temp) {
item[j+1] = item[j];
j--;
} // 삽입할 위치 결정및 뒤로 이동시키는 작업을 함
item[j+1] = temp;
}
}
- 쉘정렬 (Shell sort)
void Shell(int item[], int count)
{
register int begin, inc=count;
do {
inc = inc/3+1; // 간격을 계산한다.
for(begin=0; begin<inc; begin++)
InsertSort(begin, inc, item, count);
// 계산된 간격으로 삽입정렬을 한다.
} while(inc>1);
}
// 쉘정렬에 사용된 삽입정렬
void InsertSort(int start, int inc, int item[], int count)
{
register int i, j, temp;
for(i=start; i<count; i+=inc) {
temp = item[i];
j = i-inc;
while(j >= 0 && item[j] > temp) {
item[j+inc] = item[j];
j-=inc;
}
item[j+inc] = temp;
}
}
- 퀵정렬 (Quick Sort)
순서
1. 어떤 특정 값을 기준으로 한 리스트를 두 개의 리스트로 분할한다. 그 중 한 리스트에는 그 기준값보다 작은 원소만 존재하고, 다른 리스트에는 그 기준값보다 큰 원소만 존재하도록 리스트를 분할한다.
2. 분할된 2개의 리스트를 또 다시 1과 같은 방식으로 분할한다.
3. 이 과정을 모든 리스트의 크기가 1이 될 때까지 반복하면 정렬이 완료된다.
void Quick(int item[], int count)
{
qs(item, 0, count-1);
}
void qs(int item[], int left, int right)
{
register int i=left, j=right+1, pivot, temp;
pivot = item[left]; // 비교할 중간의 값을 맨 왼쪽에서 따옴
// 재귀호출의 BASE CASE
if(left<right) {
do {
// 자리바꿈할 위치를 찾는다.
do i++; while(item[i] < pivot);
do j--; while(item[j] > pivot);
// 자리바꿈을 한다.
if(i<j) {
temp = item[i];
item[i] = item[j];
item[j] = temp;
}
} while(i<j);
item[left] = item[j];
item[j] = pivot;
// 나뉘어진 각각에 대해 다시 퀵정렬 실시
qs(item, left, j-1);
qs(item, j+1, right);
}
}
- 힙 정렬 (Heap Sort)
void heap_sort(int *list, int n)
{
int i, temp;
for(i=(n/2); i>=1; i--) // 초기 히프 만들기
adjust(list, i, n);
for(i=(n-1); i>=1; i--) { // 히프 정렬의 두 번째 단계
temp = list[i+1]; // 마지막 노드와 뿌리 노드의 교환
list[i+1] = list[1];
list[1] = temp;
adjust(list, 1, i); // i개의 키에 대하여 adjust 적용
}
}
void adjust(int *list, int i, int n)
// i : adjust 알고리즘을 시작하는 노드의 인덱스
// n : 전체 노드의 개수
{
int j, k, done;
done = 0; // 아직 끝나지 않았음을 표시
k = list[i]; // 뿌리 노드의 값, 즉 옮겨야 할 원소의 값
j = 2 * i; // i 노드의 좌 자 노드
while ((j <= n) && (!done)) { // 자식노드가 있고 not done일 때까지 반복
if ( j < n) // j + 1 <= n 과 마찬가지인데 우 자 노드의 존재를 검사
if (list[j] < list[j + 1])
j ++; // 자 노드들 중 큰 노드를 선택
if (k >= list[j])
done = 1; // 자 노드보다 크므로 수행을 중단
else{
list[j / 2] = list[j]; // 자 노드를 부노드로 끌어 올림,
// 자 노드에 k 값을 쓰지 않는 이유는 나중에
// 수행이 다 끝난 다음에 쓰기 때문임.
j *= 2;
}
}
list[j / 2] = k; // 수행이 끝나면 찾아낸 위치에 맨 처음 저장한 뿌리 노드의 값을 저장
}
참고 사이트
힙정렬 : http://www.tipssoft.com/bulletin/tb.php/FAQ/67
퀵정렬 : http://www.tipssoft.com/bulletin/tb.php/FAQ/66
쉘정렬 : http://www.tipssoft.com/bulletin/tb.php/FAQ/62
삽입정렬 : http://www.tipssoft.com/bulletin/tb.php/FAQ/61
선택정렬 : http://www.tipssoft.com/bulletin/tb.php/FAQ/60
버블정렬 : http://www.tipssoft.com/bulletin/tb.php/FAQ/58
http://i0nucleus.egloos.com/2265111