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

재귀 버전

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

int sort(int x[], int a, int b, int c)
{
    if (x[b] < x[a])
        swap(int, x[b], x[a]);
    if (x[c] < x[b])
        swap(int, x[c], x[b]);
    if (x[b] < x[a])
        swap(int, x[b], x[a]);
    return b;
}
void insertion(int a[], int n)
{
    int i, j;
    for (i = 1; i < n; i++)
    {
        int tmp = a[i];
        for (j = i; j > 0 && a[j - 1] > tmp; j--)
            a[j] = a[j - 1];
        a[j] = tmp;
    }
}

void quick(int a[], int left, int right)
{
    if (right - left < 9)
    {
        insertion(&a[left], right - left + 1);
    }
    else
    {
        int pl = left;
        int pr = right;
        int x;
        int y = sort(a, pl, (pl + pr) / 2, pr);
        x = a[y];
        swap(int, a[y], a[right - 1]);
        pl++;
        pr -= 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 (pr - left > right - pl)
        {
            if (left < pr)
                quick(a, left, pr);
        }
        else
        {
            if (pl < right)
                quick(a, pl, right);
        }
    }
}

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(x, 0, nx - 1);
    puts("오름차순으로 정렬했습니다.");
    for (i = 0; i < nx; i++)
        printf("x[%d] = %d\n", i, x[i]);
    free(x);

    return 0;
}

비재귀 버전

#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 sort(int x[], int a, int b, int c)
{
    if (x[b] < x[a])
        swap(int, x[b], x[a]);
    if (x[c] < x[b])
        swap(int, x[c], x[b]);
    if (x[b] < x[a])
        swap(int, x[b], x[a]);
    return b;
}

void insertion(int a[], int n)
{
    int i, j;
    for (i = 1; i < n; i++)
    {
        int tmp = a[i];
        for (j = i; j > 0 && a[j - 1] > tmp; j--)
            a[j] = a[j - 1];
        a[j] = tmp;
    }
}

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);
        int x;
        int y = sort(a, pl, (pl + pr) / 2, pr);
        x = a[y];
        swap(int, a[y], a[right - 1]);
        pl++;
        pr -= 2;
        
        if (right - left < 9)
        {
            insertion(&a[left], right - left + 1);
        }
        else
        {
            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 (pr > right - pl)
            {
                if (left < pr)
                {
                    Push(&lstack, left);
                    Push(&rstack, pr);
                }
                if (pl < right)
                {
                    Push(&lstack, pl);
                    Push(&rstack, right);
                }
            }
            else
            {
                if (pl < right)
                {
                    Push(&lstack, pl);
                    Push(&rstack, right);
                }
                if (left < pr)
                {
                    Push(&lstack, left);
                    Push(&rstack, pr);
                }
            }
        }
    }
    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;
}