Hi, I'm working on a quick sort for double linked list. All work except the first item. I don't know what is wrong. Can u plz help me find the error? Here is my code.

dlist_t* quick_sort(dlist_t* list)
{
     dlnode_t *tnode = NULL, *first = NULL, *last = NULL;

     first = list->head;
     last = list->foot;
     tnode = list->head;

        printf("Before Sort=");
        while (tnode != NULL)
        { 
        printf(" %d ", *((int *) tnode->data));
        tnode = tnode->next;
        }
      printf("\n\n");
     quick_sorting(list, first, NULL);
     return list;
}

void quick_sorting(dlist_t *list, dlnode_t *less, dlnode_t *greater)
{
   dlnode_t *tnode= NULL, *pivot = NULL, *i, *next, *temp = NULL, *last = NULL;

   pivot = less -> next;
   temp = pivot;
   last = greater ? greater->next : NULL;

   if (less == greater || less->next == greater)
        return; 

   for(i = pivot->next; i != last; i = next)
   { 
        next = i->next;  /*n = pivot -> next -> next*/
        list_detach(list, i);
        if ((cmp_int(i -> data, pivot-> data) == SMALLER))
            list_insert_after(less, i);
        else
            list_insert_after(pivot, temp == pivot ? (temp = i) : i);
        tnode = list->head;

        printf("Sorting=");
        while (tnode != NULL)
        { if(tnode == pivot) printf("->");
        printf(" %d ", *((int *) tnode->data));
        tnode = tnode->next;
        }
      printf("\n\n");
   }


   quick_sorting(list, pivot, temp);
   quick_sorting(list, less, pivot -> prev);
}

void list_insert_after(dlnode_t *p,dlnode_t *n)
{
    dlnode_t *next = NULL;
    n->prev = p; 
    n->next = p->next;
    if (p->next)
        next = p -> next;
        next->prev = n;
    p->next = n;
}

void list_detach(dlist_t *list,dlnode_t *n)
{
    dlnode_t *prev = NULL;
    if (n != list->head)
    {
        prev = n->prev;
        prev->next = n->next;
        if (n->next)
            n->next->prev = n->prev;
    }
    else
        printf("Tried to detach head!");
}

Please provide your definition of the dlist structure. I can infer it from the code, that that is not really reliable...

Here is the code

struct dlnode
    {
        void *data;     /* A pointer to a generic satellite data payload */
        dlnode_t *next; /* A pointer to the next item in the list */
        dlnode_t *prev; /* A pointer to the previous item in the list */
    };

    typedef struct
    {
        dlnode_t *head; /* A pointer to the head node of the list */
        dlnode_t *foot; /* A pointer to the foot node of the list */
        int list_len;   /* Total number of items in the list */
        int size;       /* Size of the list in bytes */
    } dlist_t;

Edited 4 Years Ago by smith32

This question has already been answered. Start a new discussion instead.