Sort Linked List

ADVERTISEMENT

Author

shabbir ( Go4Expert Founder )

Shabbir is a developer in the field of Applications, web as well as database designing and is devoted to the optimization and usability of the code. He maintains Programming forum and is a C++ addict.

All articles By shabbir

Recent Articles

• All about Arrays in C/C++ - Part II, Started by Mridula in C-C++
• All about Arrays in C/C++ - Part I, Started by Mridula in C-C++
• About size_t and ptrdiff_t, Started by Karpov2007 in C-C++
• What is down-casting and how to make it safe?, Started by d_arin100 in C-C++
• The concept behind the “upcast”., Started by d_arin100 in C-C++

Similar Articles

• Huffman Encoding in C (Minimum Variance Encoding), Started by rai_gandalf in C-C++
• Basic operations in Linked List, Started by shabbir in C-C++
• Doubly Linked List Implementation in C#, Started by Sanskruti in C#

After having so many articles on Linked List

Basic operations in Linked List
Swap two nodes of a linked list
Move forward a node in linked list
Insert a node in a linked list
Double linked list
Double circular linked list
Circular linked list
Priority Queue implementation using Linked List
Queue implementation through linked list

I thought why not also have the one which sorts the linked list as well. I did not submit it because I thought the above list is sufficient for sorting as well but because of lots of query regarding the same I thought lets have it online as well.

Note: I had a major bug pointed out by RiOrius and is rectified now. Thanks for letting me know about it.

#include <iostream>
using namespace std;

#define NULL 0

class LinkList 
{
private:
    struct Node 
    {
        Node* prev;
        int value; 
        Node *next;
    };
    Node *first;
    
public :
    
    LinkList()
    {
        Node *t1 = new Node();
        t1->prev = NULL;
        t1->value = 4;
        t1->next = NULL;
        first = t1;
        
        Node *t2 = new Node();
        t2->prev = t1;
        t2->value = 6;
        t2->next = NULL;
        t1->next = t2;
        
        Node *t3 = new Node();
        t3->prev = t2;
        t3->value = 1;
        t3->next = NULL;
        t2->next = t3;
        
        Node *t4 = new Node();
        t4->prev = t3;
        t4->value = 5;
        t4->next = NULL;
        t3->next = t4;

        Node *t5 = new Node();
        t5->prev = t4;
        t5->value = 8;
        t5->next = NULL;
        t4->next = t5;

        Node *t6 = new Node();
        t6->prev = t5;
        t6->value = 1;
        t6->next = NULL;
        t5->next = t6;

        Node *t7 = new Node();
        t7->prev = t6;
        t7->value = 0;
        t7->next = NULL;
        t6->next = t7;
    }
    
    ~LinkList() 
    { 
        Node *temp = first, *current = first;
        while(current != NULL)
        {
            temp = current->next;
            delete current;
            current = temp;
        }
        
    }
    
    void Display()
    {
        Node *temp;
        for(temp = first; temp != NULL; temp = temp->next)
        {
            cout<<temp->value<<" , ";
        }
        cout<<endl;
    }
    
    
    void Sort()
    {
        Node *current, *cur;

        for(current = first; current->next != NULL; current = current->next)
        {
            Node *minimum = current;
            for(cur = current ; cur != NULL; cur = cur->next)
            {
                if(minimum->value > cur->value) 
                {
                    minimum = cur;
                }
            }
            if(minimum != current)
            {
                Node *current_previous, *current_next, *min_previous, *min_next;

                // Initialize them
                current_next = current->next;
                min_previous = minimum->prev;
                min_next = minimum->next;
                current_previous = current->prev;

                if(current_previous == NULL)
                {
                    // Change the First Node
                    first = minimum;
                }
                if(current->next == minimum)
                {
                    // Nodes are Adjacent
                    minimum->prev = current_previous;
                    minimum->next = current;

                    current->prev = minimum;
                    current->next = min_next;

                    if(min_next)
                    {
                        min_next->prev = current;
                    }
                    if(current_previous)
                    {
                        current_previous->next = minimum;
                    }
                }
                else
                {
                    minimum->prev = current_previous;
                    minimum->next = current_next;

                    current->prev = min_previous;
                    current->next = min_next;

                    if(current_next)
                    {
                        current_next->prev = minimum;
                    }
                    if(min_previous)
                    {
                        min_previous->next = current;
                    }
                    if(min_next)
                    {
                        min_next->prev = current;
                    }
                    if(current_previous)
                    {
                        current_previous->next = minimum;
                    }
                }
                current = minimum;
            }
        }

    }
};

