Sorting (All Sorts of Sorts)

From JmPm

Jump to: navigation, search

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

• Map 

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


• Pack

pack TEMPLATE,LIST

Retrieved from "http://jerusalempm.beamartyr.net/wiki/index.php/Sorting_(All_Sorts_of_Sorts)"