From mboxrd@z Thu Jan  1 00:00:00 1970
X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me
X-Spam-Level: 
X-Spam-Status: No, score=-1.3 required=5.0 tests=BAYES_00,INVALID_MSGID
	autolearn=no autolearn_force=no version=3.4.4
X-Google-Language: ENGLISH,ASCII-7-bit
X-Google-Thread: 103376,50880f040eb869b4
X-Google-Attributes: gid103376,public
From: steved@pacifier.com (Steve Doiel)
Subject: Re: Anyone help develop an algorythm?
Date: 1997/04/22
Message-ID: <5jhae2$l62$1@news.pacifier.com>#1/1
X-Deja-AN: 236483504
References: <5jddg7$uf0@newssvr01-int.news.prodigy.com>
 <E8yGpJ.Dyu@world.std.com>
Organization: Pacifier BBS, Vancouver, Wa.  ((360) 693-0325)
Newsgroups: comp.lang.ada
Date: 1997-04-22T00:00:00+00:00
List-Id: <comp.lang.ada>



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