Re: Anyone help develop an algorythm?

[dewar@merv.cs.nyu.edu (Robert Dewar)]

Matthew says

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

Ugh! bubble sort sounds, even modified as you say, sounds like a horrible
choice here. Have a look at the g-hesora or g-hesorg files in the GNAT
distribution for efficient sorts (this is a modified heapsort, using the
modification i developed in my thesis work 30 years ago, which halves
the number of comaprisons). It is setup with a procedural interface
that should be easy to adapt to your application.