### bogo sort

########################
####   bogo sort    ####
########################

there are two variations
- (1) try all permutations of the input array of N elements, and check one by one till you find a sorted version. aka deterministic version.
- (2) shuffle the input array, and see if it is sorted.

- both unstable

(ref) https://en.wikipedia.org/wiki/Bogosort

##########################
####    complexity    ####
##########################

let's consider the deterministic version.

performance
- best case: O(n)          # when you get an already sorted list
- worst case: O((n+1)!)
- average case: O((n+1)!)

worst case: there are n! permutations, and you iterate the whole list (of N elems) at every permutation, so n! * n = (n+1)!

##################################
####  implementation example  ####
##################################

https://ja.wikipedia.org/wiki/%E3%83%9C%E3%82%B4%E3%82%BD%E3%83%BC%E3%83%88

taken from the above wiki article

--------------------------- // bogo_sort.pl
use List::Util 'shuffle';

sub is_sorted {
for my \$i (1 .. \$#_) {
return 0 if (\$_[\$i - 1] > \$_[\$i]);
}
return 1;

sub bogosort {
until (is_sorted(@_)) {
@_ = shuffle @_;
}
return @_;

--------------------------

--------------------------// bogo_sort.cpp
#include <algorithm>
#include <random>
template <class RandomIter>
void bogosort( RandomIter first, RandomIter last )

while( !std::is_sorted( first, last ) )
std::shuffle( first, last, std::default_random_engine() );

--------------------------

1. 2016-10-02 14:52:28 |
2. Category : algo
3. Page View: