Thread: 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;
}

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?

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.

Originally Posted by tabstop

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.

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.