How to implement bubble sort in C++?

Question

I have tried to implement bubble sort on singly linked list (by changing pointers). I am wondering what's wrong with this solution. It seems to be clear and should work, but I am beginner in C++, so I guess that I did somewhere mistake which I cannot spot. Here is code:

#include <iostream>
using namespace std;

struct node{
    int value;
    node *next = nullptr;
};

void print(node* n){
    while(n){
        cout<< n->value << " ";
        n = n->next;
    }
    cout << endl;
}

void replace(node*& first, node* second){
    node* tmp = second->next;
    second->next = first;
    first->next = tmp;
    first = second;
}

void bubbleSortRecu(node*& head, int length){
    if(!head || !head->next || length == 1) return;
    node* n = head;
    int counter = length - 1;
    while(n->next && counter){
        if(n->value > n->next->value)
            // std::swap(n->value, n->next->value); // swaping values works fine
            replace(n, n->next);
        n = n->next;
        counter --;
    }
    bubbleSortRecu(head, --length);
}

int main(){

    node* list = new node{4};
    list->next = new node{3};
    list->next->next = new node{5};
    list->next->next->next = new node{1};
    list->next->next->next->next = new node{0};

    cout << "Original: ";
    print(list);

    cout << "Replaced: ";
    replace(list, list->next);
    replace(list->next->next->next, list->next->next->next->next);
    print(list);

    bubbleSortRecu(list, 5);
    cout << "After bubblesort: ";
    print(list);

    return 0;
}

I have tested replace function on first two and last two elements of list. It worked. After calling bubbleSortRecu(list, 5) my list is broken. Here is output:

Original: 4 3 5 1 0 
Replaced: 3 4 5 0 1 
After bubblesort: 3 4 5

Could you explain me please how to fix it and where am I doing mistake?

Or indeed, if you don't want to use a debugger, the absolutely classic "shove a print statement on every line to say what the previous line's result was and what the next line will do" should work too. — Patrick Stevens, Jun 07 '20 at 17:57
I wasn't using debugger. I tried to use `cout`s, but I couldn't find that mistake. Maybe I did not enough printing. I will try to place them after each line and see if it can help me. Thank you for advice. — Ethr, Jun 07 '20 at 18:01
If the cout method did not help it may be time to obtain a debugger like the one in Visual Studio that you can step through your code 1 line at a time looking at the variables and flow at each step to understand why your algorithm is not doing what you expect. — drescherjm, Jun 07 '20 at 19:36
It would be easier to help you if you provided a working example — Damien, Jun 08 '20 at 08:28
@Ethr To be fair, the advice to use print statements is pretty bad advice. You're basically expending a lot of manual effort to replicate what the debugger already does automatically and with more control. Instead, invest the time to learn how to use your debugger (which shouldn't take long). — JBentley, Jun 08 '20 at 11:09
@JBentley Thank you for advice. I spend some time to run debbuger, but I have some troubles with launching it. I was mostly programming in Python before, so my IDE choice was stright - Pycharm. Now, starting my journey with C++ brought me to Visual Studio Code. I have installed extension "Code runner" to compile my programs, but when I try to use standard menu -> run -> Start debugging or Run without debugging it throws a lot of errors which I try to fix at the moment. — Ethr, Jun 08 '20 at 11:19

Damien · Accepted Answer · 2020-06-09T07:26:31.250

1

In practice, you don't swap the nodes, only the pointers to the next nodes.

In particular, you don't modify the pointers that were pointing to the nodes that you try to swap.

For example, if

a -> b -> c -> d

and you want to swap b and c, then a should point to c now, not to b. Moreover, cshould point to b, etc.

Therefore, intead of obtaining

a -> c -> b -> d

with your method, you get:

a -> b -> d
c -> c

Therefore, the chain is broken.

A simple workaround is simply to swap the value inside the nodes, without modifying the pointers.

void replace(node* first, node* second){
    std::swap (first->value, second->value);
}

edited Jun 09 '20 at 07:26

answered Jun 08 '20 at 15:18

Damien

4,809
4
15
20

I still don't get why replace called like this `replace(list, list->next);` in main works fine, but when it is called inside function `bubbleSortRecu` it is not. I don't want to change values. `std::swap` is commented out in my code just to show that my function works (when `replace` is not used inside). – Ethr Jun 08 '20 at 23:05
I did not notice that the swap solution on values was in comment. I tried to detail in the post why your method cannot work. – Damien Jun 09 '20 at 07:27

How to implement bubble sort in C++?

1 Answers1