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.3 required=5.0 tests=BAYES_00,INVALID_MSGID autolearn=no autolearn_force=no version=3.4.4 X-Google-Language: ENGLISH,ASCII-7-bit X-Google-Thread: 103376,50880f040eb869b4 X-Google-Attributes: gid103376,public From: dewar@merv.cs.nyu.edu (Robert Dewar) Subject: Re: Anyone help develop an algorythm? Date: 1997/04/23 Message-ID: #1/1 X-Deja-AN: 237067013 References: <5jddg7$uf0@newssvr01-int.news.prodigy.com> <5jjtaj$1e9e@newssvr01-int.news.prodigy.com> Organization: New York University Newsgroups: comp.lang.ada Date: 1997-04-23T00:00:00+00:00 List-Id: <<>There is a variant of quick-sort that works on linked lists. >The trick is to use the first element in the list as the "pivot" and >then build up two new linked lists containing the left and right partitions, >and then recurse as usual. I would think this could be generalized >to handle a linked list of arrays (left as an exercise to the reader ;-). Could you give me a reference (or two) where I might be able to find the Quick Sort variation you mentioned? >> This is not quick sort at all. The essence of quick sort is the in place exchange -- otherwise you are just talking about a simple recursive sort, known for a long time before quicksort was published by Hoare. The algorithm is trivial enough, just form two lists one of elements greater than the pivot, one of elements less than the pivot, and then recursively sort both lists and append one to the other. However, this algorithm is NEVER preferable to a straight 2-way merge sort, since its average behavior is the same, and its worst case performance is quadratic. The only reasonable way to sort a list is with a two way merge sort. Divide the list into equal parts, sort each sublist recurs9ively, and then do a 2-way merge to form the result. This sort is average and worst case NlogN, is easy to program, and has no disadvatanges over other methods that I can see.