1. We have moved from vBulletin to XenForo and you are viewing the site in the middle of the move. Though the functional aspect of everything is working fine, we are still working on other changes including the new design on Xenforo.
    Dismiss Notice

Sort Linked List

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

  1. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,276
    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,276
    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,276
    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,276
    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