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?

Answer 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);
}