정렬 알고리즘 (Sorting Algorithm)

정렬 알고리즘 정리에 앞서 두 가지를 정리하였다.

안전 정렬 ( stable )	불안전 정렬 ( not stable )
같은 값(key)의 위치가 정렬 과정에서 바뀌지 않는 것	같은 값(key)의 위치가 정렬 과정에서 바뀌는 것

내부 정렬 ( Internal sorting )	외부 정렬 ( External sorting )
데이터의 크기가 주 기억장소 용량보다 적을 경우 기억장소를 활용하여 정렬	데이터의 크기가 주 기억장소 용량보다 클 경우 외부 기억장치를 사용하여 정렬

가장 효율적인 정렬 알고리즘이 무엇인가? 라는 질문에 대한 답은 상황에 따라 다르다이다.

데이터의 크기, 양, 정렬상태 등 다양한 상황에 따라 최적의 정렬 알고리즘을 선택하기 위해 각각의 정렬 알고리즘들을 정리하였다.

1. Bubble Sort

시간 복잡도			공간 복잡도
최악	최선	평균

- 안전 정렬    - 내부 정렬    - 비교와 교환

- 연산이 완료되었는지를 나타내는 flag를 통한 코드 수정으로 복잡도 줄일 수 있다.

- 이미 정렬이 되어 있는지 확인 가능하다.

- 가장 쉬운 정렬 알고리즘    - 시간복잡도가 높아 잘 사용하지 않는다

- 나란히 있는 2개의 데이터를 계속해서 바꾸어 나간다.

- 데이터가 적고 단순한 구현이 필요한 경우 사용한다.

// flag를 통해 개선된 버블 정렬

void bubble_sort(int list[], int n) {

int flag = 1;

for (int i = n - 1; flag > 0; i--) {

flag = 0;

for (int j = 0; j < i; j++) {

if (list[j] > list[j + 1]) {

swap(list[j], list[j + 1]);

flag = 1;

}

}

}

}

2. Selection Sort

시간 복잡도			공간 복잡도
최악	최선	평균

- 불안전 정렬    - 내부 정렬    - 비교와 교환

- 데이터 중 최솟값을 선택하여 제일 앞과 자리를 바꾸며 정렬한다.

- 데이터가 적을 때 사용한다.

- 데이터의 초기 정렬형태에 영향을 받지않고 일정한 시간 복잡도를 나타낸다.

- 거품 정렬에 비해 2~3배 빠르다.

void selection_sort(int list[], int n) {

int minValue;

for (int i = 0; i<n - 1; i++) {

minValue = i;

for (int j = i + 1; j<n; j++) if (list[j]<list[minValue]) minValue = j;

swap(list[i], list[minValue]);

}

}

3. Insertion Sort

시간 복잡도			공간 복잡도
최악	최선	평균

- 안전 정렬    - 내부 정렬    - 비교와 교환

- 데이터에 대해 더 작거나 큰 값이 나올때까지 진행하며 값을 찾아가며 바꾼다.

- 버블, 선택 정렬보다 빠르고 안전성이 높아 다른 분할정복으로 구현되는 알고리즘의 base가 된다.

- 이미 정렬된 상태면 최선의 시간 복잡도가 나온다. 반면 역순으로 정렬되어 있는 경우 최악의 시간 복잡도가 나온다.

- 선택 정렬보다 2배정도 빠르다.    - 많은 이동때문에 적은 양의 데이터에 유리하다.

- 데이터의 초기 정렬형태에 영향을 받는다.

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;

}

}

4. Shell Sort

시간 복잡도			공간 복잡도
최악	최선	평균

- 불안전 정렬    - 내부 정렬    - 비교와 교환

- 속도가 빠르다.

- 정렬되지 않은 데이터의 경우에 비효율적인 삽입정렬을 개선한 방법

- 일정한 간격(gap)으로 그룹을 만들어 각각 삽입정렬을 한 후 전체를 간격 1로 보고 삽입정렬로 종합한다.

- 간격에 따라 시간 복잡도가 결정되며 아직 정확한 시간 복잡도는 확인되지 않았다. 약 n의 1.25승 정도이다.

- 일정한 간격의 수열이 서로 소가 되게 정의해야 성능이 좋아진다. (ex 701, 301, 132, 57, 23, 10, 4, 1)

- 간격에 따른 그룹 별 정렬 방식이 H/W로 정렬 알고리즘을 구현하는데 적합하여 임베디드 시스템에 주로 사용된다.

