Sorting a linked list

Sorting a linked list

While working on something (you’ll see on a later post), and since not being an experienced programmer, I faced this question, ‘how do I sort a linked list?’. I wasn’t in the mood to develop the algorithm from scratch so I started to look on the internet if there was any already written one, found some, but many of them instead of actually sorting the nodes in the list they exchanged some values within nodes given a certain condition. That’s just wrong, the beauty (and the challenge) in sorting a linked list, it is not exchanging values within nodes, but handling pointers in order to exchange the nodes themselves.So, being that I was not able to find any decent algorithm that decided to write it by my self and share it in case some else requires to do the same. It is very likely that you find it can be optimized, if so, I would be really thankful if you want to share your thoughts.

About how does the algorithm work, basically I have identified 4 cases that must be taken into account in order to successfully sort a linked list, each of these cases a different set of steps must be executed:

  • Case 1: Exchanging the first node with the consecutive node within the list.
  • Case 2: Exchanging the first node with a non consecutive node within the list.
  • Case 3: Exchanging a node (not the first) with the consecutive one in the list.
  • Case 4: Exchanging a node (not the first) with another one in the list not being consecutives.

The approach I have used is the Selection sort, using 3 auxiliary pointers, 2 to keep track of previous nodes (prev, prev2, will understand later), and ‘temp’ for pivoting nodes.

The node structure

Just a simple structure self referenced, and a data type definition of a pointer to the structure data type.

typedef struct snode{
int value;
struct snode *next;
} tnode;

typedef tnode * tpnode;

The code

void sort(tpnode *root)
{
//Pointers used to control ‘current’ (first looper, slower)
    tpnode current,prev=NULL;
//Pointers used to control ‘compared’ (second looper, faster)
    tpnode compared,prev2=NULL;
//Temp pointers
    tpnode temp;
current=*root;

while(current!=NULL)
{
compared=current->next;
while(compared!=NULL)
{
if(current->value>compared->value)
{
if(current==*root)
{
if(compared==current->next)
{
//CASE 1: Replacing the first node with the next node in the list
                        current->next=compared->next;
temp=current;
current=compared;
compared->next=temp;
*root=compared;
}
else
{
//CASE 2: Replacing the first node with a non consecutive node within the list
                        temp=current->next;
current->next=compared->next;
prev2->next=current;
compared->next=temp;
current=compared;
*root=compared;
}
}
else
{
if(current->next==compared)
{
//CASE 3: Replacing consecutive nodes
                        prev->next=compared;
current->next=compared->next;
compared->next=current;
current=prev->next;
}
else
{
//CASE 4: Replacing non consecutive nodes
                        prev->next=compared;
prev2->next=current;
temp=compared->next;
compared->next=current->next;
current->next=temp;
current=compared;
}
}
}
prev2=compared;
compared=compared->next;
}
prev=current;
current=current->next;
}
}


Hope you find this useful!!

Hernán J. Larrea

Leave a Reply

Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.