|
Anonymous Monk has asked for the wisdom of the Perl Monks concerning the following question:
I have a set of outline style numbers ( 1.0, 1.0.1, 1.0.2, 1.1, 2.0, 2.0.1, ... ) and I want to sort them. The decimal points separate tiers, not digits. Unfortunately, Perl wants to sort them wrong - placing 1.10.1 between 1.1 and 1.2, for example. And sorting with <=> doesn't work either because of the extra decimal points. Can anyone please suggest a way to sort these correctly? Also, I don't know how many tiers deep it will be, so I could have a number like 1.10.1.1.3 or something. |
Re: Sorting Outline Numbers
by japhy (Canon) on Aug 10, 2005 at 18:53 UTC
|
So long as the section numbers never go above 255, this should work fine:
my @sorted =
map join(".", map ord, split //),
sort
map join("", map chr, split /\./),
@data;
It turns "4.2.1" into a three-byte string made of characters \x04, \x02, and \x01. It compares the outline numbers as strings of this form, and then expands them back to their numeral form.
| [reply]
[d/l] |
|
|
my @sorted =
map sprintf('%vd', $_),
sort
map join('', map chr, split /\./),
@data;
Hugo | [reply]
[d/l] |
|
|
Wow, I forgot entirely about that. I eschew the whole version-format idiom for numbers.
| [reply] |
|
|
using Sort::Key it becomes even simpler (and faster?):
use Sort::Key qw(keysort);
@sorted = keysort { join('', map chr, split /\./) } @data;
| [reply]
[d/l] |
|
|
I'm assuming that's producing a Schwartzian Transform. The benefit of the Guttman-Rosler Transform (which I've employed) is that it uses 'sort' instead of 'sort { ... }'. However, speed really isn't an issue here (nor should it be).
| [reply] |
|
|
Re: Sorting Outline Numbers
by jimbojones (Friar) on Aug 10, 2005 at 18:34 UTC
|
Hi
You have to roll your own sort routine. The example below splits each number on the "." and compares them section-by-section. Something like
sub sect
{
my @a = split /\./, $a;
my @b = split /\./, $b;
my $len = @b;
if ( @a > @b )
{
$len = @a;
}
foreach my $i ( 0 .. $len-1 )
{
if ( $a[$i] > $b[$i] )
{
return 1;
}
elsif ( $a[$i] < $b[$i])
{
return -1;
}
}
return 0;
}
my @s = ( "1.0", "3", "2.0.1", "4.1.1.1", "1.0.1", "1.1", "1.0.2", "2.
+0" );
my @t = sort sect @s;
print "@t\n";
__DATA__
1.0 1.0.1 1.0.2 1.1 2.0 2.0.1 3 4.1.1.1
there are probably more efficient ways to do this.
- j | [reply]
[d/l] |
Re: Sorting Outline Numbers
by Fletch (Bishop) on Aug 10, 2005 at 18:57 UTC
|
Presuming you don't have more than 255 (or 16k for you Unicodians) levels in any one outline you could always convert into a character string and just sort on that (sort of like a radix sort).
use List::Util qw( max );
my @raw = qw( 1.3 2.3 2.1 2.0 2.0.3 1.2 2.0.2 1.0 );
my $longest = max map { my @c = split(/\./, $_); scalar @c } @raw;
my @sorted =
map { $_->[1] } sort { $a->[0] cmp $b->[0] }
map { my @c = split( /\./, +$_ );
push @c, ("0") x $longest - @c;
[ pack( "c*", @c ), $_ ] } @raw;
print join( "\n", @sorted ), "\n";
Update; Dang, japhy beat me. And the filling out to the same length's unnecessary; I don't know why I thought I needed to do that. Meh, need more caffeine.
--
We're looking for people in ATL
| [reply]
[d/l] |
Re: Sorting Outline Numbers
by davidrw (Prior) on Aug 10, 2005 at 18:52 UTC
|
may not be the prettiest w/ the nested maps, but this works for any number of tiers .. it converts the "1.10.4" to "00001.00010.00004" and sorts that, which will sort properly, and then converts back to strip the leading zeros. (Note the caveat that the '%05d' might need to be '%08d' or something.)
use strict;
use warnings;
my @s = ( "1.0", "1.10", "1.2", "3", "2.0.1", "4.1.1.1", "1.0.1", "1.1
+", "1.0.2", "2.0" );
my @t = map { join ".", map { sprintf '%d', $_ } split(/\./,$_) }
sort
map { join ".", map { sprintf '%05d', $_ } split(/\./,$_) }
@s;
print "IN: ", join(" ", @s), "\n";
print "OUT: ", join(" ", @t), "\n";
__END__
IN: 1.0 1.10 1.2 3 2.0.1 4.1.1.1 1.0.1 1.1 1.0.2 2.0
OUT: 1.0 1.0.1 1.0.2 1.1 1.2 1.10 2.0 2.0.1 3 4.1.1.1
| [reply]
[d/l]
[select] |
Re: Sorting Outline Numbers
by spiritway (Vicar) on Aug 11, 2005 at 01:23 UTC
|
How about converting those strings into ones in which leading zeroes are included, sort the strings, and then convert the strings back to the numerals as shown?
The following code is painful to see for Perl programmers. Forgive me. I don't yet speak Perlish very well.
#!/usr/bin/perl -w
#
use diagnostics;
use strict;
use warnings;
my @data= ( "1.1.2.3", "1.10.2.3", "1.10.2.3.1", "1.1.1.1.1.1.1", "1.1
+2", "1.0");
my $strg;
my @hold=();
my $element;
foreach $element (@data) {
@hold=split(/\./,$element);
$strg="";
foreach my $item (@hold) {
$strg.=sprintf("%03d.", $item);
}
$strg=substr($strg, 0, (length($strg)-1));
$element=$strg;
}
print "Unsorted:\n";
foreach $element (@data) {
print "$element\n";
}
@ data = sort {$a cmp $b} @data;
print "\n\nSorted\n";
foreach $element (@data) {
print "$element\n";
}
The output is:
Unsorted:
001.001.002.003
001.010.002.003
001.010.002.003.001
001.001.001.001.001.001.001
001.012
001.000
Sorted
001.000
001.001.001.001.001.001.001
001.001.002.003
001.010.002.003
001.010.002.003.001
001.012
A similar use of sprintf could be used to convert the numbers with leading zeroes back to ones that do not have leading zeroes. I leave this as an exercise for the reader, and to spare you gentle folks any more of my ugly code. | [reply]
[d/l]
[select] |
|
|
