Re: Anyone help develop an algorythm?

[jvl@ocsystems.com (Joel VanLaven)]

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.

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

: Any suggestions are appreciated.

I would be inclined to go with a merge sort (of some kind or other).  
Allow me to quote from Robert Sedgewick's _Algorithms_ (I highly
recommend this book).  "Mergesort is the method of choice for sorting
a linked list, where sequential access is the only kind of access
available."  It is quite simple, has O(NlogN) worst-case performance and
in your situation ought to require additional memory of at most 1 array
of strings (plus a teensy bit).  Of course sort each array by any method
you prefer (quicksort, heapsort, shellsort, or selection sort). 
 
Note that selection sort (still O(N^2)) is much better than bubble sort
and is "just as simple".  It would also be easy to apply to your 
situation (as the primary sort).  Basically, if you are really using
bubble sort, almost anything at all would be better.  Of course it might
be that you are not using what I call a buuble sort.

Hope that helps some.
-- 
-- Joel VanLaven