void main()
{
    LinkList list;
    
    cout<<"LinkList = ";
    
    list.Display();
    
    cout<<"\n\nSorting \n\n";
    
    list.Sort();
    
    cout<<"LinkList = ";
    
    list.Display();
    
}

[Shishir191]

Hi,
The code you have written is good but according to me the sorting function should be small, its too complex.

[shabbir]

Originally Posted by Shishir191

Hi,
The code you have written is good but according to me the sorting function should be small, its too complex.

I am sure if we try we will have something better and shorter.

[seeguna]

#include<stdio.h>
#include<stdlib.h>
void create();
void show();
void sort();
struct node
{
    int d;
    struct node *link;
}*head=0,*current,*prev;
int num_nodes=0;
void main()
{
    int choice;
    while(1)
    {
        printf("\n1.Create\n2.Display\n3.Sort\n4.Exit\n");
        printf("Enter ur choice:");
        scanf("%d",&choice);
        switch(choice)
        {
        case 1:
            create();
            break;
        case 2:
            show();
            break;
        case 3:
            sort();
            break;
        case 4:
            exit(0);
        }
    }
}
void create()
{
    int data;
    current=(struct node*)malloc(sizeof(struct node));
    printf("Enter the data:");
    scanf("%d",&data);
    num_nodes++;
    if(head==0)
    {
        head=current;
        current->d=data;
        current->link=NULL;
        prev=current;
        
    }
    else{
        current->d=data;
        current->link=NULL;
        prev->link=current;
        prev=current;
    }
}
void show()
{
    current=head;
    while(current!=NULL)
    {
        printf("->%d",current->d);
        current=current->link;
    }
    
}
void sort()
{
    // current ptr is used to point the current node in the list
    //prev ptr is used to point the previous node of current node
    //next ptr is used to point the next node of current node
    int i,j;
    struct node *prev=0,*next=0;
    //Initially current node and previous node should be the same(first) node in the list
    current=head;
    prev=head;
    next=head->link;
    for(i=0;i<num_nodes-1;i++)
    {
        for(j=0;j<num_nodes-i-1;j++)
        {
            if(current->d>next->d)
            {
                current->link=next->link;
                next->link=current;
                if(current==head)
                {
                    head=next;prev=next;
                }
                else
                {
                    prev->link=next;prev=next;
                }
                if(next!=NULL)//check whether final node is reached 
                    next=current->link;
                
            }
            else//just moved each node ptr by one position
            {
                prev=current;
                current=next;
                next=current->link;
            }
            
        }
        //For next iteration make the initial settings again
        current=head;
        prev=head;
        next=current->link;
    }
    
    //For display the sorted numbers
    current=head;
    while(current!=NULL)
    {
        printf("->%d",current->d);
        current=current->link;
    }
}

[shabbir]

Thats a good one. Yours is a Linear sort and I have used bubble sort but I am sure with bubble sort also some code blocks can be made shorter.

[Shishir191]

Originally Posted by shabbir

Thats a good one. Yours is a Linear sort and I have used bubble sort but I am sure with bubble sort also some code blocks can be made shorter.

Hi Shabbir,

I think it is much better than pervious one.

[seeguna]

Thanks shabbir