0

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;
        }
    }
3
  • 2
    First off, it's good that you are swapping pointers instead of data, because that is the ideal way to go about selection sort. Secondly, did you try using a debugger? If not, then this is a good time to learn how to use a debugger. Commented Apr 4, 2021 at 4:52
  • 1
    Also, usually, the selection sort function should be named aptly as selecSort or 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 :) Commented Apr 4, 2021 at 4:57
  • Thank you. I honestly don't know how to use a debugger; I'll watch youtube videos to know how to use it on Eclipse. Commented Apr 4, 2021 at 5:05

1 Answer 1

2

Solved. There is a mistake in my code that I didn't notice at first. It is when swapping pre_minNodePtr->next with head I assigned pre_minNodePtr->next with head instead of temp (temporary value of head since head has already changed).

Incorrect line:

pre_minNodePtr->next=head;

should be fixed to

pre_minNodePtr->next=temp;
Sign up to request clarification or add additional context in comments.

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.