Wanted: tricky algorithm
Tom Stockfisch
tps at chem.ucsd.edu
Wed Apr 19 14:43:57 AEST 1989
In article <1317 at nusdhub.UUCP> rwhite at nusdhub.UUCP (Robert C. White Jr.) writes:
>in article <749 at acorn.co.uk>, enevill at 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 at chem.ucsd.edu
More information about the Comp.lang.c
mailing list