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-04 17:52:05 PST Path: archiver1.google.com!news1.google.com!newsfeed.stanford.edu!postnews1.google.com!not-for-mail From: dewar@gnat.com (Robert Dewar) Newsgroups: comp.lang.ada Subject: Re: Generation of permutations Date: 4 May 2002 17:52:04 -0700 Organization: http://groups.google.com/ Message-ID: <5ee5b646.0205041652.63032ba6@posting.google.com> References: <4519e058.0204300552.15317df9@posting.google.com> <4519e058.0205020747.11336b44@posting.google.com> <3CD1664A.804F56BC@attbi.com> NNTP-Posting-Host: 205.232.38.14 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 8bit X-Trace: posting.google.com 1020559924 27773 127.0.0.1 (5 May 2002 00:52:04 GMT) X-Complaints-To: groups-abuse@google.com NNTP-Posting-Date: 5 May 2002 00:52:04 GMT Xref: archiver1.google.com comp.lang.ada:23550 Date: 2002-05-05T00:52:04+00:00 List-Id: "Marin David Condic" > A better (slower) algorithm would be > to generate a random set of machine > instructions, execute them, see if it sorted the list ^^^ You could see if it sorted some particular list, but to determine whether a set of instructions constitutes a general sorting algorithm is obviously recursively undecidable. So this is not a well formed method. Incidentally while we are at it, consider the following sorting algorithm which is guaranteed to do the minimal number of comparisons under all circumstances: Step 1. Determine number of items to be sorted Step 2. Enumerate all binary decision trees for sorting this number of items. Step 3. Choose the decision tree with the minimum depth Step 4. Use this tree to sort the data