PerlingTheUK has asked for the wisdom of the Perl Monks concerning the following question:

Hi all, I am looking for a way to sort times. my problem is that I do not always have a time available. I have a pre-sorted arrat that looks something like this: 
@ar = ( 1245, 1248, 0000, 1246, 1247 );

sort{ $a <=> $b } @ar;

[download]
would sort all values, returning ( 0000, 1245, 1246, ... ). I only wish to move larger numbers to the end, returning (1245,0000,1246,1247,1248). Writing a new sort algorithm would solve this, but I was wondering, if there is a way to teach sort to do so, and if this was possibly faster. Actually by pre-sorted I mean that all larger values simply need to be sorted upwards in the array, so 1248 will be at the end while in the end while the other values are in the right order already.

Replies are listed 'Best First'.
Re: Exceptional sorting
by Corion (Patriarch) on May 25, 2004 at 10:28 UTC

    Your "new" sort order is not unique, or I don't understand the criteria used to sort. I think I can find two possible orders for your example:

    1245 0000 1246 1247 1248
1245 1246 1247 1248 0000

    [download]

    Why is the second order not allowed? Is it because the 0000 was to the left of the 1246 ? If such is the case, I would make the elements so that they order "properly" by encoding them differently:

    1. Translate all elements by appending the "normal" marker. Let's define the "normal" marker as "n".
    2. For every element 0000n (a "normal 0"), replace that element by the element to the right of it, but omit the normal marker. In your example, the 0000n would become 1246.
    3. Let the normal Perl sort rip through your items.
    4. Convert all your items back to their old format.

    Depending on your actual needs (for example, times wrapping around the day border), it might be more convenient to first convert all your "numbers" into seconds since the 1. January 1970, and then sort the times.

[reply]
[d/l]
      > For every element 0000n (a "normal 0"), replace that element by the element to the right of it
      Do that only if the element to the right of it is not a '0000n' also.

      pelagic
[reply]
        Most would be 0000n.
[reply]
Re: Exceptional sorting
by Abigail-II (Bishop) on May 25, 2004 at 10:43 UTC
    How would you sort: 
        @ar = (1245, 1247, 0000, 1246, 1248)

    [download]
    Should 0000 remain between 1245 and 1246, or should it remain between 1247 and 1248? It can't do both.

    Abigail

[reply]
[d/l]
      0000 should remain between 1245 and 1246. 
       @ar = ( 1245, 0000, 1246, 1247, 1248 );

      [download]
      after sorting.
[reply]
[d/l]
        Why? Why not between 1247 and 1248? If you don't say why 0000 stays between certain numbers, I'd have to ask 120 questions to be able to sort a set of five numbers.

        Abigail

[reply]
Re: Exceptional sorting
by CountZero (Bishop) on May 25, 2004 at 10:21 UTC
    What's so special about '1245' that it should not be sorted?

    CountZero

    "If you have four groups working on a compiler, you'll get a 4-pass compiler." - Conway's Law

[reply]
      It is basically converting special events into a order, but some events are not to be timed at some stations so taking the presorted array from the last station, I know that an even occurs after an other event, even without having any timing for it available.
[reply]
        From your answer here and your other answers and comments I understand that there is a lot more data hidden behind these "times". In order to "sort" your data, this other information must also be taken into account.

        Without going into details (as I'm not sure you did already provide us with all necessary details), I think one has to think first about a representation of all of your data in some format, which later allows it to be easily "sorted" based upon the different properties of your data.

        CountZero

        "If you have four groups working on a compiler, you'll get a 4-pass compiler." - Conway's Law

[reply]
Re: Exceptional sorting
by pelagic (Priest) on May 25, 2004 at 14:12 UTC
    Although it is unclear (to me) whether this will solve your problem, here is a codelet for the sorting issue:
    use strict;

my @aa = qw/1245 1248 0000 1246 1247/;
my @c;
my %bb;

my $cnt = -1;
foreach my $tim (@aa) {
    ++$cnt;
    $bb{$cnt}{'time'}  = $tim;
    if ($tim == 0000) {
        for my $next_non_zero ($cnt + 1 .. scalar (@aa) -1) {
            next if ($aa[$next_non_zero] == 0000);
            $bb{$cnt}{'order'} = $aa[$next_non_zero];
            last;
        }
        if (! $bb{$cnt}{'order'}) {
            for my $last_non_zero (reverse 0 .. $cnt - 1) {
                next if ($aa[$last_non_zero] == 0000);
                $bb{$cnt}{'order'} = $aa[$last_non_zero];
                last;
            }
        }
        if (! $bb{$cnt}{'order'}) {
            $bb{$cnt}{'order'} = 0000;
        }
    }
    else {
        $bb{$cnt}{'order'} = $tim;
    }
}

foreach my $key ( sort {
                        $bb{$a}{'order'} <=> $bb{$b}{'order'}
                        ||
                        $bb{$a}{'time'} <=> $bb{$b}{'time'}
                       } keys %bb ) {
    push @c, $bb{$key}{'time'};
}

  
print "@aa\n";
print "@c\n";

__DATA__
1245 1248 0000 1246 1247
__OUTPUT__
1245 0000 1246 1247 1248
or
__DATA__
1245 1248 0000 1246 1247 0000
__OUTPUT__
1245 0000 1246 0000 1247 1248

    [download]

    pelagic
[reply]
[d/l]

Back to Seekers of Perl Wisdom