sorted linked list

[edenn1]

irealy dont know how to sort my liked list .
i should sort it by friends and by name .
please try to help me......
i dont know even how to start.

here is my structs :

typedef struct Person {
	int id;
	char* name;
	struct PersonList* friends;
} Person;

typedef struct PersonList {
	Person* person;
	struct PersonList* next;
} PersonList;

### this programm should be like facebook .
the sorting function is :
PersonList *sortByPopularity(PersonList* allPersons);

at this point i can get person by ID(the output is apointer to the person)
and also i can count number of friends to a spesific person

any help is welcome!!!!!

[Ancient Dragon]

Its the same as any other sort algorithm -- when you need to swap just swap Person pointer in the PersonList structure.

It would be a lot easier to convert the linked list to an array of pointers into the linked list, then sort that array.

[edenn1]

i agree with you about the array . but i am not allowed to use arrays.

[Tom Gunn]

Linked lists can be sorted just like arrays as long as you only use sequential access. Pick a sort algorithm that only looks at adjacent nodes at any given time and it'll work for lists. You don't need to monkey with links either, just swap the data.

This is a program to show you the idea. It's not suitable for your problem because the sort depends on both forward and backward traversal and your lists are only forward, but it might give you some ideas:

#include <stdio.h>

typedef int (*Comparer)(void *a, void *b);
typedef void (*Swapper)(void *a, void *b);

typedef struct Node {
    int value;
    struct Node *prev;
    struct Node *next;
} Node;

void ListSort(Node *head, Comparer cmp, Swapper swap)
{
    Node *x = head;

    /* gnomesort */
    while (x != NULL)
    {
        if (x == head || cmp(x->prev, x) <= 0)
        {
            x = x->next;
        }
        else
        {
            swap(x->prev, x);
            x = x->prev;
        }
    }
}

int CompareNodes(void *a, void *b);
void SwapNodes(void *a, void *b);
void PrintList(Node *head);

int main()
{
    /* manual list for testing */
    Node src[] = 
    {
        {5}, {6}, {3}, {5},
        {1}, {3}, {4}, {6}
    };
    int x;

    /* build the first and last links */
    src[0].next = &src[1];
    src[7].prev = &src[6];

    /* build internal node links */
    for (x = 1; x < 7; ++x)
    {
        src[x].prev = &src[x - 1];
        src[x].next = &src[x + 1];
    }

    PrintList(&src[0]);
    ListSort(&src[0], CompareNodes, SwapNodes);
    PrintList(&src[0]);

    /* just a test. let the OS free memory */

    return 0;
}

int CompareNodes(void *a, void *b)
{
    Node *pa = (Node*)a,
         *pb = (Node*)b;

    if (pa->value == pb->value) return 0;

    return pa->value < pb->value ? -1 : +1;
}

void SwapNodes(void *a, void *b)
{
    Node *pa = (Node*)a,
         *pb = (Node*)b;
    int temp;

    temp = pa->value;
    pa->value = pb->value;
    pb->value = temp;
}

void PrintList(Node *head)
{
    Node *node;

    for (node = head; node != NULL; node = node->next)
    {
        printf("(%d)", node->value);
    }

    puts("");
}

List sorting algorithms usually build a new list with the sorted nodes, but if you don't have much experience with linked lists, they might be confusing. Insertion sort and selection sort are probably the simplest for lists. But if you can keep the lists sorted at all times by inserting nodes in sorted position, that's so much easier than writing a sort function.

[edenn1]

thank you very much .
there is still one plroblem .
how can i sort my list not only by ABC but also by num of frineds(how can i sort by two characters)?????
thank you!

[Tom Gunn]

The easiest way is to sort by the secondary criteria, then sort again by the primary criteria using a stable sort algorithm. The order of the secondary criteria will stay the same with a stable algorithm.