<6> Q17. 자료구조와 함께 배우는 알고리즘 입문 (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 med3(int a, int b, int c)
{
    if (a >= b)
        if (b >= c)
            return b;
        else if (a <= c)
            return a;
        else
            return c;
    else if (a > c)
        return a;
    else if (b > c)
        return c;
    else
        return b;
}
#include <stdio.h>
#include <stdlib.h>
#define swap(type, x, y) \
    do                   \
    {                    \
        type t = x;      \
        x = y;           \
        y = t;           \
    } while (0)

void quick(int a[], int left, int right)
{
    int pl = left;
    int pr = right;
    int x = med3(a[pl], a[(pl + pr) / 2], a[pr]);
    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)
        quick(a, left, pr);
    if (pl < right)
        quick(a, pl, right);
}

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;
}

비재귀 버전

#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 med3(int a, int b, int c)
{
    if (a >= b)
        if (b >= c)
            return b;
        else if (a <= c)
            return a;
        else
            return c;
    else if (a > c)
        return a;
    else if (b > c)
        return c;
    else
        return b;
}

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)
{
    if (right < 8)
    {
        int i, j;
        for (i = 1; i < right + 1; i++)
        {
            int tmp = a[i];
            for (j = i; j > 0 && a[j - 1] > tmp; j--)
                a[j] = a[j - 1];
            a[j] = tmp;
        }
        return;
    }
    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 = med3(a[pl], a[(pl + pr) / 2], a[pr]);
        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;
}