Re: Anyone help develop an algorythm?

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

Matthew Givens (NKSW39B@prodigy.com) wrote:

: Okay, I have need for a special case sorting algorythm.  The best I've 
: come up with is a streamlined, modified bubble sort, but performance 
: isn't good enough, since I can have between 5000 and 15000 records.  
: Here's the situation:

: I have a linked list, each node corresponding to an array (contiguous in 
: memory) of fixed length strings.  The default size of each array is 100, 
: but that is user configurable and can change at run time.  So, call the 
: size of the S and the length of each string in the array L.  Also, call 
: the number of nodes in the linked list N.

: Now, I have to sort these multiple nodes as if the whole shebang was a 
: single, contiguous array.  The best I've been able to come up with is a 
: modified Bubble Sort using page number as part of the looping structure.  
: It looks a little weird, but it works.  Too slow, though.

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 ;-).

Alternatively, you might be able to use a heap sort to merge the
result of quick-sorting each array in the list.

: This algorythm is for work, and I have to have it operational by the end 
: of May.  Performance is a major consideration.

Then avoid bubble sort like the plague.

: Any suggestions are appreciated.

-Tucker Taft   stt@inmet.com   http://www.inmet.com/~stt/
Intermetrics, Inc.  Burlington, MA  USA