Re: list strawman

[Ted Dennison<dennison@telepath.com>]

In article <3c3b13ba$0$212$626a54ce@news.free.fr>, Jean-Marc Bourguet says...
>
>How do you do quicksort on a list?  quicksort assume random access so
>you'll have O(n) space overhead. I'd use a merge sort on a list which
>would have the same complexity as quicksort and do not need random
>access.

I don't see that. The way it works, all you have to keep track of is the ends of
the list (or sublist you are working on), the pivot point, and a couple of
pointers that iterate through the list. There's nothing in there that can't be
done easily with a doubly-linked list.

For an example of how this can be done in place (and thus no extra space
overhead), see http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/qsort1a.html .
The example uses an array, but again there's nothing in there that can't be
trivially adapted to doubly-linked lists. 

There are even ways to do it in place without recursion...

---
T.E.D.    homepage   - http://www.telepath.com/dennison/Ted/TED.html

No trees were killed in the sending of this message. 
However a large number of electrons were terribly inconvenienced.