Path: utzoo!dptcdc!jarvis.csri.toronto.edu!mailrus!tut.cis.ohio-state.edu!rutgers!psuvax1!flee
From: flee@shire.cs.psu.edu (Felix Lee)
Newsgroups: comp.lang.c
Subject: Re: Wanted: tricky algorithm
Message-ID: <FLEE.89Apr16103712@shire.cs.psu.edu>
Date: 16 Apr 89 14:37:12 GMT
References: <749@acorn.co.uk>
Sender: news@psuvax1.cs.psu.edu
Organization: Penn State University Computer Science
Lines: 34
In-reply-to: enevill@acorn.co.uk's message of 13 Apr 89 18:02:31 GMT

In article <749@acorn.co.uk>,
   enevill@acorn.co.uk (Edward Nevill) wants
to reorder strings in a blob of memory according to a sorted array of
pointers to the strings, using constant memory.

The obvious algorithm (obvious to me, at least) runs in something like
O(n*n + n*m) time, where n is the number of strings and m is the size
of the blob of memory.

Given
  a[0 .. m-1] the blob of memory
  s[0 .. n-1] indexes into a[], referring to the strings
  l[0 .. n-1] the lengths of the strings

  // invariant: a[0 .. p-1] contains the strings s[0 .. i-1]
  //   in the right order
  p := 0
  for i in 0 .. n-1 do
    swap a[p .. s[i]-1], a[s[i] .. s[i]+l[i]]

    for j in i+1 .. n-1 do      // adjust the string pointers
      if s[j] < s[i] then s[j] := s[j] + l[i]

    s[i] := p; p := p + l[i]

Note that the "swap" exchanges unequal-sized segments.  This can be
done in place.

Less obvious algorithms are . . . less obvious.  I can't seem to come
up with any.  The amount of character swapping, O(n*m), feels like it
could be reduced by something suitably clever.  Maybe if the memory
constraint were relaxed a bit. . . .
--
Felix Lee	flee@shire.cs.psu.edu	*!psuvax1!shire!flee