Re: sort linked listW
On Jan 17, 7:08 pm, Juha Nieminen <nos...@thanks.invalid> wrote:
t wrote:
(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.
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).
--
James Kanze (GABI Software) email:james.kanze@gmail.com
Conseils en informatique orient=E9e objet/
Beratung in objektorientierter Datenverarbeitung
9 place S=E9mard, 78210 St.-Cyr-l'=C9cole, France, +33 (0)1 30 23 00 34