Path: utzoo!dptcdc!jarvis.csri.toronto.edu!mailrus!tut.cis.ohio-state.edu!ucbvax!ucsd!chem.ucsd.edu!tps
From: tps@chem.ucsd.edu (Tom Stockfisch)
Newsgroups: comp.lang.c
Subject: Re: Wanted: tricky algorithm
Message-ID: <444@chem.ucsd.EDU>
Date: 19 Apr 89 04:43:57 GMT
References: <749@acorn.co.uk> <1317@nusdhub.UUCP>
Reply-To: tps@chem.ucsd.edu (Tom Stockfisch)
Organization: Chemistry Dept, UC San Diego
Lines: 28

In article <1317@nusdhub.UUCP> rwhite@nusdhub.UUCP (Robert C. White Jr.) writes:
>in article <749@acorn.co.uk>, enevill@acorn.co.uk (Edward Nevill) says:
>> Does anyone have, or can anyone think of an algorithm to
>> do the above
  [basically, sort a bunch of strings w/o allocating any more
   memory, given that you have an array of pointers to the strings]
>>without using an auxiliary array and with a
>> fairly decent running order (ie < N*N).
 
>The clasic "heap sort" is an in-place sort useful for such things,
>though it wouoldn't be that useful here becuse you have an index into the
>memory in the form of your array of pointers....

You've got a bunch of STRINGS, i.e., ascii data.
There in a block of memory but spread all over the place.
You want them sorted and compacted.
You don't want to allocate any more memory.
You don't want to spend a ridiculous amount of time.

The solution:

Sort the pointers in place using qsort().
Write the strings out in order to a temporary file.
Read the temporary file back in starting at the base of your memory
unlink() the temporary.
-- 

|| Tom Stockfisch, UCSD Chemistry	tps@chem.ucsd.edu