# 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
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}
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, \$_) )
}
return 1;
}
my @list = (1, 2, 3, 4, 5, 6);
@list = do { shuffle @list } until inorder { \$_ <= \$_ } @list;
```

Or, for a deck of cards:

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