Go4Expert

Go4Expert (http://www.go4expert.com/)
-   C++ (http://www.go4expert.com/articles/cpp-tutorials/)
-   -   Sort Linked List (http://www.go4expert.com/articles/sort-linked-list-t4593/)

shabbir 7Jun2007 18:10

Sort Linked List
 
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.

Code: Cpp

#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 27Jul2007 12:22

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

shabbir 27Jul2007 18:08

Re: Sort Linked List
 
Quote:

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 31Jul2007 18:40

Re: Sort Linked List(Simple coding for sorting)
 
Code: Cpp

#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 31Jul2007 18:51

Re: Sort Linked List
 
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 31Jul2007 21:11

Re: Sort Linked List
 
Quote:

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 1Aug2007 07:52

Re: Sort Linked List
 
Thanks shabbir

davy876 24Mar2010 20:06

Re: Sort Linked List(Simple coding for sorting)
 
what kind of sorting method is used is it a buble sort ?

maryam-90 25Oct2010 22:22

Re: Sort Linked List
 
its a good code
but how we can sort and creat a linked list of charectars?????

msdnguide 27May2011 20:12

Re: Sort Linked List
 
In the same way as he has done for numbers. You just need to overload > operator if you are using C++. If you are using C, then write a function that does the string comparison and tells you the result. strcmp can be used


All times are GMT +5.5. The time now is 15:25.