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 algorithm

Following is a description of the algorithm in pseudocode.

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

Implementations in different programming languages

C++

#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

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

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

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

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

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

class Array
  def bogosort!
    shuffle! until sorted?
  end

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

Scheme

(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

|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

• H. Gruber, M. Holzer and O. Ruepp: Sorting the Slow Way: An Analysis of Perversely Awful Randomized Sorting Algorithms, 4th International Conference on Fun with Algorithms, Castiglioncello, Italy, 2007, Lecture Notes in Computer Science 4475, pp. 183–197.
• Jargon File entry for bogo-sort, "the archetypal perversely awful algorithm"

External links

• http://c2.com/cgi/wiki?BogoSort
• Bogosort: an implementation that runs on Unix-like systems, similar to the standard sort program.
• Bogosort and jmmcg::bogosort: Simple, yet perverse, C++ implementations of the bogosort algorithm.