Sorting linked list with bubble sort in c++

Question

I have been trying to bubble sort a doubly linked list using swap function. My question is does the swap function swap the pointer, and not just the data? My code shows me it only swap the data but not the pointers. Is there any way to efficiently to swap the pointers on the linked list? Please show me the code as I am very inexperienced in coding and I do not understand other codes in other answer.

void sortPoly(PolyNode* a)
{
  PolyNode* head =a;
  PolyNode* current = head;
  PolyNode* current_next = current->next;


  int len =Polylength(current);

  if(len ==1 || len ==0)
   {
      return;
   }

for(int i =0; i < len; i++)
{
    for (int j =0; j< len -i; j++)
    {
        int sum = current->expx + current->expy;
        cout << "sum=" << sum << endl;
        int next_sum = current_next->expx + current_next->expy;
         cout << "\t nextsum=" << next_sum << endl;

        if( sum < next_sum)
        {
            cout << "current=" << current->coef << "expx = " << current->expx << "expy=" << current->expy << endl;
            cout << "current_next=" << current_next->coef << "expx = " << current_next->expx << "expy=" << current_next->expy << endl;

            std:: swap(current, current_next);
            cout << endl;
            cout << "swapped" << endl;

            cout << "current=" << current->coef << "expx = " <<    current->expx << "expy=" << current->expy << endl;
            cout << "current_next=" << current_next->coef << "expx = " << current_next->expx << "expy=" << current_next->expy << endl;

           cout << "current=" << current->coef << "expx = " << current->expx << "expy=" << current->expy << endl;
           cout << "current_next=" << current_next->coef << "expx = " << current_next->expx << "expy=" << current_next->expy << endl;

        current = current->next;

        current_next = current->next->next;
        cout << "current=" << current->coef << "expx = " << current->expx << "expy=" << current->expy << endl;
        cout << "current_next=" << current_next->coef << "expx = " << current_next->expx << "expy=" << current_next->expy << endl;
    }
   }

 }

This is my struct:

    struct PolyNode
    {
      int coef;
      int expx;
      int expy;
      PolyNode* prev;
      PolyNode* next;
     };

Please find following my response on Mac terminal.

so you have your own list implementation? try to break the problem in smaller steps, you need somehow to compare 2 nodes and implement a function for swapping correctly 2 nodes (you can decide what to swap: data, or pointers, due to cache effect it is probably more efficient swapping data, but you can decide that detail) the final result would be a list that iterated give sorted elements. until you are not sure you have a correct "SWAP" and a correct "COMPARE" don't even try to do a sort — CoffeDeveloper
– CoffeDeveloper, Commented Oct 4, 2015 at 13:08

Adem · Accepted Answer · 2015-10-04 13:14:21Z

1

I think you probably have problems in swap function. I dont think std::swap can swap also prev and next reference. to be sure, you can implement your own swap. I would do this with this function.

void swap(PolyNode* node1, PolyNode* node2){
PolyNode* prev = node1->prev;
PolyNode* next = node2->next;
if (prev)
    prev->next = node2;
if (next)
    next->prev = node1;

node1->next = next;
node1->prev = node2;

node2->prev = prev;
node2->next = node1;
}

btw, you have to move iteration out of if.

current = current->next;
current_next = current->next->next;

part has to be out of if

answered Oct 4, 2015 at 13:14

Adem

9,4489 gold badges45 silver badges59 bronze badges

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

2 Comments

Kirsteen Ng Over a year ago

Thanks for the reply. Quick question, why the condition if(prev) and if(next)?

Adem Over a year ago

prev and next object can be out of array. I assume, you set NULL first object's prev, and last object's next

Collectives™ on Stack Overflow

Sorting linked list with bubble sort in c++

1 Answer 1

2 Comments

Your Answer

Collectives™ on Stack Overflow

Sorting linked list with bubble sort in c++

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related