void insertion_sort(int list[], int first, int last, int gap) {

int i, j, key;

for (i = first + gap; i <= last; 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 /= 2) {

if ((gap % 2) == 0) gap++;

for (i = 0; i<gap; i++)

insertion_sort(list, i, n - 1, gap);

}

}

5. Merge Sort

시간 복잡도			공간 복잡도
최악	최선	평균

- 안전 정렬    - 외부 정렬

- 외부 정렬로 몇 번 패스(read/write)하냐 를 가지고 시간 복잡도를 측정한다. 

- 가장 많이 쓰이는 알고리즘 중 하나이다.

- 데이터를 2개의 균등 크기로 분할하고, 각각 재귀적으로 합병 정렬을 이용하여 정렬한 후 합병한다.

- 데이터 크기만큼 외부 메모리가 필요하다.

- 퀵 정렬과 달리 안정적인 복잡도를 발휘한다.

- 데이터의 초기 상태에 별로 영향을 받지 않는다.

void mergesort(int list[], int size, int tmp[]) {

int i, j, t;

if (size <= 1) return;

mergesort(list, size / 2, tmp);

mergesort(list + size / 2, size - size / 2, tmp);

i = 0;

j = size / 2;

t = 0;

while (i < size / 2 && j < size) {

if (list[i] <= list[j])

tmp[t++] = list[i++];

else

tmp[t++] = list[j++];

}

while (i < size / 2) tmp[t++] = list[i++];

while (j < size) tmp[t++] = list[j++];

memcpy(list, tmp, size * sizeof(int));

}

6. Tim Sort

시간 복잡도			공간 복잡도
최악	최선	평균

- 안전 정렬    - 외부 정렬    - 2분할 삽입 정렬 + 병합 정렬

- 병합 정렬일 때 요소수가 적은 경우 오버헤드에 의해 느려진다. 이를 개선한 알고리즘

- 미리 어느 정도의 크기의 정렬이 끝난 열(run)로 분할하고 병합한다.

- run은 32보다 작게 하여 2분할 삽입 정렬을 한다.

- 가장 많이 쓰이는 알고리즘 중 하나이다.

- 데이터를 2개의 균등 크기로 분할하고, 각각 재귀적으로 합병 정렬을 이용하여 정렬한 후 합병한다.

- 데이터 크기만큼 외부 메모리가 필요하다.

- 퀵 정렬과 달리 안정적인 복잡도를 발휘한다.

- 데이터의 초기 상태에 별로 영향을 받지 않는다.

7. Quick Sort

시간 복잡도			공간 복잡도
최악	최선	평균

- 불안전 정렬    - 내부 정렬

- 실제 데이터에서 빠르다고 알려져서 가장 많이 쓰는 알고리즘

- 최악의 경우에 시간 복잡도가 큰 약점이 있다.

- 임의의 값(pivot)을 기준으로 한쪽은 pivot보다 작은 것, 다른 쪽은 큰것으로 나누어(partition) 양쪽을 다시 재귀로 반복한다.

- pivot을 선택이 매우 중요하다.

- 원소 개수가 한자리로 떨어졌을 때는 재귀가 아니라 삽입 정렬로 효율을 높일 수 있다.

- 정렬된 데이터에 대해서는 시간이 더 걸린다.

void quicksort(DATA list[], int left, int right)

{

int pivot, i, j;

if (left < right) { 

i = left; j = right + 1;

pivot = list[left].key;

do { 

do i++;

while (list[i].key < pivot && i <= right);

do j--;

while (list[j].key > pivot); 

if (i < j)

swap(list[i], list[j]);

} while (i < j);

swap(list[left], list[j]);

quicksort(list, left, j - 1);

quicksort(list, j + 1, right);

}

}

8. Intro Sort

시간 복잡도			공간 복잡도
최악	최선	평균

- 불안전 정렬    - 내부 정렬

- 퀵 정렬의 개량 버전이다.

- 퀵 정렬에서 pivot의 선택에 의해 시간 복잡도가 최악으로 되는 경우를 대처하기 위해 재귀 탐색이 요소수의 대수를 넘으면

   힙 정렬로 바꾼다. 또한 퀵 정렬에서 32미만의 데이터 수의 경우 오버헤드를 적게하기 위해 삽입 정렬로 바꾼다. 

