[Gllug] [OT] sort algorithms

David L Neil GLLUG at GetAroundToIt.co.uk
Tue Nov 29 22:36:38 UTC 2011


>>> Target pattern is a list of numbers in a certain predefined sequence.
>>> The source data is a set of numbers that is always a subset of the
>>> predefined sequence.
>>> I need a way to sort the source data so that the numbers appear in the
>>> same order as the predefined sequence.
>> What is the order of magnitude of the numbers in the source data set/in the
>> predefined sequence?
> Magnitude is the input/predefined sequence is between 0 and 2^32.  I.e
> 0 to MAXINT32


>> How large/small a proportion of the predefined sequence is/are the source
>> data set(s) likely to be?
> The source sequence will always be shorter than the predefined
> sequence. Source is a subset of the predefined sequence.

=understood from spec.

=a selection process is only likely to be more efficient than a sort as 
the size of the sample (source) approaches the size of the population 
(predefined sequence, or MAXINT32). Hence the question. Any idea of the 

>> Is each record in the source unique with respect to the number in the set or
>> may there be several with the same 'number',
>> eg result may be 1 1 8 8 4 4 3 3 9 9
> There should not be any duplicates in the source or predefined sequence.

=then efficient selection is possible...

Gllug mailing list  -  Gllug at gllug.org.uk

More information about the GLLUG mailing list