I've been trying to create a selection sort function to sort a linked list in ascending order by swapping pointers only, rather than the data/contents of the nodes since I think if there is a lot of data in each node, then it would require a large amount of temporary memories for swapping data.
The problem is that there is something wrong with my logic of swapping that I could not figure out. I still have some test cases that after swapping, the linked lists' nodes are lost since the pointers couldn't connect them together.
My logic is that there should be 2 main cases:
Case 1) When the two nodes are adjacent (next to each other)
Case 2) When the two nodes are afar (not adjacent)
I have to deal with the first node (head); thus, there should be 4 cases = (2 for head or non-head) x (2 for adjacent or afar)
These are the two classes that construct my linked list
template <class T>
class ListNode
{
public:
T value;
ListNode<T> *next;
ListNode(T val)
{
value=val;
next=nullptr;
}
};
template <class T>
class Class_LinkedList
{
private:
ListNode<T> *head;
public:
/*****constructors + functions*****/
void sort() {;}
}
This is the sorting function that I'm having troubles with
void sort()
{
/*******There are four cases for swapping********
Case 1: First node (head) and Minimum Node are not adjacent
Case 2: First node (head) and Minimum Node are adjacent
(Case 3 and 4 are for non-head)
Case 3: The two nodes are not adjacent
Case 4: The two nodes are adjacent */
if (head==nullptr)
return;
ListNode<T> * pre_startPtr = nullptr; //points to the node before the starting node (selection sort)
ListNode<T> * pre_nodePtr = nullptr; //temporary pointer that points to the node before the temporary node for traversing
ListNode<T> * pre_minNodePtr=nullptr; //points to the node before the minimum node
//the prefix pre_ indicates these pointers point to previous nodes
/********Dealing with head/the first node*********
* Traverse once through the list to find the minimum node and swap it with the first node
**********************************/
pre_minNodePtr=head;
pre_nodePtr=head;
while (pre_nodePtr->next!=nullptr)
{
if (pre_minNodePtr->next->value > pre_nodePtr->next->value)
{
pre_minNodePtr=pre_nodePtr;
}
pre_nodePtr=pre_nodePtr->next;
}
if (pre_minNodePtr->next->value < head->value) //if there is a value less than head value, then swap
{
//Case 1: First node (head) and Minimum Node are not adjacent
if (head!=pre_minNodePtr)
{
ListNode <T> * temp;
temp=head;
head=pre_minNodePtr->next;
pre_minNodePtr->next=head;
temp=head->next;
head->next=pre_minNodePtr->next->next;
pre_minNodePtr->next->next=temp;
}
//Case 2: First node (head) and Minimum Node are adjacent
else //if (head==pre_minNodePtr)
{
head=pre_minNodePtr->next;
pre_minNodePtr->next=head->next;
head->next=pre_minNodePtr;
}
}
/************Dealing with the list after the first node**************/
pre_startPtr=head; //starting node = the second node (the node after head)
while (pre_startPtr->next!=nullptr)
{
pre_minNodePtr=pre_startPtr;
pre_nodePtr=pre_startPtr->next;
while (pre_nodePtr->next!=nullptr)
{
if (pre_minNodePtr->next->value > pre_nodePtr->next->value)
{
pre_minNodePtr=pre_nodePtr;
}
pre_nodePtr=pre_nodePtr->next;
}
//swap nodes if there is a value less than that of the starting node
if (pre_minNodePtr->next->value < pre_startPtr->next->value)
{
//Case 3: The two nodes are not adjacent
if (pre_startPtr->next!=pre_minNodePtr)
{
ListNode<T> * temp;
temp = pre_startPtr->next;
pre_startPtr->next=pre_minNodePtr->next;
pre_minNodePtr->next=temp;
temp = pre_startPtr->next->next;
pre_startPtr->next->next = pre_minNodePtr->next->next;
pre_minNodePtr->next->next = temp;
}
//Case 4: The two nodes are adjacent
else //if (pre_startPtr->next==pre_minNodePtr)
{
pre_startPtr->next=pre_minNodePtr->next;
pre_minNodePtr->next=pre_startPtr->next->next;
pre_startPtr->next->next=pre_minNodePtr;
}
}
//starting node = the next node
pre_startPtr=pre_startPtr->next;
}
}
selecSortor the likes, and should Ideally take the linked list as an argument. Please change your naming convention too (Class_LinkedList) is really not welcome in cpp land :)