view release on metacpan or  search on metacpan

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

        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
comparison function.

The Bogosort is probably mostly useful as a teaching example of a terrible sort 
algorithm.  There are approximately 1e80 atoms in the universe.  A sort list of 
59 elements will gain an average case solution of 1e80 iterations, with a worst 
case approaching infinite iterations to find a solution.  Anything beyond just a 
few items takes a considerable amount of work.

Each iteration checks first to see if the list is in order.  Here a comparatively 
minor optimization is that the first out-of-order element will short-circuit the 
check.  That step has a worst case of O(n), and average case of nearly O(1).  
That's the only good news.  Once it is determined that the list is out 
of order, the entire list is shuffled (an O(n) operation).  Then the test happens 
all over again, repeating until a solution is happened across by chance.

There is a potential for this sort to never finish, since a typical random number
synthesizer does not generate an infinitely non-repeating series.  Because this 
algorithm has the capability of producing O(INF) iterations, it would need an 
infinite source of random numbers to find a solution in any given dataset.  

Small datasets are unlikely to encounter this problem, but as the dataset grows, 
so does the propensity for running through the entire set of pseudo-random numbers 
generated by Perl's rand() for a given seed.  None of this really matters, of course, 
as no sane individual would ever use this for any serious sorting work.

Not every individual is sane.

=cut