Re: Sorting on Section Numbers

[tye]

Pad all numeric parts before sorting:

my @sects= qw( 1 2 2.2 2.13 2.1.7 3.4a 10.1
    10.10 10.1a 1a.2 );
my $maxdigs= 4;
my %sects;
foreach my $sect (  @sects  ) {
    ( my $sort= $sect ) =~ s/(\d+)/
        sprintf "%0$maxdigs.$maxdigs"."d", $1 /ge;
    $sects{$sort}= $sect;
}
print join( " ", @sects{ sort keys %sects } ), "\n";

[chip]

Good approach! But you could simplify it a lot by noticing that your sprintf only prepends zeros:

my @sects= qw( 1 2 2.2 2.13 2.1.7 3.4a 10.1 10.10 10.1a 1a.2 );
my %sects;
for ( @sects ) {
    ( my $key = $_ ) =~ s/(\d+)/substr("0000$1",-4)/ge;
    $sects{$key} = $_;
}
print "@sects{sort keys %sects}\n";

Parameterizing on $maxdigs is left an an excercise for the acolyte. :-) (And extra credit if you knew that you could interpolate a hash slice.)

If we simplify the problem space by eliminating the alphanumerics, things get even neater--we don't even need a hash any more:

my @sorted = map { join '.', unpack 'N*', $_ }
             sort
             map { pack 'N*', split /\./ }
             @unsorted;

    -- Chip Salzenberg, Free-Floating Agent of Chaos

[tye]

You simplified it a lot by dropping $maxdigs. Put that back in and I doubt you'll have saved more than a keystroke or two. :) But thanks for the substr method; I like that.

substr("0000$1",-4)
sprintf"%04.4d",$1
substr("0"x$maxdigs.$1,-$maxdigs)
sprintf"%0$maxdigs.$maxdigs"."d",$1

When I saw the name chip, I wondered if it was you. Welcome to Perl Monks! I've run into your work many times and have been impressed.

If you know you don't need extra leading zeros, then you can also get away with:

grep{s/(^|\D)0+(\d)/$1$2/g,1} sort
grep{s/(\d+)/sprintf"%06.6d",$1/ge,1} @sects;

Man, I shouldn't attempt this much thinking before breakfast.

[chip]

You simplified it a lot by dropping $maxdigs.

It's a fair cop, but society's to blame.

I appreciate your final no-hash sprintf approach, but modifying temp values in a grep gives me the screaming heebie-jeebies, you know what I mean? I'd much rather use map for that sort of thing. But I can't argue with the fact that it works.... And my Rule #0 is, ``Anything that works is better than anything that doesn't.''

    -- Chip Salzenberg, Free-Floating Agent of Chaos

PS: Thanks for the welcome. This is a neat site.

[jimt]

There is a slight bug in this solution, it drops letters.
Using the above test data, the following list is generated:
1, 1.2, 2, 2.1.7, 2.2, 2.13, 3.4, 10.1, 10.1, 10.10
which dropped the letters from the section headings.
Here's my version:

@sorted = 
    map {$_->[0], ", "}
    sort {$a->[0] <=> $b->[0]}
    map {[$_, pack ("N*", $_)]}
    
@unsorted;


it works the same way, but I substituted in a Schwartzian transform to cache the original value of the heading instead of unpacking it again later. According to some tests with Benchmark, it's about 40% faster than doing the unpack later.
Plus it keeps letters intact.

[DrManhattan]

  @sorted = 
          map {$_->[0], ", "}
          sort {$a->[0] <=> $b->[0]}
          map {[$_, pack ("N*", $_)]}
          
  @unsorted;

For anyone who doesn't understand what the above code does, here are some nodes with explanations of the technique and some interesting discussion:

<list>
• Schwartzian Transform
• Sorting IP Addresses Quickly
• A Fresh Look at Efficient Perl Sorting (thanks davorg)

-Matt

[chip]

Of course that solution drops letters. That was the whole point, demonstrating that things get a lot simpler without them. Quoting myself:

If we simplify the problem space by eliminating the alphanumerics, things get even neater.

    -- Chip Salzenberg, Free-Floating Agent of Chaos

[turnstep]

> it works the same way, but I substituted in a Schwartzian transform to cache the original
> value of the heading instead of unpacking it again later. According to some tests with
> Benchmark, it's about 40% faster than doing the unpack later. Plus it keeps letters intact.

Unfortunately, there are two problems with this code:

@sorted = 
  map {$_->[0], ", "}
  sort { $a->[0] <=> $b->[0]}
  map {[$_, pack ("N*", $_)]}
@unsorted;

First, the map arguments should be reversed or the sort subscripts should be "1" not "0". As it is, all the code does is a simple sort, and ignores the whole pack part! Second, even when it is fixed, it does not quite sort correctly:

@unsorted = qw(2 1.2a 2.2 1.2 1.1a);
## A fixed version:
@sorted = 
  map {$_->[0], ", "}
  sort { $a->[1] <=> $b->[1]}
  map {[$_, pack ("N*", $_)]}
@unsorted;

print @sorted, "\n";
## produces:
1.2a, 1.1a, 1.2, 2, 2.2