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] );