Re: Anyone help develop an algorythm?

[stt@houdini.camb.inmet.com (Tucker Taft)]

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