Wikibooks

Algorithm Implementation/Sorting/Bogosort

< Algorithm Implementation | Sorting

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 algorithm

edit

Following is a description of the algorithm in pseudocode. 

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

Implementations in different programming languages

edit

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;
}

Java

edit 
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;
}

Lua

edit 
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

Perl 5

edit 
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 6

edit 
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;


Python

edit 
from random import *
from time import *
 
seed()
valeurs = []
for i in range(0, 10):
    valeurs.append(randint(0, 100))
 
def inorder(valeurs):
    i = 0
    j = len(valeurs)
    while i + 1 < j:
        if valeurs[i] > valeurs[i + 1]:
            return(False)
        i += 1
    return(True)
 
def bogo(valeurs):
    while not inorder(valeurs):
        shuffle(valeurs)
    return valeurs

start = time()
print("Before: ", valeurs)
valeurs = bogo(valeurs)
print("After: ", valeurs)
print("%.2f seconds" % (time() - start))

Ruby

edit 
class Array
  def bogosort!
    shuffle! until sorted?
  end

  def sorted?
    each_cons(2).all? { |a,b| a <= b }
  end
end

Scheme

edit 
(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)))

Smalltalk

edit 
|deck|

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

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

References

edit
edit
Retrieved from "https://en.wikibooks.org/w/index.php?title=Algorithm_Implementation/Sorting/Bogosort&oldid=3769231"