[C] 퀵정렬 예제 정리

[C] 퀵정렬 예제 정리

퀵 정렬은 아주 빠른 속도를 나타낼뿐만 아니라 원리도 간단해서 많은 응용 분야에서 사용되고 있다.

퀵 정렬은 연속적인 분할에 의해서 정렬한다.

축(Pivot)값을 중심으로 왼쪽은 이 축값보다 작은 값으로 오른쪽은 모두 이 축값보다 큰 값을 배열시키는 것이다.

이렇게 하여 축값의 왼쪽과 오른쪽 부분을 각각 또다시 분할하고 하는 과정을 분할의 크기가 1이 될 때까지 반복하면 전체적으로는 정렬이 완료된다.

알고리즘

1. 만약 n>1 이면

1.1 N 크기의 a 배열을 분할 하여 축값의 위치를 mid로 넘긴다.

1.2 퀵 정렬 알고리즘(a, mid)

1.3 퀵 정렬 알고리즘 (a+mid-1, N-mid-1)

퀵 정렬은 안정성이 없다.

void quick_sort(int a[], int n){          int v, t;     int i, j;     if (n > 1){         v = a[n - 1];    // v=축값         i = -1;         j = n - 1;         while (1){    // 분할             while (a[++i] < v);    // 왼쪽에서부터 축값보다 큰 값이 있는지?             while (a[--j] > v);    // 오른쪽에서부터 축값보다 작은 값이 있는지?             if (i >= j) break;    // i와 j의 위치가 뒤바뀌었으면 분할 끝             t = a[i];    // 아니면 두 값을 바꿈             a[i] = a[j];             a[j] = t;         }         t = a[i];    // 축 값과 축값의 위치에 있는 값을 바꿈         a[i] = a[n - 1];         a[n - 1] = t;         quick_sort(a, i);    // 왼쪽 구간 퀵정렬         quick_sort(a + i + 1, n - i - 1);    // 오른쪽 구간 퀵정렬     } }

퀵 정렬은 난수 배열이나 반쯤 정렬된 배열에 대해서는 빠른 속도를 보이지만 이미 정렬된 배열이나 역순 배열에 대해서는 성능이 엄청나게 떨어진다.

퀵 정렬의 이상적인 경우는 분할이 정확하게 구간을 양분하는 것이다. 이 경우 재귀의 깊이는 logN이 되며 가장 빠른 속도를 나타낸다.

이렇게 퀵 정렬은 분할할 축값이 어느 정도 그 구간의 중앙을 나누느냐에 성능이 좌우된다.

재귀 호출로 인해서 내부 스택이 사용된다. 따라서 퀵 정렬이 속도가 빠른 반면에 메모리의 희생이 있다. 

N이 커지면 커질수록 스택의 크기가 커지며 스택 오버플로우가 발생할 수 있다.

* 난수 분할을 사용한 퀵 정렬 개선

정렬된 배열과 역순 배열일 때 퀵 정렬의 속도가 현저히 느려지는 것은 축값으로서 가장 오른쪽의 값을 택하기 때문에 결과적으로 가장 큰 값이나 가장 작은 값이 축값이 되기 때문이다. 이 때문에 재귀의 깊이가 깊어지고 스택이 넘치며 속도가 느려진다.

축 값을 잘 선택하는 대안으로 축값을 난수로 선택하는 것이다. 확률로 퀵 정렬의 속도 향상을 기대해본다.

0부터 n-1 범위의 난수를 발생시켜 그 난수의 위치와  배열의 제일 오른쪽 요소의 위치를 바꾼 후에 퀵 정렬 알고리즘을 수행한다.

이러한 개선은 평균적으로 고른 속도 향상은 있을 수도 있지만 속도의 결과가 확률에 맡겨지게 된다.

* 삽입 정렬을 사용한 퀵 정렬 개선

삽입 정렬은 구현이 간단하면서도 작은 크기의 배열에서는 매우 효율이 좋다. 또한 삽입 정렬은 추가적인 메모리를 필요로 하지 않는다.

작은 구간에 대해서는 삽입 정렬을 사용하면서 퀵 정렬의 재귀의 깊이를 줄여주고 속도의 향상을 기대할 수 있다.

구간의 크기가 너무 큰 경우 삽입 정렬은 큰 크기의 배열에서 성능이 좋지 못하여 전체적인 성능이 떨어질 것이다.

실험 결과 레코드의 크기가 작은 경우는 100에서 200 정도가 가장 효율이 좋으며 레코드의 크기가 큰 경우는 50에서 10 사이가 효율이 좋다고 한다.

구현은 퀵 정렬 종료 조건을 크기가 200보다 작을때로 변경하고, 작을때는 삽입정렬을 수행하도록 변경하면 된다.

* 세 값의 중위 값을 구한 퀵 정렬의 개선

이 것은 배열의 가장 왼쪽 값, 가장 오른쪽 값, 중간의 값 3개의 값을 사용한다.

세 값을 정렬하여 가장 작은 값을 가장 왼쪽에 중간값을 중간에 가장 큰 값을 가장 오른쪽으로 옮긴다.

그리고 중간값을 가장 오른쪽의 앞의 값과 위치를 바꾼다.

이렇게 되면, 배열의 첫번째 값은 마지막의 앞의 값보다 항상 작고, 마지막 값은 마지막 앞의 값보다 항상 크다.

이렇게 되면 분할 구간은 배열 앞에서 두번째 값과 뒤에서 세번째 값으로 좁혀진다.

위와같이 범위에서 2개를 줄이는 것만으로도 재귀의 깊이를 상당히 줄일 수 있으며 분할도 거의 중앙에서 이루어질 가능성이 많다. 특히 정렬된 배열이나 역순의 배열은 분할을 정 중아에서 할 수 있으므로 이 방법을 쓰면 가장 속도가 빨라진다.

* qsort() 함수

search.h 라이브러리에서는 퀵 정렬 함수를 제공한다. (qsort());

#include <stdio.h> #include <search.h> #include <string.h> void main(void){     // qsort 라이브러리를 사용     int array[] = { 3, 5, 6, 3, 1, 2, 7, 6, 7, 4, 8, 9, 3 };     qsort(array, 13, sizeof(int), strcmp);     for (i = 0; i < 13; i++){         printf("%d\t", array[i]);     }     return 0; }

출처: https://hyeonstorage.tistory.com/361?category=622873 [개발이 하고 싶어요]