Linked List Selection Sort duplicating value

[mpjpgpnp]

This is for an assignment which involves using selection sort to sort a linked list.

The linked list nodes consist of another object, Person, and a next pointer. Person has 2 attributes-priority (int) and name (string). Priority is descending. _front is a pointer to the first node.

The issue I am running into is that the program is placing the 2nd to last element based on priority first. Aside from that it is sorting correctly, including listing that 2nd to last element in the correct order.

For example, if the data is 1 Smith, 2 Jones, 3 Roberts, 4 Doe, it prints as Jones, Doe, Roberts, Jones, Smith.

I would appreciate any guidance as to what I am doing incorrectly.

  void PQueue::enqueue(Person *person)
{	
        Node *curr = NULL; 
	Node *largest = NULL;
	Node *first = NULL;
	Node *tempnode = NULL;
	
	if (_front == NULL) 
	{
		_front = new Node(person, _front);
		_size++; //add to count
	}
	else 
	{	
		tempnode = _front; 
		tempnode->_next = new Node(person, tempnode->_next);
		_size++; //add to count
		
		first = _front;
		
		while(first->_next != NULL) //loop through linked list
		{
			curr = first->_next;
			largest = first;
			
			while (curr != NULL) 
			{
		if (largest->_person->_priority < curr->_person>_priority)
				{
					largest = curr;
				}
			
			curr = curr->_next;
			
			}			
			
			
			
		tempnode->_person->_priority = first->_person->_priority;
		tempnode->_person->_name = first->_person->_name;
		
		first->_person->_priority = largest->_person->_priority;
		first->_person->_name = largest->_person->_name;
						
		largest->_person->_priority = tempnode->_person->_priority;
		largest->_person->_name = tempnode->_person->_name;
			
		first = first->_next;
						
		}	
		
	}	
}

[coder777]

You cannot use the tempnode for swapping.

What you need to do is unlink the node in question and then link at the new position again. For the unlink you need to store the previous node if it is a singly linked list (as it appears to be).

The unlink is important because otherwise you will have duplicates.

[mpjpgpnp]

Thank you for the response.

I was trying to avoid swapping the pointers by swapping the data instead. Is that not a workable solution?

If it does require moving the pointers around is the following what I would need to update?

Add another pointer node (prev) that would point to the node before curr

Have a check to move prev along with curr if prev->_next != largest

After the inner loop is finished-

1. prev->_next would need to be updated to point to first (moving first to largest position)
2. first->_next would need to be updated to point to largest->-next (relinking _next for moved node)
3. first would need to be updated to point to largest & largest->_next to point to first->_next (moving largest to first position and relinking _next for moved node)

Thanks for any additional assistance.

[dhayden]

Normally when sorting a linked list, you adjust the pointers, not the data within the pointers, but in this case, since _person is itself a pointer, it's probably easier to just swap the pointers.

As coder777 pointed out, you can't use tempnode when swapping because you overwrite the old value. Instead, change lines 39-46 to

Person *tmp = first->_person;
first->_person = largest->_person;
largest->_person = tmp;

Or better yet, add #include <algorithm> to the front and do
std::swap(first->_person, largest->_person);

By the way, at lines 15 & 16 you make the new node the second one in the list. Why not make it the first?
_front = new Node(Person, _front);

[D80DSL3A]

I think that lines 15, 16 are causing trouble. They insert a new node after _front, but you don't yet know it goes there...

I also think you're complicating the task. I'm not sure but it looks like you're attempting to sort the entire list each time a node is added.
This isn't necessary. It is much easier to maintain the sorted list by inserting each node where it belongs in the already sorted list. Just find the Node to insert before and insert a new Node there.

To compare how much easier this is, here's some code I wrote recently for a queue. This addNode() function is for a queue with a first pointer setup in main(), not as a data member of any list class
and with an int (not a Person) as the data load. Also insertion is in ascending order:

void addNode( int x, node_type** ppNode )
{
    while( *ppNode && x > (*ppNode)->num )
        ppNode = &(*ppNode)->next;
    *ppNode = new node_type(x,*ppNode);
}

Adapting this to your case:

void PQueue::enqueue(Person *person)// instead of an int
{
    Node** ppNode = &_front;
    while( *ppNode && (person->_priority < (*ppNode)->_person->_priority) )
        ppNode = &(*ppNode)->next;
    *ppNode = new Node(person,*ppNode);
}

edit:
OK. Doing that using a Node** allows for quite compact code, but it's confusing.
gotta work the logic up from a Node* version. I found this works great:

void addNode( int x, node_type*& pNode )
{
    if( !pNode || x < pNode->num )// list is empty or new item belongs in front
        pNode = new node_type(x,pNode);// push_front
    else// x goes deeper in the list
    {
        node_type* it = pNode;
        while( it->next && x > it->next->num ) it = it->next;// find Node to insert after (it)
        it->next = new node_type(x,it->next);// insert after it
    }
}

Does that make better sense?
Adapting it is simple. The function is called by passing a pointer to first, eg addNode(5, first);. As such, pNode cannot reference any pointer other than first. References cannot be re bound. Just substitute _first for pNode everywhere.
This is the advantage in using a Node** as the iterator. We can change which Node* a Node** points to (unlike a Node*&). This allows us to use ppNode as the list iterator and leads to the code compaction.

edit2: Another way around being unable to rebind a Node*& is to pass a new reference in another function call, hence this recursive version:

void addNode_rec( int x, node_type*& pNode )
{
    if( pNode && x > pNode->num )
        return addNode_rec( x, pNode->next );// pass a reference to the next Node in the list
    pNode = new node_type(x,pNode);
}

[mpjpgpnp]

Thank you dhayden and fun2code.

I had seen the swap function under the list class but not algorithm-thanks for pointing that out.
It works brilliantly.

I may also try out switching the person pointers instead of the actual node pointers-I hadn't thought of that.

And, yes, it is sorting the list every time another node is added. It would probably make much more sense to do it your way, fun2code, or at least wait until all the elements are added (the data is being read from a file) but the assignment required that it be done with selection sort within the enqueue method.

Thanks again!!

[D80DSL3A]

You're welcome. I would double check on the requirement to perform a full list sort each time a single Node is added. That's quite senseless. You enqueue each Node where it belongs.