RE: list strawman

["Steven Deller" <deller@smsail.com>]

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