From mboxrd@z Thu Jan  1 00:00:00 1970
X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me
X-Spam-Level: 
X-Spam-Status: No, score=0.6 required=5.0 tests=BAYES_00,TO_NO_BRKTS_FROM_MSSP
	autolearn=no autolearn_force=no version=3.4.4
X-Google-Language: ENGLISH,ASCII-7-bit
X-Google-Thread: 103376,cda33fc7f63c2885
X-Google-Attributes: gid103376,public
X-Google-ArrivalTime: 2002-01-08 09:07:44 PST
Path: 
 archiver1.google.com!news1.google.com!newsfeed.stanford.edu!news-spur1.maxwell.syr.edu!news.maxwell.syr.edu!out.nntp.be!propagator-SanJose!in.nntp.be!newsranger.com!www.newsranger.com!not-for-mail
Newsgroups: comp.lang.ada
From: Ted Dennison<dennison@telepath.com>
References: <mailman.1010451062.16465.comp.lang.ada@ada.eu.org>
 <7iE_7.8661$cD4.15714@www.newsranger.com>
 <3c3b13ba$0$212$626a54ce@news.free.fr>
Subject: Re: list strawman
Message-ID: <sHF_7.8807$cD4.16831@www.newsranger.com>
X-Abuse-Info: When contacting newsranger.com regarding abuse please
X-Abuse-Info: forward the entire news article including headers or
X-Abuse-Info: else we will not be able to process your request
X-Complaints-To: abuse@newsranger.com
NNTP-Posting-Date: Tue, 08 Jan 2002 12:07:36 EST
Organization: http://www.newsranger.com
Date: Tue, 08 Jan 2002 17:07:36 GMT
Xref: archiver1.google.com comp.lang.ada:18652
Date: 2002-01-08T17:07:36+00:00
List-Id: <comp.lang.ada>

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.