<6> Q14. 자료구조와 함께 배우는 알고리즘 입문 (C언어)

#include <stdio.h>
#include <stdlib.h>
#define swap(type, x, y) \
    do                   \
    {                    \
        type t = x;      \
        x = y;           \
        y = t;           \
    } while (0)

#include <stdio.h>
#include <stdlib.h>

typedef struct
{
    int max;
    int ptr;
    int *stk;
} IntStack;

int Initialize(IntStack *s, int max)
{
    s->ptr = 0;
    if ((s->stk = (int *)calloc(max, sizeof(int))) == NULL)
    {
        s->max = 0;
        return -1;
    }
    s->max = max;
    return 0;
}

int Push(IntStack *s, int x)
{
    if (s->ptr >= s->max)
        return -1;
    s->stk[s->ptr++] = x;
    return 0;
}

int Pop(IntStack *s, int *x)
{
    if (s->ptr <= 0)
        return -1;
    *x = s->stk[--s->ptr];
    return 0;
}

int IsEmpty(const IntStack *s)
{
    return s->ptr <= 0;
}

void Terminate(IntStack *s)
{
    if (s->stk != NULL)
        free(s->stk);
    s->max = s->ptr = 0;
}

void quick(int a[], int left, int right)
{
    IntStack lstack;
    IntStack rstack;

    Initialize(&lstack, right - left + 1);
    Initialize(&rstack, right - left + 1);

    Push(&lstack, left);
    Push(&rstack, right);

    while (!IsEmpty(&lstack))
    {
        int pl = (Pop(&lstack, &left), left);
        int pr = (Pop(&rstack, &right), right);
        printf("{%d, %d}을 분할\n",pl,pr);
        int x = a[(left + right) / 2];
        do
        {
            while (a[pl] < x)
                pl++;
            while (a[pr] > x)
                pr--;
            if (pl <= pr)
            {
                swap(int, a[pl], a[pr]);
                pl++;
                pr--;
            }
        } while (pl <= pr);

        if (left < pr)
        {
            printf("Push {%d, %d}\n",left,pr);
            Push(&lstack, left);
            Push(&rstack, pr);
        }
        if (pl < right)
        {
            printf("Push {%d, %d}\n",pl,right);
            Push(&lstack, pl);
            Push(&rstack, right);
        }
    }
    printf("종료\n");
    Terminate(&lstack);
    Terminate(&rstack);
}

void quick_sort(int a[], int n)
{
    quick(a, 0, n - 1);
}
int main(void)
{
    int i, nx;
    int *x;
    puts("퀵 정렬");
    printf("요소 개수 : ");
    scanf("%d", &nx);
    x = calloc(nx, sizeof(int));
    for (i = 0; i < nx; i++)
    {
        printf("x[%d] : ", i);
        scanf("%d", &x[i]);
    }
    quick_sort(x, nx);
    puts("오름차순으로 정렬했습니다.");
    for (i = 0; i < nx; i++)
        printf("x[%d] = %d\n", i, x[i]);
    free(x);

    return 0;
}