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: stt@houdini.camb.inmet.com (Tucker Taft) Subject: Re: Anyone help develop an algorythm? Date: 1997/04/23 Message-ID: #1/1 X-Deja-AN: 236833290 Sender: news@inmet.camb.inmet.com (USENET news) X-Nntp-Posting-Host: houdini.camb.inmet.com References: <5jjtaj$1e9e@newssvr01-int.news.prodigy.com> Organization: Intermetrics, Inc. Newsgroups: comp.lang.ada Date: 1997-04-23T00:00:00+00:00 List-Id: Matthew Givens (NKSW39B@prodigy.com) wrote: : stt@houdini.camb.inmet.com (Tucker Taft) wrote: : > : >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? "The Handbook of Algorithms and Data Structures in Pascal and C" Second Edition, G.H. Gonnet, R. Baeza-Yates, Addison-Wesley, look for "Quick Sort on Lists" in the table of contents. You can also derive the algorithm yourself if you understand how "normal" Quick Sort works. For your case of a list of arrays, I suspect you could create a hybrid of "normal" Quick Sort and a linked-list version. The requirements of Quick Sort are an ability to iterate though any partition of an array, and to make exchanges. If your iteration "cursor" consists of a pointer to the "current" array, and an index into the current array, and a partition were represented by two such cursors, then I believe you could use the basic Quick Sort algorithm relatively straightforwardly. -Tucker Taft stt@inmet.com http://www.inmet.com/~stt/ Intermetrics, Inc. Burlington, MA USA