1. ## 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;

{
printf("\n\n***   SORT SINGLY LINKED LIST   ***\n\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  */
{
person *new = *nova;

{
new->next = NULL;
}
else
{
}
}

/*  PRINTOUT THE LIST  */
{
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)
{

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 *theone;
int success = 0;

if (temp != NULL)
{
if (theone == NULL)
success = -1;
else
{
while (temp->next != theone)
temp = temp->next;

temp->next = theone->next;

success = 1;
}
}

return success;
}

/*	SORT LIST BY POINTER MANIPULATION  */
{
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
while (temp)
{
if (temp->age < min->age)
min = temp;
temp = temp->next;
}

id = min->id;

// move it to the beginning of the list

// check if list is sorted
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 *nova;
int choice, n, id = 1;

do {
scanf("%d", &choice);
switch (choice)
{
case 1:
new = NewPerson(id);
id++;
break;

// Printout the list
case 2:
break;

// Sort te list
case 3:
printf("\nList empty, sorting is pointless");
else
{
}
break;

default:
break;
}
} while (choice!=0);

return 0;
}```

2. 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;

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. 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?

4. 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.

5. 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. p.s. why "You're joking, right?" poor choice of variables name or bad logic?

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. 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....
that's exactly that! I figured out that my logic is flawed in that respect

8. 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.

9. Originally Posted by iMalc
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. 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.