view release on metacpan or  search on metacpan

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

package Acme::Sort::Bogosort;

use 5.010;

use strict;
use warnings;

use parent qw/Exporter/;
use Carp 'croak';

use List::Util qw/shuffle/;

our @EXPORT = qw/bogosort/;

our $VERSION = '0.05';



#   bogosort()
#   Usage:
#   Sort a list in standard string comparison order.
#
#   my @sorted = bogosort( @unsorted );
#
#   Sort a list in ascending numerical order:
#   sub compare { return $_[0] <=> $_[1] };
#   my @sorted = bogosort( \&compare, @unsorted );
#
#   Warning: Average case is O( (e-1) * n! ).
#   Warning: Worst case approaches O(INF).
#
#   bogosort() is exported automatically upon use.

sub bogosort {
    my $compare = ref( $_[0] ) =~ /CODE/ 
        ?   shift
        :   \&compare;
    return @_ if @_ < 2;
    my @list = @_;
    @list = shuffle( @list ) while not is_ordered( $compare, \@list );
    return @list;
}



# Internal use, not exported.  Verifies order based on $compare->().
sub is_ordered {
    my ( $compare, $listref ) = @_;
    ref( $compare ) =~ /CODE/ 
        or croak "is_ordered() expects a coderef as first arg.";
    ref( $listref ) =~ /ARRAY/
        or croak "is_ordered() expects an arrayref as second arg.";
    foreach( 0 .. $#{$listref} - 1 ) {
        return 0 
            if $compare->( $listref->[ $_ ], $listref->[ $_ + 1 ] ) > 0;
    }
    return 1;
}

# Default compare() is ascending standard string comparison order.
sub compare {
    croak "compare() requires two args."
        unless scalar @_ == 2;
    return $_[0] cmp $_[1];
}


=head1 NAME

Acme::Sort::Bogosort - Implementation of a Bogosort (aka 'stupid sort' or 'slowsort').

=head1 VERSION

Version 0.05

=head1 SYNOPSIS

The Bogosort is a sort that is based on the "generate and test" paradigm.  It works by 
first testing whether the input is in sorted order.  If so, return the list.  But if not, 
randomly shuffle the input and test again.  Repeat until the shuffle comes back sorted.

    use Acme::Sort::Bogosort;

    my @unsorted = qw/ E B A C D /;
    my @ascending = bogosort( @unsorted );
    
    my @descending = bogosort(
        sub{ return $_[1] cmp $_[0]; },
        @unsorted
    );

The Bogosort has a worst case of O(INF), though as time approaches infinity the odds of not 
finding a solution decline toward zero (assuming a good random number generator).  The average 
case is O( (n-1) * n! ).  The n! term signifies how many shuffles will be required to obtain 
a sorted result in the average case.  However, there is no guarantee that any particular sort 
will come in anywhere near average.

Keep in mind that a list of five items consumes an average of 5!, or 120 iterations.  10! is 
3,628,800 shuffles.  Also keep in mind that each shuffle itself is an O(n-1) operation.  
Unless you need to heat a cold office with your processor avoid sorts on large data sets.

=head1 EXPORT

Always exports one function: C<bogosort()>.

=head1 SUBROUTINES/METHODS

=head2 bogosort( @unsorted )

Accepts a list as a parameter and returns a sorted list.

If the first parameter is a reference to a subroutine, it will be used as the