Ordering a linked list by a value -

Question

Please bear with me, I'm new to stackoverflow so let me attempt to explain my problem, if there are any points that I could improve on in my question making please be sure to comment and I'll edit the question

Okay, so I've got myself a Linked list, I want to order it by a value in the list which happens to be the price:

tmpPtr->item->price;

The problem I'm having is switching the positions, here's the code:

struct inventory *sort_list() {
        struct inventory *tmpPtr = pFirstNode;
        struct inventory *temp = NULL;
        struct inventory *tmpNxt = pFirstNode->next;
        int tmp;
        while(tmpNxt != NULL){
               while(tmpNxt != tmpPtr){
                        if(tmpNxt->item->price < tmpPtr->item->price){
                                // if next item price is smaller than current
                                // temp for the next item
                                // heres the problem....
                                temp = tmpNxt->next;
                                tmpNxt->next = tmpPtr;
                                tmpPtr->next = temp;
                        }
                        else{
                            // if not any smaller continue    
                            tmpPtr = tmpPtr->next;

                        }
                }
                tmpPtr = pFirstNode;
                tmpNxt = tmpNxt->next;
        }
        return tmpPtr; 
    }

The values aren't ordering as I expected from my logic, any pointers would be great EDIT:

struct inventory *sort_list() {
        struct inventory *tmpPtr = pFirstNode;
        struct inventory *temp = NULL;
        struct inventory *tmpNxt = pFirstNode->next;
        while(tmpNxt != NULL){
               while(tmpNxt != tmpPtr){
                        if(tmpNxt->item->price < tmpPtr->item->price){
                                // if next item price is smaller than current
                                // temp for the next item
                                if(tmpPtr == pFirstNode){
                                    tmpPtr = pFirstNode->next; // tmpPtr is now second node
                                    pFirstNode->next = tmpPtr->next;
                                    tmpPtr->next = pFirstNode;
                                    pFirstNode = tmpPtr;
                                }

                                tmpNxt = tmpPtr->next;
                                tmpPtr->next = tmpNxt->next;
                                tmpNxt->next = tmpPtr;
                                temp->next = tmpNxt;
                        }

                }
                  temp = tmpPtr;
        }
        return tmpPtr; // Place holder
    }

Answer 1

To swap two adjacent singly linked list members, you need three adjacent members (the one that is behind the two you want to swap), unless one of them is the head of the list.

1. Head of the list case → swap list_head and list_head->next

   assert(list_head->next);
   next = list_head->next;
   list_head->next = next->next;
   next->next = list_head;
   list_head = next;
   

2. Other cases → swap cur and cur->next

   assert(prev->next == cur && cur->next);
   next = cur->next;
   cur->next = next->next;
   next->next = cur;
   prev->next = next;
   

However, these two cases can be collapsed into a single case if the previous node is redefined to be the address of the next member of the previous node.

void swap_cur_with_next (node **pnext, node *cur) {
    assert(*pnext == cur && cur->next);
    node *next = cur->next;
    cur->next = next->next;
    next->next = cur;
    *pnext = next;
}

/* swap list_head with list_head->next */
swap_cur_with_next(&list_head, list_head);

/* swap cur with cur->next */
swap_cur_with_next(&prev->next, cur);

With a correct swap routine, it is easier to implement your bubble sort algorithm on a list. The code structure might look like this:

void bubble_up(node **pnext, node *cur) {
    while (cur->next) {
        if (need_to_swap(cur)) {
            swap_cur_with_next(pnext, cur);
        }
        pnext = &(*pnext)->next;
        cur = *pnext;
    }
}

node **pnext = &list_head;
while (*pnext) {
    bubble_up(pnext, *pnext);
    pnext = &(*pnext)->next;
}

However, as noted in a different answer, merge sort is a more natural and efficient algorithm to use to sort a list.

At the very least, you can pack the node pointers into an array, and use qsort() to sort the node pointers, and then link them up in sorted order afterwards.

Answer 2

When you are in the inner if condition, you have the following state:

Node1 -> tmpPtr -> tmpNxt -> Node2

What you want to achieve is:

Node1 -> tmpNxt -> tmpPtr -> Node2

Then you have the following code:

1. temp = tmpNxt->next; // makes temp = Node2
2. tmpNxt->next = tmpPtr; // changes list to Node1 -> tmpPtr <-> tmpNxt,
3. tmpPtr->next = temp; // changes list to Node1 ->tmpPtr and tmpNxt -> tmpPtr -> Node2

So as you can see, you are missing the link from Node1 -> tmpNext. You can do that and examine your results.