Jump to content

Algorithm Implementation/Sorting/Bogosort

Add links
From Wikibooks, open books for an open world

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 | edit source]

Following is a description of the algorithm in pseudocode. 

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

Implementations in different programming languages

[edit | edit source]

C++

[edit | edit source]
#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 | edit source]
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 | edit source]
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 | edit source]
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 | edit source]
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 | edit source]
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 | edit source]
class Array
  def bogosort!
    shuffle! until sorted?
  end

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

Scheme

[edit | edit source]
(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 | edit source]
|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 source]
[edit | edit source]
Retrieved from "https://en.wikibooks.org/w/index.php?title=Algorithm_Implementation/Sorting/Bogosort&oldid=3769231"