CODEWITHSUNDEEP
c++sortinglinked-listinsertion-sort
Max
Max

Reputation: 3

Insertion sort linked list c++

I'm trying to sort a filled linked list with random numbers. The function I have made doesnt work as it should. I can't see what is wrong, its not sorting the numbers properly. 

void linked_list::SortList()
{
   if(is_empty())
   {
      return;
   }
   for(node_t *it =head; it!=tail; it = it->next)
   {
      int valToIns = it->value;
      node_t *holePos = it;
      while(holePos->prev && valToIns < it->prev->value)
      {
         holePos->value = holePos->prev->value;
         holePos = holePos->prev;
      }
      holePos->value = valToIns;
   }
}

Upvotes: 0

Views: 4503

Answers (1)

Daniel Fischer
Daniel Fischer

Reputation: 183888

You're comparing with the wrong element,

while(holePos->prev && valToIns < it->prev->value)

should be

while(holePos->prev && valToIns < holePos->prev->value)

in order to compare valToIns with the value before the one holePos points to.

Upvotes: 1

Related Questions