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 autolearn=ham autolearn_force=no version=3.4.4 X-Google-Language: ENGLISH,ASCII-7-bit X-Google-Thread: 103376,c42dbf68f5320193 X-Google-Attributes: gid103376,public X-Google-ArrivalTime: 2002-05-03 06:24:48 PST Path: archiver1.google.com!news1.google.com!newsfeed.stanford.edu!news.tele.dk!small.news.tele.dk!195.27.83.146!news-FFM2.ecrc.net!news.iks-jena.de!lutz From: lutz@iks-jena.de (Lutz Donnerhacke) Newsgroups: comp.lang.ada Subject: Re: Generation of permutations Date: Fri, 3 May 2002 13:24:29 +0000 (UTC) Organization: IKS GmbH Jena Message-ID: References: <4519e058.0204300552.15317df9@posting.google.com> <4519e058.0205020747.11336b44@posting.google.com> <3CD1664A.804F56BC@attbi.com> <4519e058.0205030513.7f28eaef@posting.google.com> NNTP-Posting-Host: taranis.iks-jena.de X-Trace: branwen.iks-jena.de 1020432269 14919 217.17.192.37 (3 May 2002 13:24:29 GMT) X-Complaints-To: usenet@iks-jena.de NNTP-Posting-Date: Fri, 3 May 2002 13:24:29 +0000 (UTC) User-Agent: slrn/0.9.6.3 (Linux) Xref: archiver1.google.com comp.lang.ada:23496 Date: 2002-05-03T13:24:29+00:00 List-Id: * Ted Dennison wrote: >Mark Biggar wrote in message news:<3CD1664A.804F56BC@attbi.com>... >> There are worse sorts then Bogosort. For example there is 52-pickup >> sort: repeatedly randomize the list until you notice that it >> is sorted. > >No, that's just a form of bogosort where the permutations are picked >randomly. In the average case, it should have the exact same time >behavour. Random permutations until sorted is not as bad as expected for a good bogo. The worst case is still "one step". There is a university dealing with such problems more deeply: http://www.ru-eschweilerhof.de/cs/fb17/ (German website)