Bubble sorting with linked list

Question

I am writing a bubble sort function to sort nodes in a doubly linked list. My function is very close to working, but I am missing something simple and I can't figure it out.

void sort (struct lnode** head, void (*swapPtr) (struct lnode** head, struct lnode* n1, struct lnode* n2),
                            int(*comparePtr) (void* v1, void* v2)) {

struct lnode* next;
struct lnode* temp = *head;
int comp;
struct lnode* temp2;
int count = 0;

while (temp != NULL) {
    temp2 = nodeGetNext(temp);
    temp = temp2;
    count++;

}

temp = *head;
for(int i = 0; i < count; i++) {
    next = nodeGetNext(temp);


    comp = comparePtr(temp,next);
    if (comp == 1)
        swapPtr(head, temp, next);
    else if (comp == -1)
        swapPtr(head, next, temp);

    temp = nodeGetNext(next);
}


}

When I run the function, It only swaps the first two nodes. I'm guessing I am not setting temp properly at the end of the for loop. I have tried a few different things but have not had any success. I would appreciate any help!

Answer 1

I've done this using a nested loop since the number of traverses you have go through a list is equal to number of nodes minus 1, that is in worst case scenario. The loop for passes shall stop when there are no swaps done from previous pass (thanks to detunized).

hasSwap = 1; /* enable the first pass to execute */
for(i=0; i<len-1 && hasSwap == 1; i++)
{
    hasSwap = 0; /* initially, there is no swap in this pass */
    for(j=0; j<len-1; j++)
    {
       if(l[j] > l[j+1])
       {
            t = l[j];
            l[j] = l[j+1];
            l[j+1] = t; 
            hasSwap = 1; /* the pass has at least 1 swap, if not set, there will be no other pass */
       } 
    }

    printf("Pass %d: ", i);
    for(k=0; k<len; k++)
    {
       printf("%d", l[k]);
    }
    printf("\n");
}

Example 1: Worst case scenario, list is sorted in descending order.

5, 4, 3

First pass:

i = 0, j = 0, hasSwap = 1 -> [5], [4], 3

i = 0, j = 1, hasSwap = 1 -> 4 , [5], [3]

Has swaps from previous pass? Yes, proceed.

Second pass:

i = 1, j = 0, hasSwap = 1 -> [4], [3], 5

i = 1, j = 1, hasSwap = 1 -> 3 , [4], [5]

Has swaps from previous pass? No, but reached the maximum number of pass.

Example 2: And this is sorted already.

3, 4, 5

First pass:

i = 0, j = 0, hasSwap = 0 -> 3, 4, 5

i = 0, j = 1, hasSwap = 0 -> 3, 4, 5

Has swaps from previous pass? None, stop.

Answer 2

It seems like you make only one pass on over the list. You need to keep looping over the list and keep swapping until there's nothing to swap. Check this answer for an example and Wikipedia for the detailed algorithm description.