qsort (퀵 정렬) - 재귀, 비재귀, 삽입정렬, 난수발생

<재귀 : pivot을 배열의 중간값으로>

void qsort(int a[], int left, int right)
{
        int p, t;
        int i, j;
 
 
        if( left < right) {
                p = a[(left + right) / 2];
                i = left - 1;
                j = right + 1;
 
                while(1) {
                        while(a[++i] < p);
                        while(a[--j] > p);
 
                        if( i >= j)
                                break;
 
                        t = a[i];
                        a[i] = a[j];
                        a[j] = t;
                }
                qsort(a, left, i-1);
                qsort(a, j+1, right);
        }
 }

<재귀 : pivot을 배열의 첫 번째 값으로>

void qsort(int a[], int left, int right)
{
        int p, t;
        int i, j;
 
 
        if( left < right) {
                p = a[left];
                i = left;
                j = right + 1;
 
                while(1) {
                        while(a[++i] < p);
                        while(a[--j] > p);
 
                        if( i >= j)
                                break;
 
                        t = a[i];
                        a[i] = a[j];
                        a[j] = t;
                }
                /* pivot 값을 교환 */
                a[left] = a[j];
                a[j] = p;
 
                qsort(a, left, j-1);
                qsort(a, j+1, right);
        }
 }

 ** 재귀 함수의 문제점
    배열이 아주 클 경우 스택 오버플로우가 발생할 위험
    --> 자체 스택을 만들어 비재귀하는 방식으로 개선
    --> 구간이 작을 경우 더 이상 재귀 호출을 하지 말고 선택 정렬이나 삽입 정렬 이용


<비재귀 함수>

#include <stdio.h>
 
#define MAX_NUM 50

int stack[MAX_NUM];
int top = 0;
 
void init_stack()
{
        top = 0;
}
 
void push(int i)
{
 
        if( top >= MAX_NUM) {
                printf("stack full\n");
                return;
        }
        else
                stack[top++] = i;
}
 
int pop()
{
 
        if( top == 0)
                return 0;
        else
                return stack[--top];
 
}
 
int is_stack_empty()
{
 
        if( top == 0)
                return 1;
        else
                return 0;
 
}

void qsort(int a[], int n)
{
        int p, t;
        int i, j;
        int l, r;
 
        init_stack();  
 
        l = 0;
        r = n - 1;
 
        push(r);
        push(l);
 
        while(!is_stack_empty()) {
                l = pop();
                r = pop();
 
                if( r-l+1 > 1) {  // 종료조건 :: 남아 있는 분할의 원소 개수가 1개 이상일 경우
                        p = a[r];
                        i = l - 1;
                        j = r;
 
                        while(1) {
                                while(a[++i] < p);
                                while(a[--j] > p);
 
                                if( i >= j)
                                        break;
                       
                                t = a[i];
                                a[i] = a[j];
                                a[j] = t;
 
                        }
 
                        // pivot과 i값을 교환
                        t = a[i];
                        a[i] = a[r];
                        a[r] = t;
 
                        push(r);     // 오른쪽 분할의 오른쪽 끝
                        push(i+1);  // 오른쪽 분할의 왼쪽 끝
                        push(i-1);  // 왼쪽 분할의 오른쪽 끝
                        push(l);     // 왼쪽 분할의 왼쪽 끝
 
                } // if
        } // while
 }

** 비재귀 함수의 문제점
    재귀함수에 비해 실행시간이 약간 빠르다. 그러나, push(), pop()을 사용하므로 함수호출에 의한 오버헤드
    현상으로 속도가 확 달라지지는 않는다.
    정렬된 배열과, 역순 배열에서는 그 속도가 40배 가량 느리다. ( O(n^2) )
    ?? 가장 큰 값이나 가장 작은 값이 pivot으로 되기 때문에 속도 저하
   --> pivot 값을 난수로 지정하는 방법


< 난수 발생>

int get_random(int range)
{
 
        return rand() % range;
 
}
 
 
 
