[Gllug] [OT] sort algorithms

[Andrew Farnsworth]

in perl it would be a simple test to see if the value existed in the hash
and drop if it does not, however, this would be separate from the sort but
still very simple and fast.

Andy

On Tuesday, November 29, 2011, James Courtier-Dutton <james.dutton at gmail.com>
wrote:
> On 29 November 2011 22:36, David L Neil <GLLUG at getaroundtoit.co.uk> wrote:
>> James,
>>
>>>>> 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
>>
>> =ouch!
>>
>>
>>>> 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
>> ratio?
>>
>>
>>>> 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...
>>
>
> I have just thought of an edge case. If values in the source do not
> appear in the predefined sequence, I wish them to be dropped.
> I was planning to do some filtering on the source data to pre-drop the
> values outside the predefined sequence, but if the sort algorithm can
> handle that at the same time, all the better.
> --
> Gllug mailing list  -  Gllug at gllug.org.uk
> http://lists.gllug.org.uk/mailman/listinfo/gllug
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.lug.org.uk/pipermail/gllug/attachments/20111129/06abe5dd/attachment.html>
-------------- next part --------------
--
Gllug mailing list  -  Gllug at gllug.org.uk
http://lists.gllug.org.uk/mailman/listinfo/gllug