Beefy Boxes and Bandwidth Generously Provided by pair Networks Bob
Don't ask to ask, just ask
 
PerlMonks  

Sorting Outline Numbers

by Anonymous Monk
on Aug 10, 2005 at 18:14 UTC ( #482696=perlquestion: print w/ replies, xml ) Need Help??
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.

Comment on Sorting Outline Numbers
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

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
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.

    Jeff japhy Pinyan, P.L., P.M., P.O.D, X.S.: Perl, regex, and perl hacker
    How can we ever be the sold short or the cheated, we who for every service have long ago been overpaid? ~~ Meister Eckhart

      Using sprintf to recreate the numbers would be rather more efficient:

      my @sorted = map sprintf('%vd', $_), sort map join('', map chr, split /\./), @data;

      Hugo

        Wow, I forgot entirely about that. I eschew the whole version-format idiom for numbers.

        Jeff japhy Pinyan, P.L., P.M., P.O.D, X.S.: Perl, regex, and perl hacker
        How can we ever be the sold short or the cheated, we who for every service have long ago been overpaid? ~~ Meister Eckhart
      using Sort::Key it becomes even simpler (and faster?):
      use Sort::Key qw(keysort); @sorted = keysort { join('', map chr, split /\./) } @data;
        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).

        Jeff japhy Pinyan, P.L., P.M., P.O.D, X.S.: Perl, regex, and perl hacker
        How can we ever be the sold short or the cheated, we who for every service have long ago been overpaid? ~~ Meister Eckhart
Re: Sorting Outline Numbers
by Fletch (Chancellor) 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

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.

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://482696]
Approved by davidrw
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others studying the Monastery: (6)
As of 2014-04-20 08:54 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    April first is:







    Results (485 votes), past polls