[Gllug] [OT] sort algorithms

[Andrew Farnsworth]

In David's exact example, it works and as long as the identical numbers are
grouped together it works, however, if you intermix the
numbers (1,8,1,4,4,3,3,9,9) it will provide an incorrect sort, or at least
an ambiguous one.  In my code's case it will assume the correct order is
81439, which may be correct, or you might be expecting 18439, in which case
it is incorrect.

My code will correctly handle duplicates in the source data to be sorted
however.

Andy

On Tue, Nov 29, 2011 at 5:15 PM, Andrew Farnsworth <farnsaw at stonedoor.com>wrote:

> David has a good point, I don't think my code will work if there are
> duplicate values in your predefined list.
>
> Andy
>
>
> On Tue, Nov 29, 2011 at 5:13 PM, Andrew Farnsworth <farnsaw at stonedoor.com>wrote:
>
>> Presuming your predefined sequence is fixed or known prior to the sort
>> process, you can assign sequencial values to a hash when the keys are
>> the predefined values in the predefined order.  Then sort using a custom
>> sort on the values of the hash rather than the keys.  For example, in Perl,
>> you could do it this way.
>>
>> my @predefinedList = (1,5,8,4,3,6,9);
>> my %orderedHash;
>> my $order = 1;
>>
>> foreach my $key (@predefinedList)
>> {
>>     $orderedHash{$key} = $order++;
>> }
>>
>> my @unsortedList = (9,3,4,8,1);
>>
>> my @sortedList = sort {$orderedHash{$a} <=>
>> $orderedHash{$b}} @unsortedList;
>>
>> print "@sortedList\n";
>>
>> exit;
>>
>> Andy F
>>
>>
>> On Tue, Nov 29, 2011 at 4:34 PM, James Courtier-Dutton <
>> james.dutton at gmail.com> wrote:
>>
>>> Hi,
>>>
>>> I have a problem with a special sort I need to do.
>>> I have some ideas for an efficient solution, but I wished to ask if
>>> anyone else had a better idea.
>>> My current best solution is to do a transform on the source data using
>>> hash lookups on the predefined sequence.
>>> So the source data is changed into numbers that when sorted are in
>>> numerical order, do a normal numerical sort, and then repeat the
>>> inverse of the transform at the end.
>>>
>>> Problem is as follows.
>>> 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.
>>>
>>> Eg.
>>> Predefined sequence
>>> 1  5   8  4  3   6   9
>>>
>>> Source data
>>> 9 3 4 8 1
>>>
>>> Result
>>> 1 8 4 3 9
>>>
>>> Kind Regards
>>>
>>> James
>>> --
>>> 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/92467566/attachment.html>
-------------- next part --------------
--
Gllug mailing list  -  Gllug at gllug.org.uk
http://lists.gllug.org.uk/mailman/listinfo/gllug