Bogosort

From CodeCodex

Related content:

Implementations[edit]

BCPL[edit]

// 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
    $)
$)

C[edit]

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

C++[edit]

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

Java[edit]

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

Perl[edit]

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

PHP[edit]

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

Python[edit]

 
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

Ruby[edit]

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