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:

Google Ads