view release on metacpan or  search on metacpan

lib/Acme/Rautavistic/Sort.pm  view on Meta::CPAN

package Acme::Rautavistic::Sort;
BEGIN {
  $Acme::Rautavistic::Sort::AUTHORITY = 'cpan:SCHWIGON';
}
# ABSTRACT: Rautavistic sort functions

use warnings;
use strict;
use 5.006;

our $VERSION = '0.02';

use Scalar::Util 'reftype';
require Exporter;

use vars qw(@ISA @EXPORT_OK %EXPORT_TAGS);

@ISA = qw(Exporter);

@EXPORT_OK   = qw(dropsort dropsortx);
%EXPORT_TAGS = (all => [ qw(dropsort dropsortx) ]);

sub dropsort {
        no warnings 'uninitialized';
        my $last;
        map { $_ ge $last ? $last = $_ : () } @_;
}

sub dropsortx(&@)
{
        # magic variables $a and $b
        use vars qw($a $b);
        no strict 'refs';
        no warnings 'uninitialized';
        my $caller = caller;
        local(*{$caller."::a"}) = \my $a;
        local(*{$caller."::b"}) = \my $b;

        my $comparator = shift;
        my $last;
        map {
             $a = $_;
             $b = $last;
             $comparator->() >= 0 ? $last = $_ : ()
            } @_;
}

1; # End of Acme::Rautavistic::Sort

# TODOs / Ideas:
#   Attribute : Rautavistic(dropsort)
#    an Arrays, always keep dropsort sort order, after each change on array

__END__

=pod

=encoding UTF-8

=head1 NAME

Acme::Rautavistic::Sort - Rautavistic sort functions

=head1 SYNOPSIS

 use Acme::Rautavistic::Sort ':all';
 #
 # default alphanumeric comparison
 @res = dropsort( qw(3 2 3 1 5) );      # qw(3 3 5)
 @res = dropsort( qw(cc bb dd aa ee) ); # qw(cc dd ee)
 #
 # force numeric comparison (or other comparators)
 @res = dropsortx { $a <=> $b } 1, 11, 2;

=head1 DESCRIPTION

This module provides rautavistic sort functions. For more description
of the functions see below.

=head2 dropsort

From http://www.dangermouse.net/esoteric/dropsort.html:

Dropsort is a fast, one-pass sorting algorithm suitable for many
applications.

Algorithm Description Dropsort is run on an ordered list of numbers by
examining the numbers in sequence, beginning with the second number in
the list. If the number being examined is less than the number before
it, drop it from the list. Otherwise, it is in sorted order, so keep
it. Then move to the next number.

After a single pass of this algorithm, the list will only contain
numbers that are at least as large as the previous number in the
list. In other words, the list will be sorted!  Analysis Dropsort
requires exactly n-1 comparisons to sort a list of length n, making
this an O(n) algorithm, superior to the typical O(n logn) algorithms
commonly used in most applications.

Dropsort is what is known in the computer science field as a lossy
algorithm. It produces a fast result that is correct, but at the cost