[Gllug] [OT] sort algorithms

[Philip Hands]

On Tue, 29 Nov 2011 22:29:16 +0000, James Courtier-Dutton <james.dutton at gmail.com> wrote:
...
> The source sequence will always be shorter than the predefined
> sequence. Source is a subset of the predefined sequence.
...
> There should not be any duplicates in the source or predefined sequence.

If you've got enough memory for the sequence in memory a few times over,
plus 512MB, then you could build an array that uses the sequence numbers
as indices and their position in the sequence as values.

Then you allocate enough ram to act as a bitmap of all the MAXINT
numbers (which I calculate as is 512MB) -- you can probably optimise
that, but if you've got the RAM, why bother.

Then, starting with a bitmap of zeros, you run through the list, looking
up the ordinal of each number you find, and set that bit in the bitmap.

When you're done, walk through the bitmap and the sequence, and spit out
a number from the sequence whenever you find a set bit in the bitmap.

Job done (I think :-)

Cheers, Phil.
-- 
|)|  Philip Hands [+44 (0)20 8530 9560]    http://www.hands.com/
|-|  HANDS.COM Ltd.                    http://www.uk.debian.org/
|(|  10 Onslow Gardens, South Woodford, London  E18 1NE  ENGLAND
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 851 bytes
Desc: not available
URL: <http://mailman.lug.org.uk/pipermail/gllug/attachments/20111130/dddc1c2e/attachment.pgp>
-------------- next part --------------
--
Gllug mailing list  -  Gllug at gllug.org.uk
http://lists.gllug.org.uk/mailman/listinfo/gllug