Go4Expert (http://www.go4expert.com/)
-   C++ (http://www.go4expert.com/articles/cpp-tutorials/)

 shabbir 7Jun2007 18:10

After having so many articles on Linked List
Swap two nodes of a linked list
Move forward a node in linked list
Insert a node in a linked list
Priority Queue implementation using 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 0class 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

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

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

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

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

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

its a good code
but how we can sort and creat a linked list of charectars?????

 msdnguide 27May2011 20:12

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

 cnoobprogrammer 29Mar2012 15:17

Re: Sort Linked List(Simple coding for sorting)

Hi.
May I ask why do you use 2 for loop in this case?

 shabbir 29Mar2012 15:44

Re: Sort Linked List(Simple coding for sorting)

Quote:
 Originally Posted by cnoobprogrammer (Post 93835) Hi. Your code is nice. May I ask why do you use 2 for loop in this case? Appreciate your help!:)
Have you tried any sorting algorithms?

 cnoobprogrammer 29Mar2012 18:29

Re: Sort Linked List(Simple coding for sorting)

Ya, I try to check if this value referenced by the pointer is greater than the value referenced by another pointer. But it doesn't work.

 cnoobprogrammer 31Mar2012 13:51

Re: Sort Linked List(Simple coding for sorting)

Hi can i check with you, the reason for having 2 loop is it because you want to compare the first node with the second node and so on?

Thank you!:)

 All times are GMT +5.5. The time now is 07:37.