Sorting (All Sorts of Sorts)

From JmPm

Sorting

• Simple Sorts
• Orchish
• Schwartzian Transform
• Guttman Rosler Transform
• My example of sorting (which is not really ST)
• Modules
• Sort::Maker

Simple Sorts

• Sort Subroutines

• $a $b

• Routines that give < = > zero

• Numeric

 @sorted = sort {$a <=> $b} @unsorted 

• Descending

 @sorted = sort {$b cmp $a} @unsorted; 

• Case-insensitive

 @sorted = sort {lc $a cmp lc $b} @unsorted;

• Element-length sort:

 @sorted = sort {lenth $a <=> length $b} @unsorted;  

• Sort hash by value

@sorted = sort { $hash{$b} cmp $hash{$a} } @unsorted; 

• More complex functions

 @sorted = sort {
    (split ':', $a, 2)[0] cmp    split ':', $b, 2)[0]
 } @pw_lines; 

• Mutiple subkey sorts

@sorted = sort {
   &key1($a) cmp &key1($b)
           ||
   &key2($b) <=> &key2($a)
            ||
   &key3($a) cmp &key3($b)
}@unsorted

The Orcish Maneuver (OM)

 keys my %or_cache = @unsorted;
 @sorted = sort {
     ($or_cache{$a} ||= KEY($a))
     cmp
      ($or_cache{$b} ||= KEY($b))
     } @unsorted; 

The Schwartzian Transform

 @sorted = 
      map { $_->[0] } 
      sort { $a->[1] cmp $b->[1] } 
      map { [$_, foo($_)]
 } @unsorted; 

@sorted=
    map { pop @$_ }  
    sort{ $a->[0] <=> $b->[0] || $a->[1] cmp $b->[1] } 
    map { [tr/eE/eE/,$_] }
 @words; 

• First map the array to an array of arrays
• The inner array is [original,output of function]
• Then sort the second member of the inner array
• Then move the first part of the inner array to the sorted array

Guttman Rosler Transform (GRT)

my @sorted=map  { substr($_,4) }
 sort
 map  { pack("LA*",tr/eE/eE/,$_) } 
@words;

My Sort

@sub field is an aoa [char to sort by, rest of the data]

sort by the [0] place in each sub-array

letters come first then numbers (not like in ASCII)

lower case come before uppercase but are dispersed between the uppercase i.e. (aAbBcC....yYzZ0123456789)

sub by_subfield{
 unless ( $a->[2] cmp $b->[2]){ #falls through when it is the same letter or any number
    if ($a->[0] =~ /\d/){
    $a->[0] cmp $b->[0] ;#sort numbers normally
    }
    else {$b->[0] cmp $a->[0]#sort within each letter lc first(reverse of ASCII)
    }
 }
}
@sorted = map{$_->[0],$_->[1]} # get rid of helper field
   sort by_subfield
   map{[$_->[0],$_->[1],$_->[0]=~ /\d/ ?  '}' :lc($_->[0])]
[orig 0,orig 1,orig 0 as lowercase or '}' if it is a number because that is highest]
} @subfields;

Sort::Maker

• Sort style

my $plain_sorter = make_sorter( qw( plain ) ... ) ;

my $orcish_sorter = make_sorter( orcish => 1 ... ) ;

my $st_sorter = make_sorter( 'ST', 1, ... ) ;

my $GRT = make_sorter( 'GRT', ... ) ;

• Key attributes

ascending (default) descending

case (default) no_case

signed unsigned signed_float (default) unsigned_float fixed varying

Sort Pragma

• use sort 'stable'; # guarantee stability

• use sort '_quicksort'; # use a quicksort algorithm

• use sort '_mergesort'; # use a mergesort algorithm

• use sort 'defaults'; # revert to default behavior

• no sort 'stable'; # stability not important

• use sort '_qsort'; # alias for quicksort

my $current = sort::current(); # identify prevailing algorithm

References

• Programming Perl pp. 740,789
• Perl Cookbook pp138-143
• Perl Best Practices
• http://en.wikipedia.org/wiki/Schwartzian_transform
• http://www.perlmonks.org/?node=145659
• http://www.perlfect.com/articles/sorting.shtml
• http://sysarch.com/Perl/sort_paper.html
• http://perldoc.perl.org/functions/

• Map

%hash = map { getkey($_) => $_ } @array; 
 @words = map split, @phrases;

• Pack

pack TEMPLATE,LIST