0

So this is the thing, I need to implement the bubble sort algorithm on linked lists. Yes, I saw many answers written in Stack Overflow that addresses this question. Almost all of them are implemented using pointers-to-pointers. Here, I tried to implement this using a referenced pointer rather than double pointers. I've spent more than a day to figure out what's wrong with my code.

My implementation of the bubble-sort and swap functions are as follows:

struct node
{
    int data;
    node* next;
    node(int x)
    {
        data = x;
        next = NULL;
    }
};

node* swap(node *a, node *b){
    node* temp = b->next;
    b->next = a;
    a->next = temp;
    return b;
}

void bubbleSort(node*& head) {
    node* ptr = head;
    node* last = NULL;
    int swapped;
    do
    {
        swapped = 0;
        ptr = head;

        while (ptr->next != last)
        {
            if (ptr->data > ptr->next->data)
            {
                if (ptr == head)
                {
                    head = swap(ptr, ptr->next);
                    swapped = 1;
                }

                else{
                    ptr = swap(ptr, ptr->next);
                    swapped = 1;
                }
                
            }

            ptr = ptr->next;
            
        }
        
    } while (swapped);
    
}

The output for the above code (which is wrong) is as follows:

The original list = 
2 -> 1 -> 4 -> 3 -> 6 -> 5 -> 

The Sorted list = 
1 -> 2 -> 4 -> 6 ->

I know this is some basics for most of you. But please I would be very grateful if you can take some of your time to see what's wrong with this code.

Isn't the fact that I've used referenced pointers fulfill the same things that will be done by double-pointers. For example, this bubble-sort implementation is done using double-pointers?

Improve this question
6
  • Why are you passing pointers-by-reference into bubbleSort? Commented Feb 6, 2021 at 4:36
  • This code is written in a very C-style as opposed to being idiomatic C++. Is there a reason you're not using smart-pointers and modern (C++11-and-later) features like nullptr? Commented Feb 6, 2021 at 4:37
  • Because in case there's any change to 'head', it will be reflected inside the main method too. Commented Feb 6, 2021 at 4:38
  • No specific reason for not using smart pointers Commented Feb 6, 2021 at 4:39
  • If I don't use node* & , then I will have to use double-pointers right? Commented Feb 6, 2021 at 4:40

1 Answer 1

Reset to default
1

Swapping is a bit special for lists. Swapping 2 consecutive nodes involves touching 4 nodes, the 2 swapped nodes, and the nodes preceding them. That's why the length of the list output from your sort() was not the same length as its input.

Taking this in consideration, the swap operation then becomes:

void swap_nodes(Node* a_pred, Node*& a, Node* b_pred, Node*& b)
{
    assert(a != nullptr && b != nullptr && b_pred != nullptr);
    assert(!a_pred || a_pred->next == a);
    assert(b_pred->next == b); 

    if (a == b)
        return;

    b_pred->next = a;
    if (a_pred)
        a_pred->next = b;

    Node* t = a->next;
    a->next = b->next;
    b->next = t;

    t = a;
    a = b;
    b = t;
}

Also, you cannot escape early by testing if no swap has occured in the inner loop. This test only tells you that the current outer loop node is the smallest until the end, not that the range is fully sorted.

Keeping track of the nodes preceding the ones being tested is imprtant, since not doing so would mean having to find these predecessors by looping through the list again.

The sort function then becomes:

void sort(Node*& head)
{
    for (Node* a = head, *a_pred = nullptr; a != nullptr; a_pred = a, a = a->next)
    {
        for (Node* b = a->next, *b_pred = a; b != nullptr; b_pred = b, b = b->next)
        {
            if (b->data < a->data)
            {
               swap_nodes(a_pred, a, b_pred, b);
               if (a_pred == nullptr)
                   head = a;              
            } 
        }
    }
}

If you want to optimize a bit, you cannot reduce the amount of comparisons, but you can reduce the amount of swaps, you can try this:

void sort(Node*& head)
{
    for (Node* a = head, *a_pred = nullptr; a != nullptr; a_pred = a, a = a->next)
    {
        // find smallest node value in [a, end)
        Node* small_pred = a_pred;
        Node* small = a;
        for (Node* b = a->next, *b_pred = a; b != nullptr; b_pred = b, b = b->next)
        {
            if (b->data < small->data)
            {
               small_pred = b_pred;
               small = b;
            }
        }

        if (small != a)
        {
           // remove smallest from list.
           small_pred->next = small->next;

           // insert smallest before a.
           small->next = a;
           if (a_pred == nullptr)       // same as a == head
               head = small;
           else 
               a_pred->next = small;

           // keep outer loop happy, by making it look like a swap.
           a = small;
        } 
        // node a is now the smallest node in range [a, end)
        // move on to the next.
    }
}

[EDIT]

The bubble sort above is the one used in the industry. The "pedantic" bubble sort, which for some unknown reason is still being taught is here:

void pedantic_bubble_sort(Node*& head) {
  for (Node* sentinel = nullptr; sentinel != head;) {
    bool swaps = false;

    for (Node *pred = nullptr, *a = head, *b = a->next; a && b;
         pred = a, a = b, b = b->next) {
      if (b->data < a->data) {
        swap_nodes(pred, a, a, b);
        if (!pred) head = a;
        swaps = true;
      }
      if (b->next == sentinel) {
        sentinel = b;
        break;
      }
    }

    if (!swaps) break;
  }
}

imho, this algorithm is cleverly slow.

You can tinker with it here, and compare performance with other algorithms and std::list::sort(): https://godbolt.org/z/Yco8WY

Improve this answer
Sign up to request clarification or add additional context in comments.

11 Comments

@S.Tiss Fixed, sorry for the typos.
std::swap(a->next, b->next); std::swap(a, b) instead of doing it longhand?
Your change isn't a bubble sort. Bubble sort only ever swaps adjacent elements
It is an optimization, as advertized. If you read carefully my post, you will see there are BOTH the original algorithm AND the optimized version.
@Caleth I'll add that it is a very common optimization. I invite you to follow the link to godbolt and see that gains in performance this simple mod brings are quite impressive. That's why I've been using it for years.
|

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.