C code implementing bubble sort for linked list isn't working-CodePudding

I am trying to apply bubble sort on linklist. for that I have implemented my own list but the code isn't working as it somehow isn't printing any value when all of the linklist values are printed.

The course I was writing code for required me to write everything from scratch. I wrote a bubble sort function which isn't working as it should, It is somehow tempering the root due to which I am not able to print all of the values of the linklist.

I also tried to print string "values swapped" to understand how many times is the loop running, turns out it is running the number of times it should run. but doing something due to which I can't print the values from the root.

#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
#include <stdbool.h>

typedef struct Node
{
    int value;
    struct Node *next;
} Node;

Node *insert(Node *root, int val)
{
    Node *new = (Node *)malloc(sizeof(Node));
    new->value = val;
    new->next = NULL;
    if (root == NULL)
    {
        root = new;
        return root;
    }
    while (root->next != NULL)
    {
        root = root->next;
    }
    root->next = new;
    return NULL;
}

void swap(Node *n1, Node *n2)
{
    int temp = n1->value;
    n1->value = n2->value;
    n2->value = temp;
}

void print(Node *root)
{
    if (root == NULL)
        return;
    printf("%d ", root->value);
    print(root->next);
}

void bubbleSort(Node *root)
{
    bool toSwap = true;
    Node *trav = root;
    while (toSwap)
    {
        toSwap = false;
        while (trav != NULL)
        {
            if (trav->value > trav->next->value)
            {
                swap(trav, trav->next);
                printf("Values Swapped \n");
                toSwap = true;
            }

            trav = trav->next;
        }
    }
}

int main(void)
{
    Node *root = NULL;
    root = insert(root, 4);
    insert(root, 1);
    insert(root, 5);
    insert(root, 3);
    bubbleSort(root);
    print(root);
    return 0;
}

CodePudding user response：

Your code runs in O(n) time, since trav moves forward at every iteration and the algorithm terminates when trav has reached the end of the list. However, Bubble Sort is a O(n^2) time algorithm.

You need to use two pointers. Let's call the second pointer trav_2. The first pointer (trav) simply acts as a counter to make sure that the second pointer (trav_2) iterates through the list performing the necessary swaps n times. If you replace your while loop with the following logic, it should work fine:

while (trav!=NULL)
{
    toSwap = false;
    Node *trav_2 = root;
    while (trav_2 != NULL && trav_2->next!=NULL)
    {
        if (trav_2->value > trav_2->next->value)
        {
            swap(trav_2, trav_2->next);
            printf("Values Swapped \n");
            toSwap = true;
        }

        trav_2 = trav_2->next;
    }
    trav = trav->next;
}

I have also fixed some pointer dereferencing errors you had in your code (the ones others have mentioned). However, fixing them wasn't enough. The logic was flawed too.

CodePudding user response：

Fixing the existing code has already been done by Harsh. I'm going to show you how this is done by pure pointer juggling rather than swapping datum across nodes. Normally that is the purpose of this exercise. Imagine an enormous data payload held within each node that makes it obtrusive to copy. You don't have to if you just jostle the pointers to rearrange the list.

For each enumeration the "largest" element will bubble to the end. it is pruned from there and pushed on to the head of a new list. When the algorithm is done one of two things will have transpired:

We ran out of nodes. OR
We ejected early due to noswap-optimization.

The first of these is trivial. We already have all the nodes and they're already sorted. The latter complicates things because we still have two sorted lists: one is the list of items we've pruned thus far as we push-built our sorted result, the other is the remaining list that we detected as already-sorted and ejected the sorting loop. Fortunately, due to the manner in which we tracked the last node pointer in remaining source list, it makes linking them easy and we'll have our final result.

Finally, because root can change, the algorithm requires the new root be returned from the function. That, in turn, requires a change in main. This is not specific to the aforementioned algorithm. It would have to be done regardless as a separate, but important, bug fix.

The sorting implementation appears below:

Node *bubbleSort(Node *root)
{
    Node *result = NULL;
    Node **pp;
    
    bool swapped = (root != NULL);
    while (swapped)
    {
        // reset swap state
        swapped = false;

        pp = &root;
        while (*pp && (*pp)->next)
        {
            // compare the two node values
            if ((*pp)->next->value < (*pp)->value)
            {
                Node *p = *pp;
                *pp = (*pp)->next;
                p->next = (*pp)->next;
                (*pp)->next = p;
                swapped = true;
            } 
            pp = &(*pp)->next;
        }

        // pp holds the address of the pointer pointing to 
        //  the last node in the source list. So, we...
        //  1. prune off the end node.
        //  2. terminate the source list
        //  3. push the pruned node on to the front of
        //     the result list where it belongs.
        Node *p = *pp;
        *pp = NULL;

        p->next = result;
        result = p;

        // TODO: fun thing here. print both lists (result and root)
    }

    // the above loop could have exited early, leaving root
    //  holding the sorted low half of the list. the *last*
    //  pointer in that list is addressed by pp, so we can 
    //  just link the rest of the list we already pruned to
    //  that end and we're done.
    *pp = result;
    return root;
}

