Algorithm Implementation/Sorting/Bogosort

The algorithm bogosort (also random sort, shotgun sort or monkey sort) is a particularly ineffective sorting algorithm. Its only use is for educational purposes, to contrast it with other more realistic algorithms. If bogosort were used to sort a deck of cards, it would consist of checking if the deck were in order, and if it were not, one would throw the deck into the air, pick the cards up at random, and repeat the process until the deck is sorted. Its name comes from the word bogus.

Description of the algorithmEdit

Following is a description of the algorithm in pseudocode.

while not inOrder(deck) do
    shuffle(deck);

Implementations in different programming languagesEdit

PythonEdit

from random import shuffle
 
# Bogo-sort deck in place
while not all(x <= y for x, y in zip(deck, deck[1:])):
    shuffle(deck)

RubyEdit

class Array
  def bogosort!
    shuffle! until sorted?
  end
 
  def sorted?
    each_cons(2).all? { |a,b| a <= b }
  end
end

Perl 5Edit

use List::Util qw{shuffle};
sub inorder (&@) {
  my $sub = shift;
  while (scalar(@_) > 1) {
        return unless ( $sub->(shift, $_[0]) )
  }
  return 1;
}
my @list = (1, 2, 3, 4, 5, 6);
@list = do { shuffle @list } until inorder { $_[0] <= $_[1] } @list;

Or, for a deck of cards:

use List::Util qw{shuffle};
sub inorder (&@) {
  my $sub = shift;
  while (scalar(@_) > 1) {
        return unless ( $sub->(shift, $_[0]) )
  }
  return 1;
}
my @list = qw{2 3 4 5 6 7 8 9 A J K Q};
@list = do { shuffle @list } until inorder { $_[0] le $_[1] } @list;

Perl 6Edit

my @list = 1, 2, 3, 4, 5, 6;
@list .= pick(*) until [<=] @list;

Or, for a deck of cards:

my @deck = <2 3 4 5 6 7 8 9 A J K Q>;
@deck .= pick(*) until [le] @deck;

JavaEdit

    import java.util.*;
 
    public void bogoSort(List<Integer> deck) {
        while(!isInOrder(deck)) {
            Collections.shuffle(deck);
        }
    }
 
    public boolean isInOrder(List<Integer> deck) {
        for (int i = 0; i < deck.size() - 1; i++) {
            if (deck.get(i) > deck.get(i+1)) return false;
        }
        return true;
    }

LuaEdit

function is_sorted(t)
    local last_v = t[1]
    local current_v
    for i = 2, #t do
        current_v = t[i]
        if last_v > current_v then
            return false
        end
        last_v = current_v
    end
    return true -- if the length of the table is 1, it will return as if it is sorted
end
 
function bogosort(t)
    while not is_sorted(t) do
        local nt = {t[1]}
        for i = 2, #t do
            table.insert(nt, math.random(1, #nt), t[i])
        end
        t = nt
    end
    return t
end

SchemeEdit

(define (bogosort to-sort)
  (cond
    ((list? to-sort) (vector->list (bogosort (list->vector to-sort))))
    ((sorted? to-sort) to-sort)
    (else (bogosort (shuffle to-sort)))))
 
(define (sorted? to-sort)
  (define (check-index-and-next n)
    (or (>= n (- (vector-length to-sort) 1))
        (and (<= (vector-ref to-sort n) (vector-ref to-sort (+ 1 n)))
             (check-index-and-next (+ n 1)))))
  (check-index-and-next 0))
 
(define (shuffle deck)
  (define (set-index-to-random n)
    (if (< n 1)
      deck
      (begin 
        (let ((rand (random (+ 1 n)))
              (val-at-n (vector-ref deck n)))
          (vector-set! deck n (vector-ref deck rand))
          (vector-set! deck rand val-at-n))
        (set-index-to-random (- n 1)))))
  (set-index-to-random (- (vector-length deck) 1)))

SmalltalkEdit

|deck|
 
deck := (1 to:10) asArray randomShuffle.
[ deck isSorted ] whileFalse:[
    deck randomShuffle
]

C++Edit

 #include <iostream>
 #include <ctime>
 #include <cstdlib>
 #include <vector>
 #include <algorithm>
 #include <iterator>
 
 using namespace std;
 static const int NUM = 7;
 
 bool IsInOrder(const vector<int>& x)
 {
 	return adjacent_find(x.begin(), x.end(), greater<int>()) == x.end();
 }
 
 int main()
 {
 	int counter = 0;
 	srand(time(0));
 	vector<int> bogo;
 
 	// Initiate the vector with NUM random numbers
 	generate_n(back_inserter(bogo), NUM, rand);
 
 	// Bogosort
 	while(!IsInOrder(bogo))
 	{
 		random_shuffle(bogo.begin(), bogo.end());
 		copy(bogo.begin(), bogo.end(), ostream_iterator<int>(cout, " "));
 		cout << "\n\n";
 		counter++;
 	}
 	cout << "Sorting took " << counter << " tries." << endl;
 }


Various other implementations in C++ are available, including an STL-style algorithm, which was inspired by discussions on the ACCU General mailing list.

ReferencesEdit

External linksEdit

Last modified on 11 October 2013, at 13:22