Re: Anyone help develop an algorythm?

[steved@pacifier.com (Steve Doiel)]

In article <E8yGpJ.Dyu@world.std.com>, bobduff@world.std.com says...
>
>In article <5jddg7$uf0@newssvr01-int.news.prodigy.com>,
>Matthew Givens <NKSW39B@prodigy.com> wrote:
>>I have a linked list, each node corresponding to an array (contiguous in 
>>memory) of fixed length strings. ...
>
>Perhaps you should construct an array on the side, containing pointers
>to all the strings.  Then sort that, using your favorite (fast) sorting
>algorithm.
>
>Constructing the array can be done in linear time.  You can walk the
>list once to determine the size of the array.  Or perhaps your program
>already knows the size.  Or perhaps it knows some reasonable upper bound
>on the size.  Then walk the list again, putting pointers to each string
>in the array.  (The strings need to be "aliased".)  Then do the sort.
>
>- Bob

Agreed... but with two notes:

  1) Check out the PAL to see if you can use an "off the shelf" sort... the
     last thing you should have to do is implement a sort _again_
     (what ever happened to software re-use?).

  2) The strings do not necesarily need to be aliased if each element in
     your array contains a pointer to the array and in index to the element,
     although the aliased approach is likely to be more efficient.

Steve Doiel