재귀 없는 퀵정렬 소스코드

#include <stdio.h>
#include <time.h>
#include <stdlib.h>
 
#define N 10000000
#define R 100000
#define STKSIZE N
 
unsigned int arr[N];
 
int top = 0;
int stack[STKSIZE];
 
void init_stack() {
    top = 0;
}
 
void push(int i) {
    if (top < STKSIZE)
        stack[top++] = i;
    else {
        printf("stack full\n");
        exit(0);
        return;
    }
}
 
int pop() {
    if (top != 0)
        return stack[--top];
    else
        return 0;
}
 
int isStackEmpty() {
    if (top != 0)
        return 0;
    else
        return 1;
}
 
void quickSort() {
    int p, t;
    int i, j;
    int l, r;
    init_stack();
    l = 0;
    r = N - 1;
    push(r);
    push(l);
    while (!isStackEmpty()) {
        l = pop();
        r = pop();
        if (r - l > 0) {
            p = arr[r];
            i = l - 1;
            j = r;
            while (1) {
                while (arr[++i] < p);
                while (arr[--j] > p);
                if (i >= j)
                    break;
                t = arr[i];
                arr[i] = arr[j];
                arr[j] = t;
            }
 
            t = arr[i];
            arr[i] = arr[r];
            arr[r] = t;
            push(r);
            push(i + 1);
            push(i - 1);
            push(l);
        }
    }
}
 

 

위의 소스코드는 재귀함수를 사용하지 않는 퀵정렬의 소스코드입니다.

재귀함수의 퀵정렬은 데이터 수가 많아지면 재귀 빈도가 높아져서 스택 오버플로우가 발생하는 문제가 있습니다.

그러나 재귀없는 퀵정렬은 그러한 문제가 발생하지 않습니다.

참고:http://danamoni.tistory.com/entry/qsort%EC%97%90-%EA%B4%80%ED%95%9C-%EB%AA%A8%EB%93%A0-%EA%B2%83