qsort.c

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

void swap(int *a, int *b)
{
    int buffer;
    buffer = *a;
    *a = *b;
    *b = buffer;
}

struct Task
{
    int low;
    int high;
};
struct stack
{
    struct Task *data;
    int cap;
    int top;
};
void InitStack(struct stack *s, int n)
{
    s->data = calloc(n, sizeof(struct Task));
    s->cap = n;
    s->top = 0;
}
void Push(struct stack *s, struct Task x)
{
    s->data[s->top] = x;
    s->top++;
}
struct Task Pop(struct stack *s)
{
    return s->data[--s->top];
}
int StackEmpty(struct stack *s)
{
    return (s->top == 0) ? 1 : 0;
}

void Quicksort(int *arr, int n)
{
    int i, k, left, right, mid, q, buffer;

    struct stack tasks;
    InitStack(&tasks, 0);
    struct Task start;
    start.low = 0;
    start.high = n - 1;
    Push(&tasks, start);

    while (!StackEmpty(&tasks))
    {
        struct Task temp = Pop(&tasks);
        left = temp.low;
        right = temp.high;

        while (left < right)
        {
            mid = (left + right) >> 1;
            i = left;
            k = right;
            q = arr[mid];

            for (; i <= k; i++, k--)
            {
                while (arr[i] < q)
                    i++;
                while (q < arr[k])
                    k--;

                if (i <= k)
                    swap(&arr[i], &arr[k]);
            }

            if (i < mid)
            {
                if (i < right)
                {
                    temp.low = i;
                    temp.high = right;
                    Push(&tasks, temp);
                }

                right = k;
            }
            else
            {
                if (k > left)
                {
                    temp.low = left;
                    temp.high = k;
                    Push(&tasks, temp);
                }

                left = i;
            }
        }
    }

    free(tasks.data);
}

int main()
{
    int i, n;
    scanf("%d", &n);
    int arr[n];
    for (i = 0; i < n; i++)
        scanf("%d", &arr[i]);

    Quicksort(arr, n);


    for (i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");

    return 0;
}