Quicksort string array in C

There is zero reason to allocate for quicksort, and in fact the function can easily suffice in your case with a simple interface of quicksort(char *arr[], unsigned int len), using pointer-math for the subsequence invocations.

Provide a swap algorithm for exchanging pointers:

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

Then the algorithm is:

void quicksort_strs(char const *args[], unsigned int len)
{
    unsigned int i, pvt=0;

    if (len <= 1)
        return;

    // 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);

    // and invoke on the subsequences. does NOT include the pivot-slot
    quicksort_strs(args, pvt++);
    quicksort_strs(args+pvt, len - pvt);
}

Thats everything. including the partitioning.

How It Works

There are two general recursive quicksort algorithms: the squeeze, and the sweep. This is the sweep algorithm. We march up the sequence, swapping any element "less" than than pivot value (which is swapped to the end of the sequence before the loop starts) to a target slot, the index of which is initially the beginning of the sequence and increases with each swap operation. When the "sweep" is finished, the pvt index is where the pivot value belongs, as everything below that slot is "less" than the that value. So one more swap is made to put the pivot value into position. After that we have two partitions, which are recursed. It is vital that the slot we just identified as the pivot location is not included in either of those partitions. It is the only value we know is in its final resting place.

Test Harnass

Including the above code, we test this with a basic set of strings purposely out of order:

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

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

Output

a
is
of
quicksort
strings
test
this
with

Non-recursive implementation

It should be noted that the above algorithm lends itself beautifully to a non-recursive implementation. A local dynamic stack is used for holding pairs of data: an pointer and a length. Optimized to not push trivial segments (segments of length 1 or 0) on to the stack, one implementation would like like this:

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

Obviously having a canned node-stack implementation would shorten this up considerably, but the idea should be readily apparent. A realloc() schema for holding nodes on the end of the "stack" rather than the beginning would be equally interesting, as it would eliminate the need to next pointer management, replaced with a top index instead.

Anyway, good luck, and I hope it helps.