http://www.perlmonks.org?node_id=21095

Russ has asked for the wisdom of the Perl Monks concerning the following question: (sorting)

I need to sort a list of strings which are network line speeds, like:  "115kbps", "2Mbps", "10Mbps", "T1 LINE", ...

If I do the standard (ASCIIbetical) sort, "10Mbps" would come before "115kbps", and "115kbps" would come before "2Mbps", which is clearly not the result I want.

So I need some trick to make a "priority hash" or array where I'd put the proper order of sort.

I understand how to make comparisons in the subroutine:

return -1; # moves the item lower return +1; # goes above the previous one return 0; # equals

Originally posted as a Categorized Question.

Replies are listed 'Best First'.
Re: How do I write my own sorting routine?
by jarich (Curate) on Dec 22, 2003 at 05:57 UTC
    If you have a hash which specifies an ordering for values, then your sorting is much easier:
    my %hash = ( "very slow" => 1, "slow" => 2, "slowish" => 3, "medium" => 4, "acceptable" => 5, "fast" => 6, "very fast" => 7, );
    Now to sort, we just compare the array elements as keys into the hash:
    my @sorted = sort { $hash{$a} <=> $hash{$b} } @array;
    Hence:
    my @array = ("slow", "very fast", "fast", "very slow", "acceptable");
    would sort into:
    very slow, slow, acceptable, fast, very fast

      I believe the correct sorting should be
      my @sorted = sort { $hash{$a} <=> $hash{$b} } @array;
      Note the use of the 'spaceship' comparison operator instead of the cmp operator. The reason is that cmp compares the values based on string values, while <=> compares the values based on numerical values. So if your hash has values 1 to 10, the ordering with cmp produces 1,10,2,3,..., while ordering with <=> produces 1,2,3....,10.

Re: How do I write my own sorting routine?
by nardo (Friar) on Jul 05, 2000 at 22:38 UTC
    return -1 means $a goes before $b, return +1 means $b goes before $a, return 0 means they are equal.

    The "spaceship operator", <=>, returns -1, 0, or 1 depending on whether the left argument is numerically less than, equal to, or greater than the right argument.

    Its stringwise counterpart, cmp, returns -1, 0, or 1 depending on whether the left argument is stringwise less than, equal to, or greater than the right argument.

    To learn more about these operators, please read perlop.
    To learn more about the sort function, please read perlfunc.

Re: How do I write my own sorting routine?
by gam3 (Curate) on Mar 26, 2005 at 01:36 UTC
    This seems like it is begging for a schwartzian transform.
    my %engr_scale = ( k => 10**3, m => 10**6, g => 10**9, t => 10**12, ); sub normalized_net_speed { local $_ = lc shift; s/^T1\b/1.544 mbps/i; s/^([.0-9]+)\s*([kmgt])bps/ int( $1 * $engr_scale{lc $2} ) /e; s/[^.0-9].*$//; # kill non-numeric stuff $_ } my @sorted = map { $_->[0] } sort { $a->[1] <=> $b->[1] } map { [ $_, normalized_net_speed($_) ] } @array;

      I think the common practice of shoving the "key extraction" routine of the ST right into the first map scares away many a novice. There is no shame, especially if one aims to instruct, in writing something like:

      my $extract = sub { my $x = lc($_[0]); if ($x =~ s/^(\d+)\s*//) { $x = $1 * { mbps => 10**6, kbps => 10**3, bps => 10**0, }->{$x}; } else { $x = { 't1 line' => 100000 }->{$x}; } die "Bad input $_[0]" unless $x; return $x; }; my @sorted = map { $_->[0] } sort { $a->[1] <=> $b->[1] } map [ $_, $extract->( $_ ) ], @array;
      Once the code for the extraction routine is pulled out of the map/sort/map sequence what is left is not only very easy to follow, but, more importantly, it shows the essential structure of the ST, making it obvious that most of it is pretty generic. The most significant source of variation left is the nature of the sort routine, but with a well thought-out $extract function, the sort routine can often be reduced to the general form
      { $a->[1] <=> $b->[1] or $b->[2] <=> $a->[2] or $a->[3] cmp $b->[3] # ...compare as many sort keys as you please }

      Incidentally, it seems to me very much contrary to the spirit of the ST, a little perverse even, to have unnecessarily repetitious code in the extraction routine. The constant anonymous hashes:

      { mbps => 10**6, kbps => 10**3, bps => 10**0, }, { 't1 line' => 100000 }
      are created and destroyed anew with every iteration, for no good reason. Again, I see no reason not to simply write:
      my %lookup = ( mbps => 10**6, kbps => 10**3, bps => 10**0, 't1 line' => 100000 ); my $extract = sub { my $x = lc($_[0]); if ($x =~ s/^(\d+)\s*//) { $x = $1 * $lookup{ $x }; } else { $x = $lookup{ $x }; } die "Bad input $_[0]" unless $x; return $x; }; # etc.

      the lowliest monk

Re: How do I write my own sorting routine?
by poolpi (Hermit) on Jan 27, 2009 at 15:35 UTC
    #!/usr/bin/perl use strict; use warnings; use Data::Dumper; use Math::BigInt lib => 'GMP'; my @speeds = ( '10Mbps', '115kbps', 'Flash', '2Mbps', 'T1 LINE', 'Shocker' ); my ( @clean_speeds, @sorted_speeds ); my $speed_re = { 'BPS' => qr/(\d+)\s*([KMGT])BPS/, # 10MBPS 'T' => qr/T(\d)\s*\w*/, # T1 LINE }; my $bps = Math::BigInt->new('2')->bpow(10); my $unit = { 'BPS' => { K => $bps->copy->bpow(0), M => $bps->copy->bpow(1), G => $bps->copy->bpow(2), T => $bps->copy->bpow(3), }, # ref => http://ckp.made-it.com/t1234.html 'T' => { 1 => Math::BigInt->new('1544'), # T1 = 1544 kbps 2 => Math::BigInt->new('6312'), # T2 = 6312 kbps 3 => Math::BigInt->new('44736'), # T3 = 44736 kbps 4 => Math::BigInt->new('274760'), # T4 = 274760 kbps }, }; for (@speeds) { my $speed = uc $_; $speed =~ /(?:$speed_re->{'BPS'}|$speed_re->{'T'})/ ? push @clean_speeds, $speed : warn "Unmatched speed: $speed\n"; } @sorted_speeds = sort { net_speed($a) <=> net_speed($b) } @clean_speeds; print Dumper \@sorted_speeds; sub net_speed { my $speed = shift; if ( $speed =~ /$speed_re->{'BPS'}/ ) { Math::BigInt->new( $unit->{'BPS'}->{$2} )->bmul($1); } elsif ( $speed =~ /$speed_re->{'T'}/ ) { Math::BigInt->new( $unit->{'T'}->{$1} ); } } __END__ Output: ------ Unmatched speed: FLASH Unmatched speed: SHOCKER $VAR1 = [ '115KBPS', 'T1 LINE', '2MBPS', '10MBPS' ];
Re: How do I write my own sorting routine?
by St{)ìÑ (Initiate) on Oct 19, 2002 at 18:49 UTC
    Actually the best way to find out is to look at Learning Perl by O'REILLY Chapter 15, Strings and Sorting. This tells you how to change the default sorting into your custom sorting system. I understand the need to change from ASCIIbetical. It is a very odd sorting method.

    <STDIN>

    Originally posted as a Categorized Answer.