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

/* run this program using the console pauser or add your own getch, system("pause") or input loop */


void swap_str_ptrs(char const **arg1, char const **arg2)
{
    const char *tmp = *arg1;
    *arg1 = *arg2;
    *arg2 = tmp;
}

void print_list(char const *args[], unsigned len)
{
    unsigned i=0;
    for (;i<len;++i)
        puts(args[i]);
}


void quicksort_strs(char const *args[], unsigned int len)
{
    // holds our non-recursive stack of segments
    struct segment
    {
        char const **arr;
        unsigned int len;
        struct segment* next;
    } *stack = NULL;

    stack = malloc(sizeof(*stack));
    stack->arr = args;
    stack->len = len;
    stack->next = NULL;

    while (stack != NULL)
    {
        unsigned int i, pvt=0;
        struct segment *tmp = stack;
        stack = stack->next;

        // pull values and delete segment record
        args = tmp->arr;
        len = tmp->len;
        free(tmp);

        // nothing to unary segments
        if (len <= 1)
            continue;

        // swap a randomly selected value to the last node
        swap_str_ptrs(args+((unsigned int)rand() % len), args+len-1);

        // reset the pivot index to zero, then scan
        for (i=0;i<len-1;++i)
        {
            if (strcmp(args[i], args[len-1]) < 0)
                swap_str_ptrs(args+i, args+pvt++);
        }
        // move the pivot value into its place
        swap_str_ptrs(args+pvt, args+len-1);

        // lhs segment push
        if (pvt > 1)
        {
            tmp = malloc(sizeof(*tmp));
            tmp->arr = args;
            tmp->len = pvt;
            tmp->next = stack;
            stack = tmp;
        }
        // rhs segment push
        if ((len - ++pvt) > 1)
        {
            tmp = malloc(sizeof(*tmp));
            tmp->arr = args+pvt;
            tmp->len = len-pvt;
            tmp->next = stack;
            stack = tmp;
        }
    }
}

int main()
{
    char const *args[] =
    {
        "this", "is", "a", "test", "of", "quicksort", "with", "strings"
    };

    srand((unsigned)time(NULL));
    quicksort_strs(args, sizeof(args)/sizeof(*args));
    print_list(args, sizeof(args)/sizeof(*args));
    return 0;
}