view release on metacpan or  search on metacpan

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

package Acme::Sort::Bozo;

use 5.010;

use strict;
use warnings;

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

use List::Util qw/shuffle/;

our @EXPORT = qw/bozo/;

our $VERSION = '0.05';



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

sub bozo {
    my $compare = ref( $_[0] ) =~ /CODE/ 
        ?   shift
        :   \&compare;
    return @_ if @_ < 2;
    my $listref = [ @_ ]; # Get a ref to a copy of @_.
    $listref = swap( $listref ) while not is_ordered( $compare, $listref );
    return @{ $listref };
}



# 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;
}

# Internal use, not exported.  Simply swaps two random elements.  The elements
# are guaranteed to be distinct.
sub swap {
    my $listref = shift;
    my $elements = @{$listref};
    my $first = int( rand( $elements ) );
    my $second;
    do{ $second = int( rand( $elements ) ); } until $second != $first;
#    ( $listref->[$first], $listref->[$second] ) = ( $listref->[$second], $listref->[$first] );
    @{$listref}[$first, $second] = @{$listref}[$second, $first];
    return $listref;
}


# 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::Bozo - Implementation of a Bozo sort algorithm.

=head1 VERSION

Version 0.05

=head1 SYNOPSIS

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

    use Acme::Sort::Bozo;

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

The worst case for Bozo is difficult to determine, though one study suggests it probably approaches O(INF).
The good news is that, as time (and computation) approaches infinity the odds of not finding a solution decline 
toward zero (assuming a good random number generator).  So if you have an eternity to wait, you'll get your 
results soon enough.  The average case is O( n * n! ).  However, there is no 
guarantee that any particular sort will come in anywhere near average.  Where the bogosort is a 'stateless'
sort, the bozo sort maintains a list state from one iteration to the next, but its decision mechanism for swaps I<is>
stateless; it blindly swaps any random two elements.

Keep in mind that a list of five items consumes an average of 5 * 5!, or 600 iterations.  10! is 
36,288,000 iterations on average.  The universe will either collapse or expand to the point that it cannot sustain
life long before the Bozo sort manages to sort a deck of cards, in the average case.  In the worst case, all of the
background radiation from our universe will have decayed to the point that there is no longer any trace of our 
existence before this sort manages to alphabetically sort your social networking friends list.

Test with short (4 to 7 element) lists, and be prepared to kill the process if you mistakenly hand it more elements
than that.

=head1 EXPORT

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

=head1 SUBROUTINES/METHODS