sort linked listW

[t]

What is the most efficient way to sort a linked list? In other words,
how is std::list's sort() member function usually implemented?

I was thinking of two approaches:
(1) make an array of pointers from the list nodes, do a quicksort, and
rebuild the list
(2) do an insertion sort, which is simple but has O(n^2) worst-case
complexity

 

[Michael DOUBEZ]

t a écrit :

What is the most efficient way to sort a linked list? In other words,
how is std::list's sort() member function usually implemented?

I guess it depends on the implementation of your STL. The only guaranty
is that it has nlog(n) complexity.

I was thinking of two approaches:
(1) make an array of pointers from the list nodes, do a quicksort, and
rebuild the list

I expect the list container already swap elements and doesn't copy them.

(2) do an insertion sort, which is simple but has O(n^2) worst-case
complexity

Do you mean that you would insert them in ordered fashion from the very
beginning ? That depends on the usage you have.

If you have a lot of insertion and if this is critical, you can adopt a
mixed approach: having a range where elements are sorted and a range
where they are not. Upon a threshold (typically a percentage of unsorted
elements), you sort them.

For now, I would advise to use std::list<>::sort() and if there is an
efficiency issue, then you would explore the alternatives (switching to
std::multiset<> by example).

Michael

 

[Phil Endecott]

What is the most efficient way to sort a linked list? In other words,
how is std::list's sort() member function usually implemented?

google("linked list sort") will find a PDF called "A COMPARATIVE STUDY
OF LINKED LIST SORTING ALGORITHMS", which I guess will comprehensively
answer your question. The linked-list mergesort is the normal best bet.
It certainly isn't necessary to copy the data, or pointers to it, into
another data structure.


Phil.

 

[Juha Nieminen]

(1) make an array of pointers from the list nodes, do a quicksort, and
rebuild the list

Quicksort is perfectly possible to apply to a linked list. (There
isn't a single step in quicksort which would require random access.)
Likewise merge sort. Heap sort would not be possible.

 

[James Kanze]

Quicksort is perfectly possible to apply to a linked list. (There
isn't a single step in quicksort which would require random access.)
Likewise merge sort. Heap sort would not be possible.

Yes, but would quicksort be faster. Most efficient
implementations of quicksort that I've seen do use random access
when finding the pivot. Just taking the first (or last) element
will result in very bad performance for some "typical" cases
(initial values almost sorted, for example); the most common
solution seems to be to take the median of the first, last and
middle values, and getting the middle value requires true random
access.

The usual solution I've seen for sorting linked lists is
mergesort, which can be very fast *if* you don't have to
actually copy values (which you don't if you're dealing with
linked nodes).

 

[Juha Nieminen]

the most common
solution seems to be to take the median of the first, last and
middle values, and getting the middle value requires true random
access.

Actually it doesn't. It's actually possible to apply
median-of-three-pivot quicksort to a linked list even without random access.

Ok, with the very first partitioning it cannot be done. The very first
partition must be done in the basic way (eg. taking the first value as
pivot). However, all subsequent partitionings can be performed with the
pivot chosen with the median-of-three method.

The way to do this is quite simple: While partitioning, ie. when
traversing the list forwards and backwards, keep an iterator which
always points to the middle element of the lower partition (ie. you
advance it once for every two advances of the traversal) and another
which points to the middle element of the upper partition. After you
have partitioned like this, you have all the necessary iterators to
calculate the new two median-of-three elements and recursively partition
the two parts.

Even optimizing this quicksorting with insertion sort when the
partition is small enough is possible (because while partitioning you
can count the size of each subpartition).

The usual solution I've seen for sorting linked lists is
mergesort, which can be very fast *if* you don't have to
actually copy values (which you don't if you're dealing with
linked nodes).

That's true. Merge sort with doubly-linked lists can be very fast
because no extra memory is required (unlike when merge-sorting arrays).
(Basically all the extra memory required to perform merge sort is
already there, in the two links in each element.)

 

[James Kanze]

Actually it doesn't. It's actually possible to apply
median-of-three-pivot quicksort to a linked list even without
random access.

Ok, with the very first partitioning it cannot be done. The
very first partition must be done in the basic way (eg. taking
the first value as pivot). However, all subsequent
partitionings can be performed with the pivot chosen with the
median-of-three method.

The way to do this is quite simple: While partitioning, ie.
when traversing the list forwards and backwards, keep an
iterator which always points to the middle element of the
lower partition (ie. you advance it once for every two
advances of the traversal) and another which points to the
middle element of the upper partition. After you have
partitioned like this, you have all the necessary iterators to
calculate the new two median-of-three elements and recursively
partition the two parts.

Hey, that's clever.