1. This site uses cookies. By continuing to use this site, you are agreeing to our use of cookies. Learn More.

Sort Linked List

Discussion in 'C++' started by shabbir, Jun 7, 2007.

  1. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,287
    Likes Received:
    364
    Trophy Points:
    83
    Sort the content of a linked list.

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

    Code:
    #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();
    	
    }
     
  2. Shishir191

    Shishir191 New Member

    Joined:
    Jul 24, 2007
    Messages:
    27
    Likes Received:
    1
    Trophy Points:
    0
    Occupation:
    Software Engineer
    Location:
    Delhi
    Hi,
    The code you have written is good but according to me the sorting function should be small, its too complex.
     
  3. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,287
    Likes Received:
    364
    Trophy Points:
    83
    I am sure if we try we will have something better and shorter.
     
  4. seeguna

    seeguna New Member

    Joined:
    Jun 20, 2007
    Messages:
    31
    Likes Received:
    0
    Trophy Points:
    0
    Occupation:
    Technical Consultant
    Location:
    Chennai
    Re: Sort Linked List(Simple coding for sorting)

    Code:
    #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;
    	}
    }
     
    Last edited by a moderator: Jul 31, 2007
  5. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,287
    Likes Received:
    364
    Trophy Points:
    83
    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.
     
  6. Shishir191

    Shishir191 New Member

    Joined:
    Jul 24, 2007
    Messages:
    27
    Likes Received:
    1
    Trophy Points:
    0
    Occupation:
    Software Engineer
    Location:
    Delhi
    Hi Shabbir,

    I think it is much better than pervious one.
     
  7. seeguna

    seeguna New Member

    Joined:
    Jun 20, 2007
    Messages:
    31
    Likes Received:
    0
    Trophy Points:
    0
    Occupation:
    Technical Consultant
    Location:
    Chennai
    Thanks shabbir
     
  8. davy876

    davy876 New Member

    Joined:
    Mar 8, 2010
    Messages:
    4
    Likes Received:
    0
    Trophy Points:
    0
    Re: Sort Linked List(Simple coding for sorting)

    what kind of sorting method is used is it a buble sort ?
     
  9. maryam-90

    maryam-90 New Member

    Joined:
    Oct 25, 2010
    Messages:
    2
    Likes Received:
    0
    Trophy Points:
    0
    Occupation:
    student<comp. eng.>
    Location:
    jordan
    its a good code
    but how we can sort and creat a linked list of charectars?????
     
  10. msdnguide

    msdnguide New Member

    Joined:
    May 14, 2011
    Messages:
    13
    Likes Received:
    0
    Trophy Points:
    0
    Occupation:
    msdnguide
    Location:
    Delhi
    Home Page:
    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
     
  11. cnoobprogrammer

    cnoobprogrammer New Member

    Joined:
    Mar 29, 2012
    Messages:
    4
    Likes Received:
    0
    Trophy Points:
    0
    Re: Sort Linked List(Simple coding for sorting)

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

    Appreciate your help!:)
     
  12. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,287
    Likes Received:
    364
    Trophy Points:
    83
    Re: Sort Linked List(Simple coding for sorting)

    Have you tried any sorting algorithms?
     
  13. cnoobprogrammer

    cnoobprogrammer New Member

    Joined:
    Mar 29, 2012
    Messages:
    4
    Likes Received:
    0
    Trophy Points:
    0
    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.
     
  14. cnoobprogrammer

    cnoobprogrammer New Member

    Joined:
    Mar 29, 2012
    Messages:
    4
    Likes Received:
    0
    Trophy Points:
    0
    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!:)
     

Share This Page