Sort a linked list 2

[mattias1975]

Hello!

Are there any function that i can use to sort a linked list?
For example in alphabetical order for a field.
Or does anyone have some code example?

Thank you.

 

[Salem]

It would be a lot easier if the data were in an array, then you could just use the qsort() function in stdlib.h


--

 

[mattias1975]

Hm. That solution does not fit in my application.

 

[Salem]

- count the elements in the list (=n)
- allocate an array of n pointers
- make each one point at a node in the list
- sort it
- recreate the links
- free the pointer array

--

 

[marsd]

Fair warning. It is a pain and basically ugly.
I worked with a singly linked list sort one time for 26 hours and came up vexed with how inflexible it was. better to sort the data than the list elements and if you must sort the elements most algos are not simple and not very efficient.
Here is a good analysis:

http://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html

 

[columb]

Try replacing yor linked list with a binary tree. For a little more code you get all the advantages of a linked list plus sorting

Columb Healy
Living with a seeker after the truth is infinitely preferable to living with one who thinks they've found it.

 

[jstreich]

selection sort works just fine with a linked list, though it is O(n^2)

node *ptr;
for( ptr = head; ptr; ptr = ptr->next);
{
   for(node *ptr2 = ptr->next; ptr2; ptr2 = ptr2->next)
   {
       //if ptr2 is less then ptr, 
       if(ptr->data > ptr2->data)
       {
          //then swap ptr and ptr2
          temp = ptr->data;
          ptr->data = ptr2->data;
          ptr2->dat = temp;
       }
   }
}

Not knowing what type your linked list contains, I couldn't declare temp, and if strings then the comparison would be strcmp (ASCIIbetical) or strcasecmp (alphabetical).

 

[marsd]

That sorts data. It does not sort the list by
re-ordering list nodes.

 

[jstreich]

He didn't say if it is to be by moving the nodes... But that would be easy enough to change...

node *ptr;
node n;
n.next = head
for( ptr = n; ptr; ptr = ptr->next);
{
   for(node *ptr2 = ptr->next; ptr2; ptr2 = ptr2->next)
   {
       //if ptr2 is less then ptr, 
       if(ptr->next->data > ptr2->next->data)
       {
          if(ptr == head)
             head = ptr2->next;
          //then swap ptr and ptr2
          node*temp = ptr->next;
          ptr->next = ptr2->next;
          ptr2->next = temp;
       }
   }
}

 

[marsd]

If you read the above posts the issue is that a linked list is sorted not by sorting struct members but by actual shuffling of nodes. Since a linked list can be circular, singly linked, doubly linked, etc.. a general purpose solution can be really ugly, and really inefficient,especially when, say, given a prototype like this:

FTYPE *sortList(FTYPE *hd, FTYPE *candidate, int (*usecmp)(void *,void *));

In any case I'm glad you think it's simple, but I don't.
I'd rather use a binary tree as columb said.

 

[jstreich]

Oops, a couple of corrections...

node *ptr;
node n;
n.next = head;
for( ptr = &n; ptr; ptr = ptr->next);
{
   for(node *ptr2 = ptr->next; ptr2; ptr2 = ptr2->next)
   {
       //if ptr2 is less then ptr,
       if(ptr->next->data > ptr2->next->data)
       {
          if(ptr->next == head)
             head = ptr2->next;
          //then swap ptr and ptr2
          node*temp = ptr->next;
          ptr->next = ptr2->next;
          ptr2->next = temp;
       }
   }
}

If you read the above posts the issue is that a linked list is sorted not by sorting struct members but by actual shuffling of nodes.

The above does that... The first solution I gave was swap the data, this one swaps pointers... i.e. reorders the nodes.

Since a linked list can be circular, singly linked, doubly linked, etc..

The above will work on singly and doubly linked lists, and is no less effecient than can be done for doubly. Modifying the code to work circularly isn't that terribly difficult.

a general purpose solution can be really ugly, and really inefficient
It's a list, sorting should take at worst O(n^2)... At best, assuming the solution someone else posed (merge sort using an array of pointers to the nodes) O(nlgn) -- but that would have a lot of extra over head for creating and destroying the array of pointers, and may or may not be faster in actual runtime.

Moreover, mattias didn't say he was looking for a general purpose solution that work on all linked lists, I'm sure he knows what type of links his list will be using. I offered a sketch of a solution in hopes that he may benifit from it; if I came off as egotistical then I'm sorry.