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=-2.9 required=5.0 tests=BAYES_00,MAILING_LIST_MULTI
	autolearn=unavailable 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 12:00:06 PST
Path: 
 archiver1.google.com!news1.google.com!newsfeed.stanford.edu!canoe.uoregon.edu!arclight.uoregon.edu!fr.usenet-edu.net!usenet-edu.net!enst!enst.fr!not-for-mail
From: "Steven Deller" <deller@smsail.com>
Newsgroups: comp.lang.ada
Subject: RE: list strawman
Date: Tue, 8 Jan 2002 14:57:35 -0500
Organization: ENST, France
Sender: comp.lang.ada-admin@ada.eu.org
Message-ID: <mailman.1010520002.5728.comp.lang.ada@ada.eu.org>
Reply-To: comp.lang.ada@ada.eu.org
NNTP-Posting-Host: marvin.enst.fr
Mime-Version: 1.0
Content-Type: text/plain;
	charset="us-ascii"
Content-Transfer-Encoding: 7bit
X-Trace: avanie.enst.fr 1010520002 80300 137.194.161.2 (8 Jan 2002 20:00:02
 GMT)
X-Complaints-To: usenet@enst.fr
NNTP-Posting-Date: Tue, 8 Jan 2002 20:00:02 +0000 (UTC)
To: <comp.lang.ada@ada.eu.org>
Return-Path: <deller@smsail.com>
X-Priority: 3 (Normal)
X-MSMail-Priority: Normal
X-Mailer: Microsoft Outlook, Build 10.0.2627
Importance: Normal
In-Reply-To: <3c3b2aa0$0$212$626a54ce@news.free.fr>
X-MimeOLE: Produced By Microsoft MimeOLE V5.50.4133.2400
Errors-To: comp.lang.ada-admin@ada.eu.org
X-BeenThere: comp.lang.ada@ada.eu.org
X-Mailman-Version: 2.0.6
Precedence: bulk
List-Help: <mailto:comp.lang.ada-request@ada.eu.org?subject=help>
List-Post: <mailto:comp.lang.ada@ada.eu.org>
List-Subscribe: <http://ada.eu.org/mailman/listinfo/comp.lang.ada>,
	<mailto:comp.lang.ada-request@ada.eu.org?subject=subscribe>
List-Id: comp.lang.ada mail<->news gateway <comp.lang.ada.ada.eu.org>
List-Unsubscribe: <http://ada.eu.org/mailman/listinfo/comp.lang.ada>,
	<mailto:comp.lang.ada-request@ada.eu.org?subject=unsubscribe>
Errors-To: comp.lang.ada-admin@ada.eu.org
X-BeenThere: comp.lang.ada@ada.eu.org
Xref: archiver1.google.com comp.lang.ada:18664
Date: 2002-01-08T14:57:35-05:00

Jean-Marc,

Sorry I did not see your second post before sending my previous reply.

> -----Original Message-----
> From: comp.lang.ada-admin@ada.eu.org 
> [mailto:comp.lang.ada-admin@ada.eu.org] On Behalf Of 
> Jean-Marc Bourguet
> Sent: Tuesday, January 08, 2002 12:22 PM
> To: comp.lang.ada@ada.eu.org
> Subject: Re: list strawman
> Yes.  There is still the problem of choosing the pivot.  With 
> random access, I'd use a random element.  Without random 
> access, you'll have to choose the first or the last element 
> and then degenerate in N^2 for a sorted input, not something 
> I'd like in a general purpose library. Well taking a random 
> element is possible but at a cost of iterating some more time 
> on the whole list.  Perhaps there is a way to even choose the 
> next pivot while you construct the upper and lower list but I 
> don't see one.

Actually, the O(N**2) for a sorted list worried me too, but I think I
have a reasonable way to choose a "median" element after the first scan
with minimal additional computations.  I'll work it through before
suggesting it.

Regards,
Steve Deller