Thread: help with sorting function :(

  1. #1
    Learner Axel's Avatar
    Join Date
    Aug 2005
    Posts
    335

    help with sorting function :(

    I've created the following nodes in my list:

    Code:
     
           addElement(&start, "B", 1);
    	addElement(&start, "D", 2);
    	addElement(&start, "A", 3);
    	addElement(&start, "C", 4);


    next i have a loop which runs it x amount of nodes. It compares the next element with the current element
    i.e. : if ( B is greater than A)

    i then pass a reference to the current node(petId) i.e. B and it swaps it to AB


    Code:
     for(i=0; i <= 5; i++){
         	
         	while (start && start->next != NULL)
         	{
         		
         		if (strcmp(start->next->petName, start->petName) <0){
            	 	current=swap(current,start->petId);
         		}
            	start = start->next;	 
         	}
         	start = head;
         	
         }
    i then run my sort function:

    Code:
    petNode* swap(petNode *current, int petId)
    {
        
        petNode *temp;                   
        petNode *tmp;                     
        
        temp=current;
        if(current->petId==petId)
        {
            tmp=current->next;
            current->next=current->next->next;
            tmp->next=current;
            current=tmp;
            return(current);
        }
        else
        {
            while(temp->next->next!=NULL)
            {
                if(temp->next->petId==petId)
                {
                    tmp=temp->next->next;
                    temp->next->next=temp->next->next->next;
                    tmp->next=temp->next;
                    temp->next=tmp;
                    break;
                }
                temp=temp->next;
            }
            return(current);
        }
    }
    The original list
    DBAC becomes BACD

    and i can't figure it out. it works for some combos like:

    BDAC becomes ABCD... any ideas??

    i have tried printing the list after every swap the occurs and get:

    BDAC
    BDAC
    BADC
    BACD

    i'm stuck :|
    Last edited by Axel; 10-27-2006 at 08:38 AM.

  2. #2
    Fear the Reaper...
    Join Date
    Aug 2005
    Location
    Toronto, Ontario, Canada
    Posts
    625
    I believe many there are already many threads on this kind of thing on the boards, so I'm not going to go in depth as to what your exact problem is. However, one thing I noticed :
    Shouldn't this part :

    Code:
    while (start && start->next != NULL)
         	{
         		
         		if (strcmp(start->next->petName, start->petName) <0){
            	 	current=swap(current,start->petId);
         		}
            	start = start->next;	 
         	}
         	start = head;
    Instead be something like this :

    Code:
    while (start && start->next != NULL)
         	{
         		current = start;
         		if (strcmp(start->next->petName, start->petName) <0){
            	 	current=swap(current,start->petId);
         		}
            	start = current->next;	 
         	}
         	start = head;
    Teacher: "You connect with Internet Explorer, but what is your browser? You know, Yahoo, Webcrawler...?" It's great to see the educational system moving in the right direction

  3. #3
    Learner Axel's Avatar
    Join Date
    Aug 2005
    Posts
    335
    Hmm i don't get what you mean? i tried it anyway and only 2 nodes are printed out. i think the problem is i want to scan the list (with the start pointer) but if i want to swap i also have to use start and since i have to keep track of the start of the list

  4. #4
    Fear the Reaper...
    Join Date
    Aug 2005
    Location
    Toronto, Ontario, Canada
    Posts
    625
    The way I see it, you're missing some comparisons in your sort.

    Suppose you have BCAD. First you compare B and C, no problems. Then you compare C and A. Swap those two. But then you must AGAIN compare with with B, to bring A up to the front. I don't believe you're doing that second part.

    And actually, now that I think about it, my fix is probably incorrect.

    Further, you may find doing this second part difficult with a singly linked list. And one last thing, if you want to look up sorting algorithms, to make sure your logic is right, look up stuff like bubblesort or inserting sort of merge sort or quick sort on google.
    Teacher: "You connect with Internet Explorer, but what is your browser? You know, Yahoo, Webcrawler...?" It's great to see the educational system moving in the right direction

  5. #5
    Learner Axel's Avatar
    Join Date
    Aug 2005
    Posts
    335
    i have tried using bubble sort but it still doesn't seem to work. I know that my swap method works i simply pass the petNo i want swapped so if i want the first element in the list swapped i pass 0 and it swaps it with the next node. I think the way i'm scanning through the list is the problem.


    Code:
    	addElement(&start, "W", 0);
    	addElement(&start, "S", 1);
    	addElement(&start, "T", 2);
    	addElement(&start, "T", 3);
    	addElement(&start, "M", 4);
    
    
    
      while (outer > 0)
         {
         	last = 0;
         	for (inner=0; inner<outer; inner++){
         		if (strcmp(current->petName, current->next->petName) >0)
         		{
         			current=swap(current,current->petId);
         			last = inner;
         		}
         	}
         	outer = last;
         }

    S

    W

    T

    T

    M

  6. #6
    Learner Axel's Avatar
    Join Date
    Aug 2005
    Posts
    335
    and even so i want to scroll through the list by doing:

    current = current->next;

    but i also have to swap fields, once the swap is complete i get a reference to the swapped list. i also have to save it to current. so they conflict... thats where im unsure now.

  7. #7
    {Jaxom,Imriel,Liam}'s Dad Kennedy's Avatar
    Join Date
    Aug 2006
    Location
    Alabama
    Posts
    1,065
    Which type of sort are you attempting to do? A bubble sort, for example, requires two loops to preform the action. A select sort requires a couple more pointers than you are using.

  8. #8
    Learner Axel's Avatar
    Join Date
    Aug 2005
    Posts
    335
    i'm trying to do it with bubblesort hence i have an outer while and inner for loop.
    Last edited by Axel; 10-27-2006 at 07:32 PM.

  9. #9
    Learner Axel's Avatar
    Join Date
    Aug 2005
    Posts
    335
    ahh it was one line but so difficult. Basically i was scanning the list comparing start and start next nodes and saving them to a new list called "current". After each pass i wasn't updating start so it was scanning the previously unordered list.

  10. #10
    {Jaxom,Imriel,Liam}'s Dad Kennedy's Avatar
    Join Date
    Aug 2006
    Location
    Alabama
    Posts
    1,065
    The use of a for loop in sorting a linked list escapes me. IMO, two while loops would be better. The purpose for a linked list is to store N records. . . where we don't know the value of N. Also, we don't need to know N for sorting or searching, since we can do everything else without N's value.
    What I have used in the past would be something like:
    Code:
    int sorted = 0;
    while (!sorted){
            sorted = 1;
            while (tmp != NULL){
                    //transvers the list.
                    if (<we find something out of place>){
                            //make the change.
                            sorted = 0;
                    }
            }
    }
    The way you did it, however, looks like you will not sort a long list.

  11. #11
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318

    Wink

    I'll let you in on a little secret:

    Properly implementing bubble sort on a linked list turns out to be reasonably complex.
    On the other hand, implementing Insertion Sort for a linked list is considerably simple, and is no slower than bubble sort.

  12. #12
    Registered User
    Join Date
    Aug 2005
    Location
    Austria
    Posts
    1,990
    Quote Originally Posted by iMalc
    I'll let you in on a little secret:

    Properly implementing bubble sort on a linked list turns out to be reasonably complex.
    On the other hand, implementing Insertion Sort for a linked list is considerably simple, and is no slower than bubble sort.
    That really depends on how you implement the swap function. Generally there is no need to touch the links of the nodes when swapping. it's good enough to just change the nodes data.
    Using bubblesort you will always swap the data of the current nodes with the data of the current nodes next nodes data. that makes the swap function very simple
    e.g
    Code:
    void bubble_swap( node * current ) {
         char * tmp = current->petName;
         int tmpId = current->petId;
         curent->petName = current->next->petName;
         curent->next->petName =tmp;
         curent->petId = current->next->petId;
         curent->next->petId =tmpId;
    }
    Kurt

  13. #13
    Learner Axel's Avatar
    Join Date
    Aug 2005
    Posts
    335
    Quote Originally Posted by ZuK
    That really depends on how you implement the swap function. Generally there is no need to touch the links of the nodes when swapping. it's good enough to just change the nodes data.
    Using bubblesort you will always swap the data of the current nodes with the data of the current nodes next nodes data. that makes the swap function very simple
    e.g
    Code:
    void bubble_swap( node * current ) {
         char * tmp = current->petName;
         int tmpId = current->petId;
         curent->petName = current->next->petName;
         curent->next->petName =tmp;
         curent->petId = current->next->petId;
         curent->next->petId =tmpId;
    }
    Kurt

    yes, i've did that but figured that it's incredibly insufficient in the long run. What happens when you have 30 fields in your node?? your code would get huge..

  14. #14
    Registered User
    Join Date
    Aug 2005
    Location
    Austria
    Posts
    1,990
    Quote Originally Posted by Axel
    yes, i've did that but figured that it's incredibly insufficient in the long run. What happens when you have 30 fields in your node?? your code would get huge..
    Then there is still the possibility to make the nodes data a pointer to a struct that contains the actual data. this way it would become a matter of swapping two pointers.
    Kurt

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Troubleshooting Input Function
    By SiliconHobo in forum C Programming
    Replies: 14
    Last Post: 12-05-2007, 07:18 AM
  2. Calling a Thread with a Function Pointer.
    By ScrollMaster in forum Windows Programming
    Replies: 6
    Last Post: 06-10-2006, 08:56 AM
  3. Please Help - Problem with Compilers
    By toonlover in forum C++ Programming
    Replies: 5
    Last Post: 07-23-2005, 10:03 AM
  4. c++ linking problem for x11
    By kron in forum Linux Programming
    Replies: 1
    Last Post: 11-19-2004, 10:18 AM
  5. Replies: 4
    Last Post: 11-23-2003, 07:15 AM