How do I do a natural sort on an array?

[Anonymous Monk]

How do I do a natural sort on an array? i.e. each array element is contains a string made up of numbers and letters.

Originally posted as a Categorized Question.

[tye]

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

See RE: RE: Re: Sorting on Section Numbers some important style comments.

Features and limitations:

• Strips extra leading zeros from digit strings
• Doesn't handle floating point numbers at all well
• Sorts negative integers in reverse after positive integers
• Uses very little extra memory
• You must specify the maximum number of digits your integers will have (6 in the above code)

[tye]

my %data;
foreach my $data (  @data  ) {
    ( my $sort= $data ) =~ s/(0*)(\d+)/
        pack("C",length($2)) . $1 . $2 /ge;
    $data{$sort}= $data;
}
my @sorted= @data{ sort keys %data };

Bugs and features
• Doesn't properly sort decimal values like 12.34
• Sorts negative integers in reverse after positive integers
• Requires more memory than other methods I'll be adding

[Dominus]

I'm not exactly sure what you want (it would have helped if you had provided an example) but here's what I use:

sub byfile {
  my @a = split /(\d+)/, $a;
  my @b = split /(\d+)/, $b;
  my $M = @a > @b ? @a : @b;
  my $res = 0;
  for (my $i = 0; $i < $M; $i++) {
    return -1 if ! defined $a[$i];
    return 1 if  ! defined $b[$i];
    if ($a[$i] =~ /\d/) {
      $res = $a[$i] <=> $b[$i];
    } else {
      $res = $a[$i] cmp $b[$i];
    }
    last if $res;
  }
  $res;
}

This may be more complicated than you need. Given the following:

53 7 119 53red
red5 red6 red7 red67 red6.jpg red12.jpg
green4.jpg
blue2.jpg blue1000.jpg blue2.jpg58

it produces the following output:

7
53
53red
119
blue2.jpg
blue2.jpg58
blue1000.jpg
green4.jpg
red5
red6
red6.jpg
red7
red12.jpg
red67

Lucs St. Louis also suggests:

 while (defined (my $A = shift @a) and defined (my $B = shift @b)) {
   $res = ($A =~ /\d/) ? $A <=> $B : $A cmp $B;
   return $res if $res;
 }
 return defined $A ? -1 : 1;

Hope this helps.

[salva]

Sort::Key::Natural is fast, can handle numbers of unlimited size and doesn't have problems with unicode:

use Sort::Key::Natural qw(natsort);
my @sorted = natsort @data;

[indigo]

@a = sort @b;

will sort lexigraphically.

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

will sort numerically.

@a = sort &naturally @b;

will sort "naturally", where naturally() is a compare routine of your own devising.

perldoc -f sort for more info.

[ihb]

You can use Sort::Naturally.

[Jammerwoch]

I wrote the following before finding the delightful Sort::Naturally library function. I recommend using that over what I've done, but maybe people are curious how it might be done. Or maybe someone needs to fine-tune or customize it.

The following code is not efficient. In particular, the calling of naturalSortInner with $a and $b as arguments completely eliminates the efficiency of having $a and $b. However, it was necessary for the recursive nature of naturalSortInner.

#!/usr/bin/perl

sub naturalSortInner {
    $x = uc( shift );
    $y = uc( shift );
    if( !($x =~ /\d+(\.\d+)?/) ) {
        return $x cmp $y;
    }
    $xBefore = $`;
    $xMatch = $&;
    $xAfter = $';
    if( !($y =~ /\d+(\.\d+)?/) ) {
        return $x cmp $y;
    }
    if( $xBefore eq $` ) {
        if( $xMatch == $& ) {
            return naturalSortInner( $xAfter, $' );
        } else {
            return $xMatch <=> $&;
        }
    } else {
        return $x cmp $y;
    }
    print "\n<before: '$xBefore', match: '$xMatch', after: '$xAfter'>\
+n";
}
sub naturalSort {
    naturalSortInner( $a, $b );
}


@arr = (
    'beta',
    'Alpha',
    'Gamma1',
    'Gamma',
    '23',
    '5',
    'Version1',
    'Version1.1',
    'Version1.2',
    'Version11.1-Sub1',
    'Version11.1-Sub10',
    'Version11.1-Sub3',
    'x23sub5',
    'Version2',
    'Version2.1',
    'GammaGlobulin',
    'Gamma10',
    'c',
    'Gamma2',
    'Gamma3',
);

print join( "\n", sort naturalSort @arr ) . "\n";