CODEWITHSUNDEEP
csortinglinked-listbubble-sort
Zobo
Zobo

Reputation: 293

Bubble sort double linked list

Hello everyone I'm trying to sort my double linked list in C using bubble sort algorithm. Here is my code:

struct node {
                unsigned char key;
                unsigned char num;
                struct node *left;
                struct node *right;
            };

Here is my sort funcion: 

void sort(int count, struct node *t_node)
{
    struct node *tmp,*nextnode, *node1, *node2;

    for(node1 = t_node;node1->right != NULL ;node1 = node1->right) {
        for(node2 = node1->right; node2->right != NULL; node2 = node2->right) {
            if(node2->key > node2->right->key)
            {               
                nextnode = node2->right;
                tmp = node2->left;
                node2->right = nextnode->right;             
                node2->left = nextnode->left;
                nextnode->right = node2;
                nextnode->left = tmp;
            }
        }
    }

}

It works in 80% because for example data: 

node1 key=3
node2 key=144
node3 key=49
node4 key=207

The result after sort is:

node1 key=3
node2 key=144
node4 key=207

Why my third node disappeared? Where is the problem?

Upvotes: 0

Views: 1796

Answers (2)

starrify
starrify

Reputation: 14761

It's a double-linked list. To swap two nodes, typically 6 pointers need to be updated. Say we have A <-> B <-> C <-> D and you want to swap B and C: you'll need to update right of A, B, and C, and also left of B, C, and D.

Your code is only updating 4 pointers here:

        if(node2->key > node2->right->key)
        {               
            nextnode = node2->right;
            tmp = node2->left;
            node2->right = nextnode->right;             
            node2->left = nextnode->left;
            nextnode->right = node2;
            nextnode->left = tmp;
        }

This shall fix your issue:

        if(node2->key > node2->right->key)
        {               
            nextnode = node2->right;
            tmp = node2->left;
            if (tmp)
                tmp->right = nextnode;
            if (nextnode->right)
                nextnode->right->left = node2;
            node2->right = nextnode->right;             
            node2->left = nextnode->left;
            nextnode->right = node2;
            nextnode->left = tmp;
        }

Upvotes: 2

Eregrith
Eregrith

Reputation: 4366

You also need to replace the previous node (tmp in your code but I'd suggest a more explicit name...) right pointer, and the next-next node's left pointer :

tmp <-> node1 <-> node2 <-> nextnext

You are on node1 and detect you need to swap it with node2 :

  • You need to have tmp -> node1 changed to tmp -> node2
  • You need to have node2 <- nextnext changed to node1 <- nextnext as well

Upvotes: 1

Related Questions