The change in main is likewise below:

int main(void)
{
    Node *root = insert(root, 4);
    insert(root, 1);
    insert(root, 5);
    insert(root, 3);

    root = bubbleSort(root);
    print(root);
    return 0;
}

And finally, the result:

1 3 4 5

Worth noting: bubble-sort is already dreadful enough. It is a terrible fit for nearly all sorting purposes, and especially for linked lists, where the ideal sorting mechanic would be merge-sort. But for academic purposes it makes for an interesting exercise, especially if you embrace the challenge of doing it exclusively with pointer jostling; not datum swapping.

An Interesting View

Modifying the code to do the following:

Generate a random shuffle of the sequence 1...30
Do the sort as shown above, but print the source and result lists after each iteration.

the results show how the pruning, pushing, and final fix up happen. The original shuffled list is:

11 28 16 6 12 23 13 1 20 14 27 3 2 7 21 4 8 30 19 15 22 17 26 29 24 9

Printing each list (the remaining source list and the result we're building), the outcome looks like this:

root:   11 16 6 12 23 13 1 20 14 27 3 2 7 21 4 8 28 19 15 22 17 26 29 24 9 5 18 25 10 
result: 30 
root:   11 6 12 16 13 1 20 14 23 3 2 7 21 4 8 27 19 15 22 17 26 28 24 9 5 18 25 10 
result: 29 30 
root:   6 11 12 13 1 16 14 20 3 2 7 21 4 8 23 19 15 22 17 26 27 24 9 5 18 25 10 
result: 28 29 30 
root:   6 11 12 1 13 14 16 3 2 7 20 4 8 21 19 15 22 17 23 26 24 9 5 18 25 10 
result: 27 28 29 30 
root:   6 11 1 12 13 14 3 2 7 16 4 8 20 19 15 21 17 22 23 24 9 5 18 25 10 
result: 26 27 28 29 30 
root:   6 1 11 12 13 3 2 7 14 4 8 16 19 15 20 17 21 22 23 9 5 18 24 10 
result: 25 26 27 28 29 30 
root:   1 6 11 12 3 2 7 13 4 8 14 16 15 19 17 20 21 22 9 5 18 23 10 
result: 24 25 26 27 28 29 30 
root:   1 6 11 3 2 7 12 4 8 13 14 15 16 17 19 20 21 9 5 18 22 10 
result: 23 24 25 26 27 28 29 30 
root:   1 6 3 2 7 11 4 8 12 13 14 15 16 17 19 20 9 5 18 21 10 
result: 22 23 24 25 26 27 28 29 30 
root:   1 3 2 6 7 4 8 11 12 13 14 15 16 17 19 9 5 18 20 10 
result: 21 22 23 24 25 26 27 28 29 30 
root:   1 2 3 6 4 7 8 11 12 13 14 15 16 17 9 5 18 19 10 
result: 20 21 22 23 24 25 26 27 28 29 30 
root:   1 2 3 4 6 7 8 11 12 13 14 15 16 9 5 17 18 10 
result: 19 20 21 22 23 24 25 26 27 28 29 30 
root:   1 2 3 4 6 7 8 11 12 13 14 15 9 5 16 17 10 
result: 18 19 20 21 22 23 24 25 26 27 28 29 30 
root:   1 2 3 4 6 7 8 11 12 13 14 9 5 15 16 10 
result: 17 18 19 20 21 22 23 24 25 26 27 28 29 30 
root:   1 2 3 4 6 7 8 11 12 13 9 5 14 15 10 
result: 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 
root:   1 2 3 4 6 7 8 11 12 9 5 13 14 10 
result: 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 
root:   1 2 3 4 6 7 8 11 9 5 12 13 10 
result: 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 
root:   1 2 3 4 6 7 8 9 5 11 12 10 
result: 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 
root:   1 2 3 4 6 7 8 5 9 11 10 
result: 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 
root:   1 2 3 4 6 7 5 8 9 10 
result: 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 
root:   1 2 3 4 6 5 7 8 9 
result: 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 
root:   1 2 3 4 5 6 7 8 
result: 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 
root:   1 2 3 4 5 6 7 
result: 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

The final result is as expected:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

CodePudding user response：

Change your inner while loop to this:

    while (trav != NULL && trav->next != NULL) {
      if (trav->value > trav->next->value) {
        printf("Swapping values %d %d\n", trav->value, trav->next->value);
        swap(trav, trav->next);        
        toSwap = true;
      }
    
      trav = trav->next;
    }

It corrects the NULL pointer dereferencement.
You'll see why it doesn't work by clearly showing what is being swapped.

That being said, you should rather do what is mentioned in the second comment.