Sorting a linked list

[Guest]

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

 

[Carl Daniel [VC++ MVP]]

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?

#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

 

[Lord2702]

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!

 

[David Olsen]

#include <list>

std::list<int> mylist;

// insert items into mylist.

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.

 

[James Curran]

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.

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