Sorting a linked list in c++

Question

I'm getting mad with infinite loop, what do you think is suitable solution?

void sorting () {
  node * temphead = head;
  node * tempnode = NULL;

  for (int i=0; i<count; i++) {
    for (int j=0; j<count-i; j++) {
      if (temphead->data > temphead->next->data) {
        tempnode = temphead;
        temphead = temphead->next;
        temphead->next = tempnode;
      }

      temphead=temphead->next;
      count++;
    }
  }
}

I tried to increment count and use many conditions with while- before and after the for loop with no result

Richard · Accepted Answer · 2014-01-15 04:04:29Z

5

An easier way to slide through a linked list is like this:

for (node *current = head; current != nullptr; current = current->next) {
    // This will run through all of the nodes until we reach the end.
}

And to slide to the second to last item (ensuring that node->next exists) looks like this:

for (node *current = head; current->next != nullptr; current = current->next) {
    // Go through all of the nodes that have a 'next' node.
}

If you want to count how many items are in a linked list, you do something like this:

int count = 0;
for (node *current = head; current != nullptr; current = current->next) {
    count = count + 1;
}

So a selection type sort like you have above would look like this:

for (node *index = head; index->next != nullptr; index = index->next) {
  for (node *selection = index->next; selection != nullptr; selection = selection->next) {
    if (index->data > selection->data) {
      swap(index->data, selection->data);
    }
  }
}

Although sorting linked lists is generally not the best way to go (unless you're performing a merge).

edited Jan 15, 2014 at 4:04

Richard

62.7k40 gold badges198 silver badges277 bronze badges

answered Oct 3, 2013 at 21:11

sircodesalot

11.5k9 gold badges55 silver badges86 bronze badges

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

4 Comments

Nora Over a year ago

I got it and that's what I really need, but when I print that on screen still non-sorted :(. Thank you for advice.

sircodesalot Over a year ago

Hmm.. I did that from memory, I'll debug it and repost a working version shortly.

sircodesalot Over a year ago

Fixed. Rather than swapping the nodes themselves, I just swapped the data.

Nora Over a year ago

Oh! how I did not notice! I appreciate your help :)

Kaushik Sivakumar · Accepted Answer · 2013-10-03 21:11:22Z

2

the problem is you are looping till count and you are incrementing count in every run of the loop//remove line count++ to avoid remove infinite loop

answered Oct 3, 2013 at 21:11

Kaushik Sivakumar

2052 silver badges9 bronze badges

2 Comments

Slava Over a year ago

Looks like he wants to loop over list (by count) and count elements in the same loop :)

Kaushik Sivakumar Over a year ago

should have duplicate count variables like count1 then(or better rename as size and count),if you are trying to do like what @Slava says

Collectives™ on Stack Overflow

Sorting a linked list in c++

2 Answers 2

4 Comments

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

4 Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related