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=-1.9 required=5.0 tests=BAYES_00,FREEMAIL_FROM autolearn=ham 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-11 04:42:20 PST Path: archiver1.google.com!news1.google.com!sn-xit-02!supernews.com!news.tele.dk!small.news.tele.dk!193.251.151.101!opentransit.net!proxad.net!feeder2-1.proxad.net!news1-2.free.fr!not-for-mail Message-ID: <3BEE70E6.E7988E71@free.fr> Date: Sun, 11 Nov 2001 13:36:54 +0100 From: Jean-Marc Bourguet X-Mailer: Mozilla 4.7 [en] (X11; I; Linux 2.2.10 i586) X-Accept-Language: en MIME-Version: 1.0 Newsgroups: comp.lang.ada Subject: Re: List container strawman 1.2 References: <3BECA3B7.5020702@telepath.com> <87668ivpw8.fsf@deneb.enyo.de> <87d72qfrtd.fsf@deneb.enyo.de> <3BED75C8.D9D55263@free.fr> <45iH7.20346$xS6.32497@www.newsranger.com> Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Organization: Guest of ProXad - France NNTP-Posting-Date: 11 Nov 2001 13:42:20 MET NNTP-Posting-Host: 213.228.43.197 X-Trace: 1005482540 news1-2.free.fr 32064 213.228.43.197 X-Complaints-To: abuse@proxad.net Xref: archiver1.google.com comp.lang.ada:16273 Date: 2001-11-11T13:42:20+01:00 List-Id: Ted Dennison wrote: > > 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 usefull when you want [...] > If you are talking *assuming* the proper supplied routine, then I guess that's a > matter for discussion. It sounds like we probably have at least one vote for > requiring that, no? Stabality is a property of the sorting algorithm, not of the comparison function. You can simulate a stable sort with a non stable algorithm at the cost of complexifying the comparison function see Knuth TAOCP Volume 3 for more information. -- Jean-Marc