Bogosort
From CodeCodex
[edit] Implementations
// This implementation does not do a full permutation between
// each comparison phase--it merely swaps two random elements.
// This does not change expected running time.
GET "LIBHDR"
LET SORTED(LIST, SIZE) =
VALOF $(
LET I
FOR I = 0 TO SIZE-2 DO
IF LIST!I > LIST!(I+1) THEN RESULTIS 0
RESULTIS 1
$)
// LIST = pointer to integer array, SIZE = size of array
LET BOGOSORT(LIST, SIZE) BE
$(
LET I, J, T
UNTIL (SORTED(LIST, SIZE)) DO
$(
I, J := RANDNO() REM SIZE, RANDNO() REM SIZE
T, LIST!I, LIST!J = LIST!I, LIST!J, T
$)
$)
#include <stdlib.h>
#include <string.h>
int isSorted(char **lines)
{
/* Array contains 0 or 1 strings, it's guaranteed to be sorted. */
if ((*lines == NULL) || (*(lines + 1) == NULL))
return 1;
lines++;
for ( ; *lines; lines++)
{
if (strcmp(*lines, *(lines-1)) < 0)
return 0;
}
return 1; /* True if nothing fails. */
}
size_t arrLen(char **lines)
{
int i=0;
for ( ; *lines; lines++, i++) ;
return i;
}
void shuffle(char **lines)
{
size_t length = arrLen(lines);
size_t randN;
size_t i;
char *temp;
for (i = 0; i < length; i++)
{
randN = rand() % length;
temp = lines[i];
lines[i] = lines[randN];
lines[randN] = temp;
}
}
void bogosort(char **lines)
{
while (!isSorted(lines))
shuffle(lines);
}
#include <algorithm>
#include <vector>
template<class T>
void bogosort(std::vector<T>& array)
{
while (! is_sorted(array))
{
std::random_shuffle(array.begin(), array.end());
}
}
template<class T>
bool is_sorted(const std::vector<T>& array)
{
for (typename std::vector<T>::size_type i = 1; i < array.size(); ++i)
{
if (array[i] < array[i-1])
{
return false;
}
}
return true;
}
//Sorts an integer array in ascending order.
//Notice that the array passed must not be a null reference.
//Parameters:
// data - the integer array to sort
//Postcondition:
// The array is sorted in ascending order.
//Warning:
// Due to the finite number of random sequences used by
// java.util.Random it is possible that the execution
// of this code will result in an infinite loop.
import java.util.Random;
public class BogoSort
{
private static final Random generator = new Random();
public static void bogoSort(int[] data)
{
while (!isSorted(data)) {
for (int i = 0; i < data.length; i++){
int randomPosition = generator.nextInt(data.length);
int temp = data[i];
data[i] = data[randomPosition];
data[randomPosition] = temp;
}
}
}
private static boolean isSorted(int[] data)
{
for (int i = 1; i < data.length; i++)
if (data[i] < data[i - 1])
return false;
return true;
}
}
use List::Util 'shuffle'; # perldoc -q shuffle
sub is_sorted {
for (1 .. $#_) {
return if $_[$_ - 1] > $_[$_];
}
return 1;
}
sub bogosort {
@_ = shuffle @_ until is_sorted @_;
@_
}
print bogosort qw(2 1 3);
function issorted($list)
{
$cnt = count($list);
for($j = 1; $j < $cnt; $j++)
{
if($list[$j-1] > $list[$j])
return false;
}
}
return true;
}
function bogosort($list)
{
do
{
shuffle($list);
}
while(!issorted($list));
return $list;
}
[edit] Python
from random import shuffle
from itertools import izip
def step(it):
it.next()
return it
def adjacents(seq):
return izip(iter(seq), step(iter(seq)))
def is_sorted(seq):
return len(seq) < 2 or all(a <= b for a, b in adjacents(seq))
def bogosort(lines):
while not is_sorted(lines):
shuffle(lines)
return lines
def sorted?(list)
list.each_cons(2).all?{|a,b|a<=b}
end
def bogosort(list)
list = list.dup
list.shuffle! until sorted?(list)
list
end
