quicksort on doubly-linked list causes bad pointer?

Question

I was writing this as part of an exercise to understand the various sorting algorithms and to judge what works best in different situations. Because I never really learned them :(

This was my interpretation of wikipedia's pseudocode, with the additional "equal" list added for speed (hopefully). and a couple of other minor additions. My program crashes once the sorting gets towards the end (2 or 3 nodes remaining). The program sorts descending order.

GDB indicates its a bad pointer with the top variable in the while loop. Apparently it didn't have the null pointer at the end of the list. I suspect the quicklist function is fine but its one of the supporting functions causing the problem. I need help spotting what I did wrong

quicksort:

void quicksort(NODE **top,NODE **last,int * size)
{
    if((*size)>3)
    {
        NODE *pivot = pop(last);
        *last=0;
        NODE *greater_node=0;int greater=0; NODE * glast=0;
        NODE *equal_node=0;int equal=0;
        NODE *less_node=0;int less=0; NODE * llast=0;
        int pivot_value=pivot->value;
        int value_at=0;
        while(*top)
        {
            value_at=(*top)->value;
            if(value_at>pivot_value)
            {
                push2(&greater_node,pop(top));
                if(!greater) { glast=greater_node; }
                greater++;
            }
            if(value_at<pivot_value)
            {
                push2(&less_node,pop(top));
                if(!less) { llast=less_node; }
                less++;
            }
            else
            {
                push2(&equal_node,pop(top));
                equal++;
            }
        }
        quicksort(&greater_node,&glast,&greater);
        quicksort(&less_node,&llast,&less);
        cat(&equal_node,less_node);
            cat(&pivot,equal_node);
        cat(&greater_node,pivot);
            *top=greater_node;
        *size = greater+less+equal+1;
    }
    else if((*size)==3)
    {
        NODE *a=(*top);
        NODE *b=(*top)->next;
        NODE *c=(*top)->next->next;
        if(a->value<b->value) { swap(&(a->value),&(b->value)); }
        if(b->value<c->value) { swap(&(b->value),&(c->value)); }
        if(a->value<b->value) { swap(&(a->value),&(b->value)); }
    }
    else if((*size)==2)
    {
            if((*top)->value<(*top)->next->value) swap(&((*top)->value),&((*top)->next->value));
    }
}

Answer 1

I don't like to leave things unresolved. IDK if I actually modified the core function compared to the other methods. Specifically the pop function. But I thought I'd post it for completeness.

void quicksort(NODE **top,NODE **last,int * size)
{
    if((*size)>3)
    {
        NODE *pivot = pop(last);
        NODE *greater_node=0;int greater=0; NODE * glast=0;
        NODE *equal_node=0;int equal=0;
        NODE *less_node=0;int less=0; NODE * llast=0;
        int pivot_value=pivot->value;
        int value_at=0;
        while(*top)
        {
            value_at=(*top)->value;
            if(value_at>pivot_value)
            {
                push2(&greater_node,pop(top));
                if(!greater) { glast=greater_node; }
                greater++;
            }
            else if(value_at<pivot_value)
            {
                push2(&less_node,pop(top));
                if(!less) { llast=less_node; }
                less++;
            }
            else
            {
                push2(&equal_node,pop(top));
                equal++;
            }
        }
        quicksort(&greater_node,&glast,&greater);
        quicksort(&less_node,&llast,&less);
        if(less) { cat(&equal_node,less_node); }
            cat(&pivot,equal_node);
        cat(&greater_node,pivot);
            *top=greater_node;
        *size = greater+less+equal+1;
    }
    else if((*size)==3)
    {
        NODE *a=(*top);
        NODE *b=(*top)->next;
        NODE *c=(*top)->next->next;
        if(a->value<b->value) { swap(&(a->value),&(b->value)); }
        if(b->value<c->value) { swap(&(b->value),&(c->value)); }
        if(a->value<b->value) { swap(&(a->value),&(b->value)); }
    }
    else if((*size)==2)
    {
        NODE *a=(*top);
        NODE *b=(*top)->next;
        if(a->value<b->value) { swap(&(a->value),&(b->value)); }
        //if((*top)->value<(*top)->next->value) swap(&((*top)->value),&((*top)->next->value));
    }
}

Answer 2

I didn't get as far as the quicksort function itself, but your pop() looks suspect. Specifically, if *top points to the first element, the

        (*top)=(*top)->next;

will have wiped out *top before you get a chance to do anything useful with it.

My overall advice would be to find the simplest input on which the code malfunctions, and step through your program in a debugger, watching what's happening. This should enable you to pinpoint the exact moment things start deviating from the plan.

An alternative strategy is to come up with a series of unit tests for each function, to test every building block in isolation.