void qsort3(int a[], int n)
{
        int p, t;
        int i, j;
        int l, r;
 
 
        init_stack();  
 
        l = 0;
        r = n - 1;
 
        push(r);
        push(l);
 
        while(!is_stack_empty()) {
 
                l = pop();
                r = pop();
 
                if( r-l+1 > 1) {
                        t = get_random(r-l+1) + l; // 난수 발생
 
                        p = a[t];
                        a[t] = a[r];
                        a[r] = p;
 
                        i = l - 1;
                        j = r;
 
                        while(1) {
                                while(a[++i] < p);
                                while(a[--j] > p);
 
                                if( i >= j)
                                        break;
 
                                t = a[i];
                                a[i] = a[j];
                                a[j] = t;
 
                        }
 
                        t = a[i];
                        a[i] = a[r];
                        a[r] = t;
 
                        push(r);
                        push(i+1);
                        push(i-1);
                        push(l);
 
                } // if
        } // while
}

 이 경우는 최악의 경우가 발생하지 않는다.


<삽입정렬 추가>

void insert_sort(int a[], int n)
{
        int i, j, t;
 
 
        for( i = 1; i < n; i++) {
                t = a[i];
                j = i;
 
                while( a[j-1] > t && j > 0) {
                        a[j] = a[j-1];
                        j--;
                }
 
                a[j] = t;
        }
 
        return;
 
}
 
void qsort4(int a[], int n)
{
        int p, t;
        int i, j;
        int l, r;
 
        init_stack();
 
        l = 0;
        r = n - 1;
 
        push(r);
        push(l);
 
        while(!is_stack_empty()) {
 
                l = pop();
                r = pop();
 
                if( r-l+1 > 200) {
                        t = get_random(r-l+1) + l; // 난수 발생
 
                        p = a[t];
                        a[t] = a[r];
                        a[r] = p;
 
                        i = l - 1;
                        j = r;
 
                        while(1) {
                                while(a[++i] < p);
                                while(a[--j] > p);
 
                                if( i >= j)
                                        break;
 
                                t = a[i];
                                a[i] = a[j];
                                a[j] = t;
 
                        }

                        t = a[i];
                        a[i] = a[r];
                        a[r] = t;
 
                        push(r);
                        push(i+1);
                        push(i-1);
                        push(l);
 
                } // if
                else
                        insert_sort(a+l, r-l+1);
 
        } // while
 }

삽입 정렬은 어느 정도 정렬된 배열에서 아주 큰 효과를 내기 때문에 사용...
메모리의 소모도 줄어듬...


<세 값의 중위>

void qsort4(int a[], int n)
{
        int p, t;
        int i, j;
        int l, r;
 
 
        init_stack();
 
        l = 0;
        r = n - 1;
 
        push(r);
        push(l);
 
        while(!is_stack_empty()) {
 
                l = pop();
                r = pop();
 
                if( r-l+1 > 200) {
                        t = (r+1) >> 1; // 나누기 2의 의미
 
                        if( a[l] > a[t]) {
                                p = a[l];
                                a[l] = a[t];
                                a[t] = p;
                        }
 
                        if( a[l] > a[r]) {
                                p = a[l];
                                a[l] = a[r];
                                a[r] = p;
                        }
 
                        if( a[t] > a[r]) {
                                p = a[t];
                                a[t] = a[r];
                                a[r] = p;
                        }
 
                        p = a[t];
                        a[t] = a[r-1];
                        a[r-1] = p;
 
                        i = l - 1;
                        j = r;
 
                        while(1) {
                                while(a[++i] < p);
                                while(a[--j] > p);
 
                                if( i >= j)
                                        break;
 
                                t = a[i];
                                a[i] = a[j];
                                a[j] = t;
 
                        }

                        t = a[i];
                        a[i] = a[r];
                        a[r] = t;
 
                        push(r);
                        push(i+1);
                        push(i-1);
                        push(l);
 
                } // if
                else
                        insert_sort(a+l, r-l+1);
 
        } // while
 
}

* 복잡도
 - Best Case
   T(n) = n + 2T(n/2)
          = n + 2(n/2 + 2T(n/4)) = 2n + 4T(n/4)
          = ...
          = n log n
 - Worst Case
   T(n) = n + T(n-1)
          = n + (n-1) + T(n-2)
          = ...
          = O(n^2)