Bubble sort for linked list

Question

I am working on a bubble sort function for a linked list. Here is the header for the function:

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

I don't really understand the function pointers being used. swapPtr is a function pointer to a function that is used to swap two nodes in the list. comparePtr is used as a pointer to one of three functions, all of which compare either the values in a certain member of the structure which is used to store the number of counts and line number of a given word. The possibilities are:

countComp — takes two nodes and compares the number of times the word shows up, returns 0 if equal, 1 if node1 > node 2 and -1 for the reverse.
wordComp — compares the words for the given nodes same return values as above.
lineComp — compares the line number the word occurs on same return values as above.

I understand how the bubble sort works and the general steps to achieve a sorted list. The area I am confused on is on how to call comparePtr and what do I need to pass to it? Also I have a test.c file used for testing my sorting methods. How would I go about calling the sort function? I'm not sure what to pass for the second and third arguments.

If someone could help explain this to me, it'd be great!

I assume countComp compares number of characters, wordComp compares words, lineComp compares lines, right? Just define your `swap` function, choose what you want to compare, and call it like `sort(my_head, &swap, &_ANY_Comp)`. — admiring_shannon, Oct 09 '12 at 05:04
The parameter of `comparePtr` is opaque, so the assumption is: the function implementation understands what is passed in and how to cast it to a meaningful type. `sort` also needs to know that, as the caller. — admiring_shannon, Oct 09 '12 at 05:08

score 0 · Answer 1 · answered Oct 09 '12 at 05:01

If you have two functions:

void intSwapPtr(struct lnode** head, struct lnode* n1, struct lnode* n2) {
    //definition
}

int intComparePtr(void* v1, void* v2) {
    //definition
}

then you can call sort by just passing those functions as arguments. The functions will be implicitly converted in to pointers to functions when used as arguments.

swap(listHead, intSwapPtr, comparePtr)

Inside the definition of swap, you can call swapPtr and comparePtr in the same way as you would call any other function, they will be implicitly dereferenced.

score 0 · Answer 2 · edited May 23 '17 at 10:24

0

It looks to me like whoever created this header wanted the comparePtr to take two pointers and return an int telling you which node is "greater" in the ordering of nodes.

So you would call it like this:

lnode * a = ...;
lnode * b = ...;
int comparison = comparePtr(a, b);
if (comparison < 0)
{
    // we know a comes after b
}
else if (comparison > 0)
{
    // we know a comes after b
}
else
{
    // a and b are equal as far as ordering is concerned
}

This is like the ruby spaceship operator.

edited May 23 '17 at 10:24

Community

1
1

answered Oct 09 '12 at 05:02

David Grayson

84,103
24
152
189

1

There is no need to deal with three cases. If `a` and `b` are in order, you leave them alone, otherwise swap. – Kaz Oct 09 '12 at 05:10
Okay..I am confused on where `lnode* a` and `lnode* b` come from. – Matt Altepeter Oct 09 '12 at 05:11
Matt, a and b point to whatever two nodes you want to consider swapping. Do you know how the bubble sort algorithm works? The algorithm tells you which nodes to consider swapping. On the first iteration, you would probably do `a = *head` and `b = a->next` so that a and b point to the first two nodes in the list. – David Grayson Oct 09 '12 at 05:16

score 0 · Answer 3 · answered Jul 29 '13 at 18:03

void sortList(node *start) { head = start;

for(ptr = head; ptr != NULL; ptr = ptr->next)
{
    for(newptr = ptr->next; newptr != NULL; newptr = newptr->next)
    {
        if(ptr->data > newptr->data)
        {
            int temp = ptr->data;
            ptr->data = newptr->data;
            newptr->data = temp;
        }
    }
}

}

This C++ function for sorting a given link list is working fine.

Bubble sort for linked list

3 Answers3