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,a644fa9cd1a3869a X-Google-Attributes: gid103376,public X-Google-ArrivalTime: 2001-11-10 20:01:32 PST Path: archiver1.google.com!news1.google.com!sn-xit-02!supernews.com!isdnet!enst!enst.fr!not-for-mail From: "Steven Deller" Newsgroups: comp.lang.ada Subject: RE: List container strawman 1.2 Date: Sat, 10 Nov 2001 22:59:10 -0500 Organization: ENST, France Sender: comp.lang.ada-admin@ada.eu.org Message-ID: 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 1005451290 96639 137.194.161.2 (11 Nov 2001 04:01:30 GMT) X-Complaints-To: usenet@enst.fr NNTP-Posting-Date: Sun, 11 Nov 2001 04:01:30 +0000 (UTC) To: Return-Path: X-Priority: 3 (Normal) X-MSMail-Priority: Normal X-Mailer: Microsoft Outlook, Build 10.0.2627 X-MimeOLE: Produced By Microsoft MimeOLE V5.50.4133.2400 In-reply-to: <45iH7.20346$xS6.32497@www.newsranger.com> Importance: Normal 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: List-Post: List-Subscribe: , List-Id: comp.lang.ada mail<->news gateway List-Unsubscribe: , List-Archive: Errors-To: comp.lang.ada-admin@ada.eu.org X-BeenThere: comp.lang.ada@ada.eu.org Xref: archiver1.google.com comp.lang.ada:16265 Date: 2001-11-10T22:59:10-05:00 > -----Original Message----- > From: comp.lang.ada-admin@ada.eu.org > [mailto:comp.lang.ada-admin@ada.eu.org] On Behalf Of Ted Dennison > Sent: Saturday, November 10, 2001 5:44 PM > To: comp.lang.ada@ada.eu.org > Subject: Re: List container strawman 1.2 > In article <3BED75C8.D9D55263@free.fr>, Jean-Marc Bourguet says... > >A sorting algorithm is stable if after applying it, the > relative order > >of elements comparing equal is conserved. That's useful > when you want > > Well, that would clearly be up to the person who supplies the > comparison routine, would it not? I mean (assuming the > current definition), if "<" or ">" is supplied, then equal > values will not be changed. On the other hand, if "<=" or > ">=" are supplied, then they will be. That is not true. There is no comparison routine that can be supplied in an instantiation that will convert a non-stable sort to a stable sort. It is necessary to "know" the original positions and include those positions as part of the comparison (the original position becomes the tie-breaker to keep equal values from switching places). For any sort that is O(NlogN) in time, converting it to a stable sort requires O(N) space (to keep the position values with the records). One of the better ways to do a stable sort on an array is to create an O(N) list of pointers to the original elements, sort the pointers, and then rearrange the original array to match the new positions of the pointers. The position of the elements then becomes the "tie-breaker". I'd prefer having a "stable sort" generic that "wraps" an arbitrary generic sorting routine, but it is not possible to pass a generic as a generic formal :-(. Jean-Marc Bourguet has it pretty much right, though I would prefer a heap sort instead of a merge sort. A heap sort is also guaranteed O(NlogN) time, and also can be done "in place" more easily. Regards, Steve Deller Smooth Sailing LLC