9. Heap Sort

시간 복잡도			공간 복잡도
최악	최선	평균

- 불안전 정렬    - 내부 정렬

- 퀵 정렬의 최악의 경우 때문에 힙 정렬을 많이 쓴다.

- 힙 조건(각 노드의 값이 자식 노드 값보다 커야 한다)을 만족하는 완전 이진 트리이다.

- 배열에 저장하여 힙을 만든 후 n개의 데이터를 삭제하고 힙을 재구성하는 과정을 반복한다. 삭제된 노드를 배열에 차례로 저장하면 정렬된 리스트가 된다.

- 재구성은 이진 트리를 힙으로 만들기 위한 재구성으로 트리의 깊이 만큼의 시간이 걸린다.

void adjust(DATA list[], int root, int n) {

int child, rootkey;

temp = list[root];

rootkey = list[root].key;

child = 2 * root;

while (child <= n) {

if ((child < n) &&

(list[child].key < list[child + 1].key))

child++;

if (rootkey > list[child].key) break;

else {

list[child / 2] = list[child];

child *= 2;

}

}

list[child / 2] = temp;

}

void heapsort(DATA list[], int n) {

int i, j;

for (i = n / 2; i > 0; i--)

adjust(list, i, n);

for (i = n - 1; i > 0; i--) {

swap(list[1], list[i + 1]);

adjust(list, 1, i);

}

}

10. Counting Sort

시간 복잡도			공간 복잡도
최악	최선	평균

- 데이터에서 최대값 만큼의 메모리가 필요하다. 따라서 메모리 낭비가 있을 수 있다.

- 정렬하는 데이터들의 값이 특정한 범위 안에 있을 때 사용한다.

- 데이터의 처음부터 끝까지 돌면서 각 숫자가 몇번 등장하는지 counting한다.

void counting_sort(int list[], int n, int max_value) {

int i,j,cnt=0,chk[max_value + 1] = { 0, };

for (i = 0; i < n; i++) chk[list[i]]++;

for (i = 0; i < max_value + 1; i++) for (j = 1; j <= chk[i]; j++) 

list[cnt++] = i;

}

11. Radix Sort

시간 복잡도			공간 복잡도
최악	최선	평균

- 데이터를 특정 진수로 자릿수 별로 정렬하는 알고리즘이다. 

- 비교 정렬 알고리즘에서 가장 빠르다.

- radix(기수), 즉 특정 진수로 일의 자리, 십의 자리, 백의 자리, 이렇게 차례로 정렬한다. 

- 기수의 크기만큼의 메모리가 필요하다.

- 부동 소숫점, 음수값 처럼 특수한 비교 연산에는 불가능하다.

- 숫자, 알파벳 관련 데이터 등 대용량 데이터 정렬에 적절하다.

void radixsort(int list[], int size) {

int i, max = list[0], rad = 1, base = 10;

int tmp[size], bucket[base];

for (i = 1; i < size; i++) {

if (list[i] > max) max = list[i];

}

while (max / rad > 0) {

memset(bucket, 0, base * sizeof(int));

for (i = 0; i < size; i++) {

bucket[(list[i] / rad) % base]++;

}

for (i = 1; i < base; i++) {

bucket[i] += bucket[i - 1];

}

for (i = size - 1; i >= 0; i--) {

tmp[--bucket[(list[i] / rad) % base]] = list[i];

}

memcpy(list, tmp, size * sizeof(int));

rad *= base;

}

}

12. Bucket Sort

시간 복잡도			공간 복잡도
최악	최선	평균

- n개의 데이터에 대해 범위를 n개로 나누고 n개의 버킷을 만든다. 그 후 각 데이터를 버킷에 넣고 버킷 별로 정렬하여 합친다.

- 데이터가 확률적으로 균등하게 분포한다고 가정할 때 성능이 나타난다.

- 연결 리스트로 버킷을 구성할 수 있고, 버킷들을 정렬할 때는 퀵 정렬 등을 사용한다.

정리

- 데이터의 값을 정확히 모른다면 Heap을 사용하면 가장 무난한 성능을 기대할 수 있다.

- 만약 데이터가 정렬되어 있거나 거의 정렬되어 있으면 Insertion 이나 Tim을 사용한다.

- quick 보다는 intro가 더 성능이 좋으므로 무난하게 사용한다.

정렬 알고리즘 별 비교 및 요약 : 

작성자 : 히더