Sort linked list by pointer manipulation

This is a discussion on Sort linked list by pointer manipulation within the C Programming forums, part of the General Programming Boards category; Hi there, long time no bother I am trying to sort a singly linked list using pointer manipulation using a ...

  1. #1
    Registered User
    Join Date
    Apr 2009
    Posts
    74

    Sort linked list by pointer manipulation

    Hi there, long time no bother

    I am trying to sort a singly linked list using pointer manipulation using a "selection sort"-ish algorithm and I'm having problems.

    My idea is this:

    1. find the smallest (by age) node
    2. move it to the head of the list
    3. check if the list is sorted and if it isn't go back to 1.

    Not highly efficient but it should work. Of course, it doesn't. If I have 3 or more nodes it causes a segmentation fault.

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    /*  WHAT IS A PERSON?  */
    typedef struct node
    	{
    		char name[10];
    		int age;
    		int id;
    		struct node *next;
    	} person;
    
    /*	MAIN MENU	*/
    void Menu()
    {
    	printf("\n\n***   SORT SINGLY LINKED LIST   ***\n\n");
    	printf(" 1. Add\n");
    	printf(" 2. Printout\n");
    	printf(" 3. Sort\n");
    	printf("\n************************************\n");
    	printf("\nChoose :> ");
    }
    
    /*  CREATE NEW PERSON  */
    person* NewPerson (int id)
    {
    	person *new = malloc(sizeof(person));
    	char name[10];
    
    	printf("\nEnter name: ");
    	scanf("%s", name);
    	strcpy(new->name, name);
    	printf("Enter age: ");
    	scanf("%d", &new->age);
    	new->id = id;
    
    	return (new);	
    }
    
    /*  ADD TO THE BEGINNING OF THE LIST  */
    void Add (person **head, person **nova)
    {
    	person *new = *nova;
    	
      	if (*head == NULL)			
      	{
        	*head = new;
        	new->next = NULL;
      	}
      	else									
      	{
        	new->next = *head;
        	*head = new;
    	}
    }
    
    /*  PRINTOUT THE LIST  */
    void Printout (person *head)
    {
      	person *temp = head;
      	int i = 1;
    	
    	printf("\nList contents: \n\n");
      	if (temp == NULL)			
        	printf("\nList is empty!!\n");
      	else						
      	{
        	     	 while (temp)
        	    	{
    			printf("No: %2d  NAME: %9s AGE: ", i, temp->name);
    			printf("%2d  ID: %3d\n", temp->age, temp->id);
    			temp = temp->next;
    			i++;
       		}
      	}
    }
    
    /*	GET NODE BY ID  */
    person* GetByID (person **head, int id)
    {
    	person *temp = *head;
    	
    	while (temp->mb != mb && temp->next != NULL)
    		temp = temp->next;
    		
    	if (temp->mb == mb)
    		return temp;
    	else
    		return NULL;
    }
    
    /*	MOVE NODE TO BEGINING OF LIST  */
    int MoveNode (person **head, int id)
    {
    	person *temp = *head;
    	person *theone;
    	int success = 0;
    	
    	if (temp != NULL)
    	{
    		theone = GetByID(&(*head), id);
    		if (theone == NULL)
    			success = -1;
    		else
    		{
    			while (temp->next != theone)
    				temp = temp->next;
    			
    			temp->next = theone->next;
    			theone->next = *head;
    			*head = theone;
    			
    			success = 1;
    		}
    	}		
    	
    	return success;
    }
    
    /*	SORT LIST BY POINTER MANIPULATION  */
    void SortList (person **head)
    {
    	person *temp = *head;
    	person *min;
    	int id, success, test;
    	
    	if (temp == NULL)
    		printf("\nList empty, sorting is pointless!");
    	else if (temp->next == NULL)
    		printf("\nJust one node, sorting is pointless");
    	else 
    	{
    		do {
    			test = 0;
    			// find the smallest 
    			min = *head;
    			while (temp)
    			{
    				if (temp->age < min->age)
    					min = temp;
    				temp = temp->next;
    			}
    		
    			id = min->id;			
    		
    			// move it to the beginning of the list
    			success = MoveNode(&(*head), id);
    		
    			// check if list is sorted
    			temp = *head;
    			while (temp->next)
    			{
    				if (temp->id > temp->next->id)
    				{
    					test = 1;
    					break;
    				}
    				temp = temp->next;
    			}
    		} while (test != 0);
    	}
    }
    
    
    /*	MAIN  */
    int main (int argc, const char * argv[]) 
    {
    	person *head = NULL;
    	person *nova;
    	int choice, n, id = 1;
    		
    	do {
    		Menu();
    		scanf("%d", &choice);
    		switch (choice)
    		{
    			// Add nodes
    			case 1:	
    		    	new = NewPerson(id);
    				id++;
    				Add(&head, &nova);
    				Printout(head);				
    			break;
    			
    			// Printout the list
    			case 2:	
    				Printout(head);
    			break;
    			
    			// Sort te list
    			case 3:
    				if (head == NULL)
    				printf("\nList empty, sorting is pointless");
    				else 
    				{
    					SortList(&head);
    					Printout(head);
    				}
    			break;
    
    			default:
    			break;	
    		}		
    	} while (choice!=0);
    
    	return 0;
    }
    Last edited by budala; 04-24-2010 at 10:13 AM.

  2. #2
    Registered User
    Join Date
    Jan 2009
    Location
    Australia
    Posts
    375
    I think that you've updated some parts of your code and forgotted to update parts that are affected by those changes.

    Code:
    typedef struct node
    {
    	char name[10];
    	int age;
    	int id;
    	struct node *next;
    } person;
    
    person *temp = *head;
    	
    	while (temp->mb != mb && temp->next != NULL)
    		temp = temp->next;
    Also your Node adding function is called "NewPerson" but you've referenced it as NovaOsaba and your Menu function is called "GlavniIzbornik" but you're referencing it as Menu. I assume that these have actually be fixed as you're saying it's segfaulting (so it must be compiling).

    On another note, I'm not sure what you're trying to do in your sorting function. You're first attempting to sort it so that the youngest are at the beginning, but are then checking whether it is sorted based on the id. Who is to say that a higher id won't be assigned to a younger age? This will cause an infinite loop.

    Lastly:

    Code:
    success = MoveNode(&(*head), id);
    You're joking, right?

  3. #3
    Registered User
    Join Date
    Apr 2009
    Posts
    74
    That's what happens when you replace with copy/paste, and then add some more code whilst forgetting to replace it also

    Anyways, replaced the idioms in my native language with english ones, and also changed the condition when checking if the list is sorted. You are right in saying it is wrong to sort by one field and check the "sortedness" with another, but in my case it was a lapsus calami (what's the latin word for keyboard? )

    BUT!! Even after changing it to check by the same field with which I am sorting, it still doesn't work


    What am I trying to do in my sorted function? Well, my logic is that I look for the smallest (or youngest since I'm comparing by age) node and moving it to the beginning of the list. After that I check if the list is sorted because maybe it was almost sorted and I needed to switch just that one node. If it's not sorted, I look again for the youngest node....

    I think I found the error in my logic! Will try to fix it immediately!

    p.s. why "You're joking, right?" poor choice of variables name or bad logic?
    Last edited by budala; 04-24-2010 at 10:23 AM.

  4. #4
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,451
    Quote Originally Posted by budala
    p.s. why "You're joking, right?" poor choice of variables name or bad logic?
    I think it is the &(*head). Most people would just write head.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  5. #5
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    After you found the first person, where are you going to put the second person? You don't want them at the head of the list....

  6. #6
    Registered User
    Join Date
    Jan 2009
    Location
    Australia
    Posts
    375
    p.s. why "You're joking, right?" poor choice of variables name or bad logic?
    Think about this:

    Code:
    #include <stdio.h>
    
    int main( void )
    {
            int v = 1;
            int *vp = &v;
    
            printf("%p -- %p\n", vp, &(*vp) );
    
            return 0;
    }
    What do you think the output will be?

  7. #7
    Registered User
    Join Date
    Apr 2009
    Posts
    74
    Quote Originally Posted by tabstop View Post
    After you found the first person, where are you going to put the second person? You don't want them at the head of the list....
    that's exactly that! I figured out that my logic is flawed in that respect

  8. #8
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,295
    Quote Originally Posted by tabstop View Post
    After you found the first person, where are you going to put the second person? You don't want them at the head of the list....
    Tabstop has clicked onto the major logic problem here, that I also noticed reading the first post.
    The algorithm you describe can only work for a list with at most two items.
    As soon as you have 3 items say (15, 10, 5) then it can never work.

    First step would be to locate the 5 and move it to the front, giving (5, 15, 10)
    Not sorted, so continue.
    Next step would be to locate the 5!! and move it to the front, giving (5, 15, 10)
    Not sorted, so continue.
    Next step would be to locate the 5!!!!
    ... etc

    What you need to do is have two separate lists. One list of unsorted items, and one list of sorted items. You find the smallest from the unsorted list, remove the item from that list, and then append it to your other list.
    Once the unsorted list is empty, you swap the list pointers over to put your newly sorted list back in place, and you're done.
    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"

  9. #9
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Quote Originally Posted by iMalc View Post
    Tabstop has clicked onto the major logic problem here, that I also noticed reading the first post.
    The algorithm you describe can only work for a list with at most two items.
    As soon as you have 3 items say (15, 10, 5) then it can never work.

    First step would be to locate the 5 and move it to the front, giving (5, 15, 10)
    Not sorted, so continue.
    Next step would be to locate the 5!! and move it to the front, giving (5, 15, 10)
    Not sorted, so continue.
    Next step would be to locate the 5!!!!
    ... etc

    What you need to do is have two separate lists. One list of unsorted items, and one list of sorted items. You find the smallest from the unsorted list, remove the item from that list, and then append it to your other list.
    Once the unsorted list is empty, you swap the list pointers over to put your newly sorted list back in place, and you're done.
    I think, although I didn't try it out, that he can get away with doing this in place, by moving the "head" forward -- use an extra pointer that can take the place of head in calls to MoveNode and in starting the walk-forward-looking-for-min loop.

  10. #10
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,295
    Yes indeed he can; the only difference with such an implementation being that to keep it as one list you'd be connecting the node that you append to the sorted list, to the remainder of the unsorted list, upon each append instead of null-terminating. Otherwise the two approaches are logically identical.

    In fact, if you simply don't connect the two lists together, and don't null-terminate the sorted list after each append either, (deferring the null-terminating until the original list is empty) you end up doing even less work / with less code.
    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. Need help sorting a linked list. Beginner
    By scarlet00014 in forum C Programming
    Replies: 1
    Last Post: 09-27-2008, 06:16 PM
  2. Duplicating value of pointer to linked list
    By zephyrcat in forum C Programming
    Replies: 14
    Last Post: 01-22-2008, 02:19 PM
  3. singly linked circular list
    By DarkDot in forum C++ Programming
    Replies: 0
    Last Post: 04-24-2007, 08:55 PM
  4. Linked List
    By jpipitone in forum C Programming
    Replies: 4
    Last Post: 03-30-2003, 08:27 PM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21