Thread: Sorting a Linked List

  1. #1
    Registered User
    Join Date
    Nov 2009
    Posts
    11

    Sorting a Linked List

    Hi I'm trying to sort a linked list I created using a function but I have no idea how to sort it. Can anyone help me?

    Here's my Code:

    Code:
    #include <iostream>                        
    #include <cstdlib>                         
    #include <cmath>
    #include <fstream>
    #include <string>
    #include <iomanip>
    
    using namespace std;
    
    struct Node{
        string parts;
        int ID;    
        int date;
        float price;
    
        Node *next;  
        
        Node(); 
    };
    
    Node::Node()
    {
        next=NULL; 
    }
    
    void Insert(Node *&Front,Node *&Rear, string n_parts, int date, int n_Id, float n_price, int count)
    {
        Node *n_Info = new Node();  
      
        n_Info->parts = n_parts;   
        n_Info->date = date;
        n_Info->price = n_price; 
        n_Info->ID = n_Id;
    
        if(count ==0)
        {        
            Front = Rear = n_Info;
        }
    
        else if(count > 0)
        {
            Rear->next = n_Info;     
            Rear = Rear -> next;
        }
        
        do
        {  
            if (n_Info == NULL)
            cout << "End of list" << endl;
            else
           {  
              cout<< n_Info->parts<<endl;
              cout<< n_Info->ID<<endl;
              cout<< n_Info->date<<endl;
              cout<< n_Info->price<<endl;
              cout << endl;
              
              n_Info = n_Info->next;
           }
      }
      while (n_Info != NULL);
    
    }
    
    void Flush(Node *&Front,Node *&Rear, int L_size)
    {
        Node *temp_node = Front;
    
        for(int i =0; i<L_size; i++)
        {
            Front = Front->next;
            delete temp_node;
            temp_node=Front;
        }
    
    }
    
    float Avg(float n_price)
    {
    	static float sum = 0, i = 0;
    	
    	sum += n_price;
    	i++;
    	return (sum/i);
    }
    
    float Highest(float n_price)
    {	
        static float  max = 0;
        
        if(n_price > max)
    	max = n_price;
    	
    	return max;
    }
    
    float Lowest(float n_price)
    {	
        static float min = n_price;
        
        if(n_price < min)
    	min = n_price;
    	
    	return min;
    	
    }
    
    int main()
    {
        
        Node *Front = NULL;
        Node *Rear = NULL;                          
        int L_size = 0;                         
        
        ifstream myfile1("a7.txt");
            
        char temp[100];
        string temp_parts;
        int temp_ID;
        int temp_date;
        float temp_price;
        
        float average, high, low;
    
        while(myfile1.peek() != EOF)
        {
            myfile1.getline(temp, 100);
            temp_parts = temp;
    
            myfile1.getline(temp, 100);
            temp_ID = atoi(temp);
            
            myfile1.getline(temp, 100);
            temp_date = atoi(temp);      
            
            myfile1.getline(temp, 100);
            temp_price = atof(temp);
    
            myfile1.getline(temp, 100);
    
            Insert(Front, Rear, temp_parts, temp_date, temp_ID, temp_price, L_size);
            average = Avg(temp_price);
            high = Highest(temp_price);
            low =  Lowest(temp_price);
            L_size++;
            
        }
       
        cout<<fixed<<setprecision(2)<<"Average Price: "<<average<<endl;
        cout<<fixed<<setprecision(2)<<"Most Expensive: "<<high<<endl;
        cout<<fixed<<setprecision(2)<<"Most Inexpensive: "<<low<<endl;
        
        Flush(Front, Rear, L_size); 
    
                       
        return 0;                    
    }
    Would it be any similar to this?
    Code:
    void bubbleSort(int *array, int length)
    {
        for(int i = 0; i < length; i++)
        {
    		 int s = i;
    		 for(int c = i+1; c < length; c++)
    		 {
    		    if(array[c]<array[s])
    		    {    
    		        s = c;
    		    }
    		 }
    		            
    		 swap(array[i], array[s]);
    		 cout<<array[i]<<endl;
    	}
    }

  2. #2
    Allways learning cs_student's Avatar
    Join Date
    Aug 2008
    Location
    ~/
    Posts
    39
    You could do it via the bubble sort algorthm. Just create an iterator which iterates through your linked list for you and have a swap method that swaps the two nodes depending on a conditional which you have set.


    However, have you considered sorting them during insertion? If your project requirements allow you to sort during insertion I suggest you take that approach.


    cs_student


    EDIT: You might even want to have a class LinkedList which manages inserting and retrieving data.
    Last edited by cs_student; 11-29-2009 at 03:34 PM.

  3. #3
    Registered User
    Join Date
    Nov 2009
    Posts
    11
    The assignment requires me to do it this way. I haven't found any good tutorials on how to do the std::list method.

    I found a way to sort it with singly list but it doesn't seen to work for me

    Code:
    void sortNodes(Node * ptr) {
    	int temp = 0;
    	Node * curr;
            
             curr->parts = parts;   
            curr->date = date;
            curr->price = price; 
            curr->ID = Id;
    
    	for(bool didSwap = true; didSwap; ) {
    		didSwap = false;
    		for(curr = ptr; curr->next != NULL; curr = curr->next) {
    			if(curr->date > curr->next->date) {
    				temp = curr->date;
    				curr->date = curr->next->date;
    				curr->next->date = temp;
    				didSwap = true;
    			} 
    		}
    	}
    	
    	do
        {  
            if (curr == NULL)
            cout << "End of list" << endl;
            else
           {  
              cout<< curr->parts<<endl;
              cout<< curr->ID<<endl;
              cout<< curr->date<<endl;
              cout<< curr->price<<endl;
              cout << endl;
              
              curr = curr->next;
           }
       }
         while (curr != NULL);
    
    }

  4. #4
    Allways learning cs_student's Avatar
    Join Date
    Aug 2008
    Location
    ~/
    Posts
    39
    Create a singly linked list class which handles the nodes for you.

    Try implementing something along the lines of

    Code:
    class SList
    {
    private:
            Node* head;
    
    public:
            SList(Node* head);  // constructs SList
            Node* get(int pos); // return the node in x position
            int getData(int pos); // return data in x position
            void insert(Node* node); // insert node or data
            void swap(int a, int b); // swap positions a and b
    };
    ~
    This would allow you to use the SList class as a front end for the Nodes while implementing the bubble sort.

    For example when you find that you need to switch two nodes you don't have to reset their tail nodes they point to and which head nodes point to them (etc...). You just call list.swap(a, b). This would also give you an easy way to go back and reimplement it so that it can be sorted during insertion.

    Also I'm assuming the data your going to be comparing is an integer. You can always use a template so that you are not constrained to an integer when using your SList class. This way you can have a singly linked list of any type of object you wish.

    cs_student

  5. #5
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    See that rocket launcher in your Avatar cs_student? If you ever try to implement BubbleSort for a linked list by re-linking nodes, you could save yourself some time and shoot yourself in the foot with it! It'll probably be less pain.
    Okay for arrays, not so good for linked-lists!

    Sherina: Thank goodness your teachers require you to do it via re-linking pointers. Treating a linked-list like an array only gives you the worst of both worlds! Don't swap the data, re-link the pointers.
    I strongly advise you to implement Insertion Sort. It is the shortest linked-list sorting algorithm there is, out of all 30 linked-list sorting algorithm I know of.
    Last edited by iMalc; 11-30-2009 at 01:01 AM.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Circularly-Doubly Linked List implementation
    By BlackOps in forum C Programming
    Replies: 4
    Last Post: 07-19-2009, 04:45 AM
  2. single linked list to double linked list (help)
    By Countfog in forum C Programming
    Replies: 8
    Last Post: 04-29-2008, 08:04 PM
  3. Please Help - Problem with Compilers
    By toonlover in forum C++ Programming
    Replies: 5
    Last Post: 07-23-2005, 10:03 AM
  4. Linked list with two class types within template.
    By SilasP in forum C++ Programming
    Replies: 3
    Last Post: 02-09-2002, 06:13 AM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM