Sorting a linked list

Thread view:

Enable EMail Alerts

Start New Thread

Thread rating:

Peter Schmitz - 12 Sep 2004 14:19 GMT

Hi,

in my application, I defined a linked list just as follows:

typedef struct _MYLIST{
int myval;
void *next;
}MYLIST;

MYLIST head;

So, the problem is the following: the value 'myval' located in each item of
a filled linked list contains a specific value - but not in the correct
order. so, what's the fastest way to sort the items in the list ascending by
their values in 'myval'.
How can this be done?

thanks a lot
Peter

Reply to this Message

Carl Daniel [VC++ MVP] - 12 Sep 2004 15:34 GMT

> Hi,
>
[quoted text clipped - 12 lines]
> the list ascending by their values in 'myval'.
> How can this be done?

#include <list>

std::list<int> mylist;

// insert items into mylist.

mylist.sort();

If you're dead-set against using the C++ standard library, to sort a linked
list you basically need to use the tehcniques that were used to sort files
on tapes in decades past. Heapsort and shellsort were both important
algorithms in that era.

Another technique is to insert pointers to your list intems into an array
(or vector), then sort that vector using an appropriate indirection in the
comparison step, then use the sorted vector to rebuild the linked list in
the desired order.

Yet another strategy is to never allow the list to be out of order - always
find the correct in-order insertion point as each item is added to the list.

-cd

Reply to this Message

David Olsen - 13 Sep 2004 17:54 GMT

>>in my application, I defined a linked list just as follows:
>>
[quoted text clipped - 18 lines]
>
> mylist.sort();

Since the data is just an int, std::vector<int> might be a better
container. std::set<int> might even work well depending on what is
being done with the data.

But in general I agree with Carl. Don't create your own linked list (or
any other container) unless there really is no other alternative.

> If you're dead-set against using the C++ standard library, to sort a linked
> list you basically need to use the tehcniques that were used to sort files
> on tapes in decades past. Heapsort and shellsort were both important
> algorithms in that era.

If I remember correctly, heapsort and shellsort both require swapping
and random access, which are problematic for singly linked lists. The
best sort algorithm for a singly linked list is merge sort.

Signature

David Olsen
qg4h9ykc5m@yahoo.com

Reply to this Message

James Curran - 17 Sep 2004 21:01 GMT

> If I remember correctly, heapsort and shellsort both require swapping
> and random access, which are problematic for singly linked lists. The
> best sort algorithm for a singly linked list is merge sort.

Actually, QuickSort is completely implementable on a Singly-linked list.
The only problem is that you'd need to use the first item on each sublist as
the pivot, so it may succumb to the "nearly-sorted" flaw.

Signature

Truth,
James Curran
Home: www.noveltheory.com Work: www.njtheater.com
Blog: www.honestillusion.com Day Job: www.partsearch.com
(note new day job!)

Reply to this Message

Lord2702 - 12 Sep 2004 18:38 GMT

Sun. Sep. 12, 2004 10:35 AM PT

Instead of sorting a list, specially, yours is a Single Linked List, then I
will suggest that you insert elements in the list in Sorted. Means, keep
your list in order while you insert an element, then Binary search will help
you to find a particular element. If you want me to give an algo. How to
insert elements in Order, pl. let me know.

Good Luck!

> Hi,
>
[quoted text clipped - 15 lines]
> thanks a lot
> Peter

Reply to this Message

Sorting a linked list

Free Magazines