Path: utzoo!attcan!uunet!ncrlnk!ncr-sd!hp-sdd!ucsdhub!isg100!nusdhub!rwhite
From: rwhite@nusdhub.UUCP (Robert C. White Jr.)
Newsgroups: comp.lang.c
Subject: Re: Wanted: tricky algorithm
Message-ID: <1317@nusdhub.UUCP>
Date: 17 Apr 89 19:29:05 GMT
References: <749@acorn.co.uk>
Organization: National University, San Diego
Lines: 35

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 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.  If you are going to
do anything in-place with the block of memory itself your strings
would need to be maximally aligned (e.g. alligned w.r.t. the longest
string.) and you would need one temporary holder string; then preform
a modified insertion-exchange: remove the string in lowest memory to
the temporary variable and adjust it's pointer; move the losest value
into the lowest (not vacant) slot; place the temporary back into the
space vacated by the exchange; advance the low water mark; repeat.
"back-pointers" from memory are helpful, but not necessary.

If you can approprate a large enough block of memory a sequential
copy using the indexing array will yeild a Big-O of N.  If you
don't have the memory but you do have the time, you could build a
memory image file (laid out as you would lay out the memory block
exactly) and then bulk-load the file back into place in memory.
This will also produce a big-O of N, but the elementary size of each
cycle is somewhat larger/slower because of the file opp.

You have, however piqued my curisoty, what do you need with the sorted
memory block while you have the pointer array.  I's not that I can't
think of a few reasons myself, but most of the ones that come to mind
first are rahter unlikely.

Rob.

Disclamer:  These opinions belong to no one; they are however 
copyrighted by a small corporation in the caman islands.  The
D.E.A. is investigating...