Sorting algorithms/Bogosort

From Rosetta Code
Jump to: navigation, search
Task
Sorting algorithms/Bogosort
You are encouraged to solve this task according to the task description, using any language you may know.

Sorting Algorithm
This is a sorting algorithm. It may be applied to a set of data in order to sort it.

For other sorting algorithms, see Category:Sorting Algorithms, or:
O(n logn) Sorts
Heapsort | Mergesort | Quicksort
O(n log2n) Sorts
Shell Sort
O(n2) Sorts
Bubble sort | Cocktail sort | Comb sort | Gnome sort | Insertion sort | Selection sort | Strand sort
Other Sorts
Bead sort | Bogosort | Counting sort | Pancake sort | Permutation sort | Radix sort | Sleep sort | Stooge sort
Bogosort a list of numbers.

Bogosort simply shuffles a collection randomly until it is sorted.

"Bogosort" is a perversely inefficient algorithm only used as an in-joke. Its average run-time is O(n!) because the chance that any given shuffle of a set will end up in sorted order is about one in n factorial, and the worst case is infinite since there's no guarantee that a random shuffling will ever produce a sorted sequence. Its best case is O(n) since a single pass through the elements may suffice to order them.

Pseudocode:

while not InOrder(list) do
   Shuffle(list)
done

The Knuth shuffle may be used to implement the shuffle part of this algorithm.

Contents

[edit] ActionScript

public function bogoSort(arr:Array):Array
{
while (!sorted(arr))
{
shuffle(arr);
}
 
return arr;
}
 
public function shuffle(arr:Array):void
{
for (var i:int = 0; i < arr.length; i++)
{
var rand:int = Math.floor(Math.random() * arr.length);
var tmp:* = arr[i];
arr[i] = arr[rand];
arr[rand] = tmp;
}
}
 
public function sorted(arr:Array):Boolean
{
var last:int = arr[0];
 
for (var i:int = 1; i < arr.length; i++)
{
if (arr[i] < last)
{
return false;
}
 
last = arr[i];
}
 
return true;
}

[edit] Ada

with Ada.Text_IO;  use Ada.Text_IO;
with Ada.Numerics.Discrete_Random;
 
procedure Test_Bogosort is
generic
type Ordered is private;
type List is array (Positive range <>) of Ordered;
with function "<" (L, R : Ordered) return Boolean is <>;
procedure Bogosort (Data : in out List);
 
procedure Bogosort (Data : in out List) is
function Sorted return Boolean is
begin
for I in Data'First..Data'Last - 1 loop
if not (Data (I) < Data (I + 1)) then
return False;
end if;
end loop;
return True;
end Sorted;
subtype Index is Integer range Data'Range;
package Dices is new Ada.Numerics.Discrete_Random (Index);
use Dices;
Dice : Generator;
procedure Shuffle is
J  : Index;
Temp : Ordered;
begin
for I in Data'Range loop
J := Random (Dice);
Temp := Data (I);
Data (I) := Data (J);
Data (J) := Temp;
end loop;
end Shuffle;
begin
while not Sorted loop
Shuffle;
end loop;
end Bogosort;
 
type List is array (Positive range <>) of Integer;
procedure Integer_Bogosort is new Bogosort (Integer, List);
Sequence : List := (7,6,3,9);
begin
Integer_Bogosort (Sequence);
for I in Sequence'Range loop
Put (Integer'Image (Sequence (I)));
end loop;
end Test_Bogosort;

The solution is generic. The procedure Bogosort can be instantiated with any copyable comparable type. In the example given it is the standard Integer type.

Output:
 3 6 7 9

[edit] ALGOL 68

Translation of: python
Works with: ALGOL 68 version Standard - no extensions to language used
Works with: ALGOL 68G version Any - tested with release mk15-0.8b.fc9.i386
Works with: ELLA ALGOL 68 version Any (with appropriate job cards) - tested with release 1.8.8d.fc9.i386
MODE TYPE = INT;
 
PROC random shuffle = (REF[]TYPE l)VOID: (
INT range = UPB l - LWB l + 1;
FOR index FROM LWB l TO UPB l DO
TYPE tmp := l[index];
INT other := ENTIER (LWB l + random * range);
l[index] := l[other];
l[other] := tmp
OD
);
 
PROC in order = (REF[]TYPE l)BOOL: (
IF LWB l >= UPB l THEN
TRUE
ELSE
TYPE last := l[LWB l];
FOR index FROM LWB l + 1 TO UPB l DO
IF l[index] < last THEN
GO TO return false
FI;
last := l[index]
OD;
TRUE EXIT
return false: FALSE
FI
);
 
PROC bogo sort = (REF[]TYPE l)REF[]TYPE: (
WHILE NOT in order(l) DO
random shuffle(l)
OD;
l
);
 
[6]TYPE sample := (61, 52, 63, 94, 46, 18);
print((bogo sort(sample), new line))
Output:
       +18        +46        +52        +61        +63        +94

[edit] AutoHotkey

MsgBox % Bogosort("987654")
MsgBox % Bogosort("319208")
MsgBox % Bogosort("fedcba")
MsgBox % Bogosort("gikhjl")
 
Bogosort(sequence) {
While !Sorted(sequence)
sequence := Shuffle(sequence)
Return sequence
}
 
Sorted(sequence) {
Loop, Parse, sequence
{
current := A_LoopField
rest := SubStr(sequence, A_Index)
Loop, Parse, rest
{
If (current > A_LoopField)
Return false
}
}
Return true
}
 
Shuffle(sequence) {
Max := StrLen(sequence) + 1
Loop % StrLen(sequence) {
Random, Num, 1, % Max - A_Index
Found .= SubStr(sequence, Num, 1)
sequence := SubStr(sequence, 1, Num-1) . SubStr(sequence, Num+1)
}
Return Found
}

[edit] AWK

Sort standard input and output to the standard output

function randint(n)
{
return int(n * rand())
}
 
function sorted(sa, sn)
{
for(si=1; si < sn; si++) {
if ( sa[si] > sa[si+1] ) return 0;
}
return 1
}
 
{
line[NR] = $0
}
END { # sort it with bogo sort
while ( sorted(line, NR) == 0 ) {
for(i=1; i <= NR; i++) {
r = randint(NR) + 1
t = line[i]
line[i] = line[r]
line[r] = t
}
}
#print it
for(i=1; i <= NR; i++) {
print line[i]
}
}

[edit] BBC BASIC

      DIM test(9)
test() = 4, 65, 2, 31, 0, 99, 2, 83, 782, 1
 
shuffles% = 0
WHILE NOT FNsorted(test())
shuffles% += 1
PROCshuffle(test())
ENDWHILE
PRINT ;shuffles% " shuffles required to sort "; DIM(test(),1)+1 " items."
END
 
DEF PROCshuffle(d())
LOCAL I%
FOR I% = DIM(d(),1)+1 TO 2 STEP -1
SWAP d(I%-1), d(RND(I%)-1)
NEXT
ENDPROC
 
DEF FNsorted(d())
LOCAL I%
FOR I% = 1 TO DIM(d(),1)
IF d(I%) < d(I%-1) THEN = FALSE
NEXT
= TRUE
Output:
383150 shuffles required to sort 10 items.

[edit] Brat

bogosort = { list |
sorted = list.sort #Kinda cheating here
while { list != sorted } { list.shuffle! }
list
}
 
p bogosort [15 6 2 9 1 3 41 19]

[edit] C

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
 
bool is_sorted(int *a, int n)
{
while ( --n >= 1 ) {
if ( a[n] < a[n-1] ) return false;
}
return true;
}
 
void shuffle(int *a, int n)
{
int i, t, r;
for(i=0; i < n; i++) {
t = a[i];
r = rand() % n;
a[i] = a[r];
a[r] = t;
}
}
 
void bogosort(int *a, int n)
{
while ( !is_sorted(a, n) ) shuffle(a, n);
}
 
int main()
{
int numbers[] = { 1, 10, 9, 7, 3, 0 };
int i;
 
bogosort(numbers, 6);
for (i=0; i < 6; i++) printf("%d ", numbers[i]);
printf("\n");
}

[edit] C++

Uses C++11. Compile with

g++ -std=c++11 bogo.cpp
#include <algorithm>
#include <iostream>
#include <iterator>
#include <random>
 
template <typename RandomAccessIterator, typename Predicate>
void bogo_sort(RandomAccessIterator begin, RandomAccessIterator end,
Predicate p) {
std::random_device rd;
std::mt19937 generator(rd());
while (!std::is_sorted(begin, end, p)) {
std::shuffle(begin, end, generator);
}
}
 
template <typename RandomAccessIterator>
void bogo_sort(RandomAccessIterator begin, RandomAccessIterator end) {
bogo_sort(
begin, end,
std::less<
typename std::iterator_traits<RandomAccessIterator>::value_type>());
}
 
int main() {
int a[] = {100, 2, 56, 200, -52, 3, 99, 33, 177, -199};
bogo_sort(std::begin(a), std::end(a));
copy(std::begin(a), std::end(a), std::ostream_iterator<int>(std::cout, " "));
std::cout << "\n";
}
Output:
-199 -52 2 3 33 56 99 100 177 200

[edit] C#

Works with: C# version 3.0+
using System;
using System.Collections.Generic;
 
namespace RosettaCode.BogoSort
{
public static class BogoSorter
{
public static void Sort<T>(List<T> list) where T:IComparable
{
while (!list.isSorted())
{
list.Shuffle();
}
}
 
private static bool isSorted<T>(this IList<T> list) where T:IComparable
{
if(list.Count<=1)
return true;
for (int i = 1 ; i < list.Count; i++)
if(list[i].CompareTo(list[i-1])<0) return false;
return true;
}
 
private static void Shuffle<T>(this IList<T> list)
{
Random rand = new Random();
for (int i = 0; i < list.Count; i++)
{
int swapIndex = rand.Next(list.Count);
T temp = list[swapIndex];
list[swapIndex] = list[i];
list[i] = temp;
}
}
}
 
class TestProgram
{
static void Main()
{
List<int> testList = new List<int> { 3, 4, 1, 8, 7, 4, -2 };
BogoSorter.Sort(testList);
foreach (int i in testList) Console.Write(i + " ");
}
 
}
}

[edit] Clojure

(defn in-order? [order xs]
(or (empty? xs)
(apply order xs)))
 
(defn bogosort [order xs]
(if (in-order? order xs) xs
(recur order (shuffle xs))))
 
(println (bogosort < [7 5 12 1 4 2 23 18]))

[edit] Common Lisp

Sortedp checks that each element of a list is related by predicate to the next element of the list. I.e., (sortedp (x1 x2 … xn) pred) is true when each of (pred x1 x2), …, (pred xn-1 xn) is true.

nshuffle is the same code as in Knuth shuffle.

(defun nshuffle (sequence)
(loop for i from (length sequence) downto 2
do (rotatef (elt sequence (random i))
(elt sequence (1- i ))))
sequence)
 
(defun sortedp (list predicate)
(every predicate list (rest list)))
 
(defun bogosort (list predicate)
(do ((list list (nshuffle list)))
((sortedp list predicate) list)))

[edit] D

import std.stdio, std.algorithm, std.random;
 
void bogoSort(T)(T[] data) {
while (!isSorted(data))
randomShuffle(data);
}
 
void main() {
auto array = [2, 7, 41, 11, 3, 1, 6, 5, 8];
bogoSort(array);
writeln(array);
}
Output:
[1, 2, 3, 5, 6, 7, 8, 11, 41]

[edit] E

Using the shuffle from Knuth shuffle#E.

def isSorted(list) {
if (list.size() == 0) { return true }
var a := list[0]
for i in 1..!(list.size()) {
var b := list[i]
if (a > b) { return false }
a := b
}
return true
}
 
def bogosort(list, random) {
while (!isSorted(list)) {
shuffle(list, random)
}
}

[edit] Eiffel

 
class
BOGO_SORT
 
feature
 
bogo_sort (ar: ARRAY [INTEGER]): ARRAY [INTEGER]
-- Sorted array in ascending order.
do
from
until
is_sorted (ar) = True
loop
Result := shuffel (ar)
end
end
 
feature {NONE}
 
is_sorted (ar: ARRAY [INTEGER]): BOOLEAN
-- Is 'ar' sorted in ascending order?
require
not_void: ar /= Void
local
i: INTEGER
do
Result := True
from
i := 1 + 1
invariant
i >= 1 + 1 and i <= ar.count + 1
until
i > ar.count
loop
Result := Result and ar [i - 1] <= ar [i]
i := i + 1
variant
ar.count + 1 - i
end
end
 
shuffle (ar: ARRAY [INTEGER]): ARRAY [INTEGER]
-- Array containing the same elements as 'ar' in a shuffled order.
require
more_than_one_element: ar.count > 1
local
count, j, ith: INTEGER
random: V_RANDOM
do
create random
create Result.make_empty
Result.deep_copy (ar)
count := ar.count
across
1 |..| count as c
loop
j := random.bounded_item (c.item, count)
ith := Result [c.item]
Result [c.item] := Result [j]
Result [j] := ith
random.forth
end
ensure
same_elements: across ar as a all Result.has (a.item) end
end
 
end
 

TEST:

 
class
APPLICATION
 
create
make
 
feature {NONE}
 
make
do
test := <<3, 2, 5, 7, 1>>
io.put_string ("Unsorted: ")
across
test as t
loop
io.put_string (t.item.out + " ")
end
create sorter
test := sorter.bogo_sort (test)
io.put_string ("%NSorted: ")
across
test as t
loop
io.put_string (t.item.out + " ")
end
end
 
test: ARRAY [INTEGER]
 
sorter: BOGO_SORT
 
end
 
Output:
Unsorted: 3 2 5 7 1
Sorted: 1 2 3 5 7

[edit] Elixir

defmodule Sort do
def bogo_sort(list) do
if sorted?(list) do
list
else
bogo_sort(Enum.shuffle(list))
end
end
 
defp sorted?(list) when length(list)<=1, do: true
defp sorted?([x, y | _]) when x>y, do: false
defp sorted?([_, y | rest]), do: sorted?([y | rest])
end

Example:

iex(114)> Sort.bogo_sort([5,3,9,4,1,6,8,2,7])
[1, 2, 3, 4, 5, 6, 7, 8, 9]

[edit] Euphoria

function shuffle(sequence s)
object temp
integer j
for i = length(s) to 1 by -1 do
j = rand(i)
if i != j then
temp = s[i]
s[i] = s[j]
s[j] = temp
end if
end for
return s
end function
 
function inOrder(sequence s)
for i = 1 to length(s)-1 do
if compare(s[i],s[i+1]) > 0 then
return 0
end if
end for
return 1
end function
 
function bogosort(sequence s)
while not inOrder(s) do
? s
s = shuffle(s)
end while
return s
end function
 
? bogosort(shuffle({1,2,3,4,5,6}))
Output:
{1,2,5,4,6,3}
{5,1,3,6,2,4}
{4,6,1,2,5,3}
.............
{1,2,6,5,4,3}
{5,3,1,2,6,4}
{1,2,3,4,5,6}

[edit] Factor

USING: grouping kernel math random sequences ;
 
: sorted? ( seq -- ? ) 2 <clumps> [ first2 <= ] all? ;
: bogosort ( seq -- newseq ) [ dup sorted? ] [ randomize ] until ;

[edit] Fantom

 
class Main
{
Bool in_order (Int[] items)
{
(0..<(items.size-1)).toList.all |Int i -> Bool|
{
items[i] <= items[i+1]
}
}
 
Int[] bogosort (Int[] items)
{
while (!in_order(items))
{
items.shuffle
}
return items
}
 
Void main ()
{
// example
echo ("Sorting [3,4,2,1] gives " + bogosort ([3,4,2,1]))
}
}
 

[edit] Fortran

Works with: Fortran version 90 and later
MODULE BOGO
IMPLICIT NONE
CONTAINS
FUNCTION Sorted(a)
LOGICAL :: Sorted
INTEGER, INTENT(IN) :: a(:)
INTEGER :: i
 
Sorted = .TRUE.
DO i = 1, SIZE(a)-1
IF(a(i) > a(i+1)) THEN
Sorted = .FALSE.
EXIT
END IF
END DO
END FUNCTION Sorted
 
SUBROUTINE SHUFFLE(a)
INTEGER, INTENT(IN OUT) :: a(:)
INTEGER :: i, rand, temp
REAL :: x
 
DO i = SIZE(a), 1, -1
CALL RANDOM_NUMBER(x)
rand = INT(x * i) + 1
temp = a(rand)
a(rand) = a(i)
a(i) = temp
END DO
END SUBROUTINE
END MODULE
 
PROGRAM BOGOSORT
 
USE BOGO
IMPLICIT NONE
INTEGER :: iter = 0
INTEGER :: array(8) = (/2, 7, 5, 3, 4, 8, 6, 1/)
LOGICAL :: s
 
DO
s = Sorted(array)
IF (s) EXIT
CALL SHUFFLE(array)
iter = iter + 1
END DO
WRITE (*,*) "Array required", iter, " shuffles to sort"
 
END PROGRAM BOGOSORT


[edit] Go

package main
 
import (
"fmt"
"math/rand"
"sort"
"time"
)
 
func main() {
list := []int{31, 41, 59, 26, 53, 58, 97, 93, 23, 84}
rand.Seed(time.Now().UnixNano())
fmt.Println("unsorted:", list)
temp := make([]int, len(list))
copy(temp, list)
for !sort.IntsAreSorted(temp) {
for i, v := range rand.Perm(len(list)) {
temp[i] = list[v]
}
}
fmt.Println("sorted! ", temp)
}
Output:
(sometimes takes a few seconds)
unsorted: [31 41 59 26 53 58 97 93 23 84]
sorted!   [23 26 31 41 53 58 59 84 93 97]

[edit] Groovy

Solution (also implicitly tracks the number of shuffles required):

def bogosort = { list ->
def n = list.size()
while (n > 1 && (1..<n).any{ list[it-1] > list[it] }) {
print '.'*n
Collections.shuffle(list)
}
list
}

Test Program:

println (bogosort([3,1,2]))
Output:
trial 1:
..............................[1, 2, 3]
Output:
trial 2:
...................................................[1, 2, 3]

[edit] Haskell

import System.Random
import Data.Array.IO
import Control.Monad
 
isSorted :: (Ord a) => [a] -> Bool
isSorted (e1:e2:r) = e1 <= e2 && isSorted (e2:r)
isSorted _ = True
 
-- from http://www.haskell.org/haskellwiki/Random_shuffle
shuffle :: [a] -> IO [a]
shuffle xs = do
ar <- newArray n xs
forM [1..n] $ \i -> do
j <- randomRIO (i,n)
vi <- readArray ar i
vj <- readArray ar j
writeArray ar j vi
return vj
where
n = length xs
newArray :: Int -> [a] -> IO (IOArray Int a)
newArray n xs = newListArray (1,n) xs
 
bogosort :: (Ord a) => [a] -> IO [a]
bogosort li | isSorted li = return li
| otherwise = shuffle li >>= bogosort

Example:

*Main> bogosort [7,5,12,1,4,2,23,18]
[1,2,4,5,7,12,18,23]

[edit] Icon and Unicon

procedure shuffle(l)
repeat {
!l :=: ?l
suspend l
}
end
 
procedure sorted(l)
local i
if (i := 2 to *l & l[i] >= l[i-1]) then return &fail else return 1
end
 
procedure main()
local l
l := [6,3,4,5,1]
|( shuffle(l) & sorted(l)) \1 & every writes(" ",!l)
end

[edit] Inform 6

[ shuffle a n i j tmp;
for(i = n - 1: i > 0: i--)
{
j = random(i + 1) - 1;
 
tmp = a->j;
a->j = a->i;
a->i = tmp;
}
];
 
[ is_sorted a n i;
for(i = 0: i < n - 1: i++)
{
if(a->i > a->(i + 1)) rfalse;
}
 
rtrue;
];
 
[ bogosort a n;
while(~~is_sorted(a, n))
{
shuffle(a, n);
}
];

[edit] Io

List do(
isSorted := method(
slice(1) foreach(i, x,
if (x < at(i), return false)
)
return true;
)
 
bogoSortInPlace := method(
while(isSorted not,
shuffleInPlace()
)
)
)
 
lst := list(2, 1, 4, 3)
lst bogoSortInPlace println # ==> list(1, 2, 3, 4), hopefully :)

[edit] J

Generally, this task should be accomplished in J using /:~. Here we take an approach that's more comparable with the other examples on this page.
bogo=: monad define
whilst. +./ 2 >/\ Ry do. Ry=. (A.~ ?@!@#) y end. Ry
)

[edit] Java

Without Collections, Lists or Iterators. With a counter.

 
 
public class BogoSort
{
public static void main(String[] args)
{
//Enter array to be sorted here
int[] arr={4,5,6,0,7,8,9,1,2,3};
 
BogoSort now=new BogoSort();
System.out.print("Unsorted: ");
now.display1D(arr);
 
now.bogo(arr);
 
System.out.print("Sorted: ");
now.display1D(arr);
}
void bogo(int[] arr)
{
//Keep a track of the number of shuffles
int shuffle=1;
for(;!isSorted(arr);shuffle++)
shuffle(arr);
//Boast
System.out.println("This took "+shuffle+" shuffles.");
}
void shuffle(int[] arr)
{
//Standard Fisher-Yates shuffle algorithm
int i=arr.length-1;
while(i>0)
swap(arr,i--,(int)(Math.random()*i));
}
void swap(int[] arr,int i,int j)
{
int temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
boolean isSorted(int[] arr)
{
 
for(int i=1;i<arr.length;i++)
if(arr[i]<arr[i-1])
return false;
return true;
}
void display1D(int[] arr)
{
for(int i=0;i<arr.length;i++)
System.out.print(arr[i]+" ");
System.out.println();
}
 
}
 
Output:
Unsorted: 4 5 6 0 7 8 9 1 2 3 
This took 23104714 shuffles.
Sorted: 0 1 2 3 4 5 6 7 8 9 


Works with: Java version 1.5+

This implementation works for all comparable types (types with compareTo defined).

import java.util.Collections;
import java.util.List;
import java.util.Iterator;
 
public class Bogosort {
private static <T extends Comparable<? super T>> boolean isSorted(List<T> list) {
if (list.isEmpty())
return true;
Iterator<T> it = list.iterator();
T last = it.next();
while (it.hasNext()) {
T current = it.next();
if (last.compareTo(current) > 0)
return false;
last = current;
}
return true;
}
 
public static <T extends Comparable<? super T>> void bogoSort(List<T> list) {
while (!isSorted(list))
Collections.shuffle(list);
}
}

[edit] JavaScript

shuffle = function(v) {
for(var j, x, i = v.length; i; j = Math.floor(Math.random() * i), x = v[--i], v[i] = v[j], v[j] = x);
return v;
};
 
isSorted = function(v){
for(var i=1; i<v.length; i++) {
if (v[i-1] > v[i]) { return false; }
}
return true;
}
 
bogosort = function(v){
var sorted = false;
while(sorted == false){
v = shuffle(v);
sorted = isSorted(v);
}
return v;
}

[edit] Julia

 
function isordered{T}(a::AbstractArray{T,1})
if length(a) < 2
return true
end
for i in 2:length(a)
if a[i] < a[i-1]
return false
end
end
return true
end
 
function bogosort!{T}(a::AbstractArray{T,1})
while !isordered(a)
shuffle!(a)
end
return a
end
 
a = [rand(-10:10) for i in 1:10]
println("Before bogosort:")
println(a)
bogosort!(a)
println("\nAfter bogosort:")
println(a)
 

This bogosort implementation changes the list in place. According to Julia naming conventions, because it makes changes to its input, the function's name ends with a !.

Output:
Before bogosort:
[7,-6,-4,-6,4,5,10,-7,8,-10]

After bogosort:
[-10,-7,-6,-6,-4,4,5,7,8,10]

[edit] Lua

function bogosort (list)
if type (list) ~= 'table' then return list end
 
-- Fisher-Yates Knuth shuffle
local function shuffle ()
local rand = math.random(1,#list)
for i=1,#list do
list[i],list[rand] = list[rand],list[i]
rand = math.random(1,#list)
end
end
 
-- Returns true only if list is now sorted
local function in_order ()
local last = list[1]
for i,v in next,list do
if v < last then return false end
last = v
end
return true
end
 
while not in_order() do shuffle() end
 
return list
end

[edit] M4

divert(-1)
define(`randSeed',141592653)
define(`setRand',
`define(`randSeed',ifelse(eval($1<10000),1,`eval(20000-$1)',`$1'))')
define(`rand_t',`eval(randSeed^(randSeed>>13))')
define(`random',
`define(`randSeed',eval((rand_t^(rand_t<<18))&0x7fffffff))randSeed')
define(`for',
`ifelse($#,0,``$0'',
`ifelse(eval($2<=$3),1,
`pushdef(`$1',$2)$4`'popdef(`$1')$0(`$1',incr($2),$3,`$4')')')')
define(`set',`define(`$1[$2]',`$3')')
define(`new',`set($1,size,0)')
define(`get',`defn($1[$2])')
define(`append',
`set($1,size,incr(get($1,size)))`'set($1,get($1,size),$2)')
define(`deck',
`new($1)for(`x',1,$2,
`append(`$1',random)')')
define(`show',
`for(`x',1,get($1,size),`get($1,x)`'ifelse(x,get($1,size),`',`, ')')')
define(`swap',`set($1,$2,get($1,$4))`'set($1,$4,$3)')
define(`shuffle',
`for(`x',1,get($1,size),
`swap($1,x,get($1,x),eval(1+random%get($1,size)))')')
define(`inordern',
`ifelse(eval($2>=get($1,size)),1,
1,
`ifelse(eval(get($1,$2)>get($1,incr($2))),1,
0,
`inordern(`$1',incr($2))')')')
define(`inorder',`inordern($1,1)')
define(`bogosort',
`ifelse(inorder(`$1'),0,`nope shuffle(`$1')`'bogosort(`$1')')')
divert
 
deck(`b',6)
show(`b')
bogosort(`b')
show(`b')

[edit] Mathematica

Bogosort[x_List] := Block[{t=x},While[!OrderedQ[t],t=RandomSample[x]]; t]
 
Bogosort[{1, 2, 6, 4, 0, -1, Pi, 3, 5}]
=> {-1, 0, 1, 2, 3, Pi, 4, 5, 6}

[edit] MATLAB / Octave

function list = bogoSort(list)  
while( ~issorted(list) ) %Check to see if it is sorted
list = list( randperm(numel(list)) ); %Randomly sort the list
end
end
Output:
bogoSort([5 3 8 4 9 7 6 2 1])
 
ans =
 
1 2 3 4 5 6 7 8 9
 

[edit] MAXScript

fn notSorted arr =
(
if arr.count > 0 then
(
local current = arr[1]
for i in 2 to arr.count do
(
if current > arr[i] then
(
return true
)
current = arr[i]
)
)
false
)
 
fn randSort x y =
(
random -1 1
)
 
fn shuffle arr =
(
qsort arr randSort
arr
)
 
fn bogosort arr =
(
while notSorted arr do
(
arr = shuffle arr
)
arr
)

[edit] Modula-3

MODULE Bogo EXPORTS Main;
 
IMPORT IO, Fmt, Random;
 
VAR a := ARRAY [1..5] OF INTEGER {1, 2, 3, 4, 5};
count := 0;
 
PROCEDURE Shuffle(VAR a: ARRAY OF INTEGER) =
VAR temp: INTEGER;
BEGIN
WITH rand = NEW(Random.Default).init() DO
FOR i := FIRST(a) TO LAST(a) - 1 DO
WITH j = rand.integer(i, LAST(a)) DO
temp := a[i];
a[i] := a[j];
a[j] := temp;
END;
END;
END;
END Shuffle;
 
PROCEDURE Sorted(VAR a: ARRAY OF INTEGER): BOOLEAN =
BEGIN
IF NUMBER(a) <= 1 THEN
RETURN TRUE;
END;
FOR i := FIRST(a) + 1 TO LAST(a) DO
IF (a[i] < a[i - 1]) THEN
RETURN FALSE;
END;
END;
RETURN TRUE;
END Sorted;
 
BEGIN
Shuffle(a);
WHILE NOT Sorted(a) DO
Shuffle(a);
INC(count);
END;
FOR i := FIRST(a) TO LAST(a) DO
IO.PutInt(a[i]);
IO.Put(" ");
END;
IO.Put("\nRequired " & Fmt.Int(count) & " shuffles\n");
END Bogo.

[edit] Nemerle

using System;
using System.Console;
using Nemerle.Imperative;
 
module Bogosort
{
public static Bogosort[T] (this x : array[T]) : void
where T : IComparable
{
def rnd = Random();
def shuffle(a)
{
foreach (i in [0 .. (a.Length - 2)])
a[i] <-> a[(rnd.Next(i, a.Length))];
}
 
def isSorted(b)
{
when (b.Length <= 1) return true;
foreach (i in [1 .. (b.Length - 1)])
when (b[i].CompareTo(b[i - 1]) < 0) return false;
true;
}
 
def loop()
{
unless (isSorted(x)) {shuffle(x); loop();};
}
 
loop()
}
 
Main() : void
{
def sortme = array[1, 5, 3, 6, 7, 3, 8, -2];
sortme.Bogosort();
foreach (i in sortme) Write($"$i ");
}
}

[edit] NetRexx

Translation of: Java
/* NetRexx */
options replace format comments java crossref savelog symbols nobinary
 
import java.util.List
 
method isSorted(list = List) private static returns boolean
 
if list.isEmpty then
return isTrue
 
it = list.iterator
last = Comparable it.next
loop label i_ while it.hasNext
current = Comparable it.next
if last.compareTo(current) > 0 then
return isFalse
last = current
end i_
 
return isTrue
 
method bogoSort(list = List) private static
loop label s_ while \isSorted(list)
Collections.shuffle(list)
end s_
 
return
 
method main(args = String[]) public constant
samples = [int 31, 41, 59, 26, 53, 58, 97, 93, 23, 84]
alst = ArrayList(samples.length)
loop iv = 0 to samples.length - 1
alst.add(Integer(samples[iv]))
end iv
 
say 'unsorted:' alst.toString
bogoSort(alst)
say 'sorted: ' alst.toString
 
return
 
method isTrue public static returns boolean
return 1 == 1
 
method isFalse public static returns boolean
return \isTrue
 
Output:
unsorted: [31, 41, 59, 26, 53, 58, 97, 93, 23, 84]
sorted:   [23, 26, 31, 41, 53, 58, 59, 84, 93, 97]

[edit] Nim

import math
randomize()
 
proc shuffle[T](x: var openarray[T]) =
for i in countdown(x.high, 0):
let j = random(i + 1)
swap(x[i], x[j])
 
proc isSorted[T](s: openarray[T]): bool =
var last = low(T)
for c in s:
if c < last:
return false
last = c
return true
 
proc bogoSort[T](a: var openarray[T]) =
while not isSorted a: shuffle a
 
var a = @[4, 65, 2, -31, 0, 99, 2, 83, 782]
bogoSort a
echo a
Output:
@[-31, 0, 2, 2, 4, 65, 83, 99, 782]

[edit] Oberon-2

MODULE Bogo;
 
IMPORT Out, Random;
 
VAR a: ARRAY 10 OF INTEGER;
 
PROCEDURE Init;
VAR i: INTEGER;
BEGIN
FOR i := 0 TO LEN(a) - 1 DO
a[i] := i + 1;
END;
END Init;
 
PROCEDURE Sorted(VAR a: ARRAY OF INTEGER): BOOLEAN;
VAR i: INTEGER;
BEGIN
IF LEN(a) <= 1 THEN
RETURN TRUE;
END;
FOR i := 1 TO LEN(a) - 1 DO
IF (a[i] < a[i - 1]) THEN
RETURN FALSE;
END;
END;
RETURN TRUE;
END Sorted;
 
PROCEDURE Shuffle*(VAR a: ARRAY OF INTEGER);
VAR n, t, r: INTEGER;
BEGIN
FOR n := 0 TO LEN(a) - 1 DO
r := Random.Roll(n);
t := a[n];
a[n] := a[r];
a[r] := t;
END;
END Shuffle;
 
BEGIN
Init;
Shuffle(a);
WHILE ~Sorted(a) DO
Shuffle(a);
END;
FOR i := 0 TO LEN(a) - 1 DO
Out.Int(a[i], 0);
Out.String(" ");
END;
Out.Ln;
END Bogo.

Init initializes the array as 1 thru 10, then it is shuffled, and then the while loop continually shuffles until Sorted returns true.

[edit] OCaml

let rec is_sorted comp = function
| e1 :: e2 :: r -> comp e1 e2 <= 0 && is_sorted comp (e2 :: r)
| _ -> true
 
(* Fisher-Yates shuffle on lists; uses temp array *)
let shuffle l =
let ar = Array.of_list l in
for n = Array.length ar - 1 downto 1 do
let k = Random.int (n+1) in
let temp = ar.(k) in (* swap ar.(k) and ar.(n) *)
ar.(k) <- ar.(n);
ar.(n) <- temp
done;
Array.to_list ar
 
let rec bogosort li =
if is_sorted compare li then
li
else
bogosort (shuffle li)

Example:

# bogosort [7;5;12;1;4;2;23;18] ;;
- : int list = [1; 2; 4; 5; 7; 12; 18; 23]

[edit] Oz

We use an array because that made most sense for the Knuth Shuffle task. Usually you would use lists for stuff like this in Oz.

declare
proc {BogoSort Arr}
for while:{Not {InOrder Arr}} do
{Shuffle Arr}
end
end
 
fun {InOrder Arr}
for I in {Array.low Arr}+1..{Array.high Arr}
return:Return default:true
do
if Arr.(I-1) > Arr.I then {Return false} end
end
end
 
proc {Shuffle Arr}
Low = {Array.low Arr}
High = {Array.high Arr}
in
for I in High..Low;~1 do
J = Low + {OS.rand} mod (I - Low + 1)
OldI = Arr.I
in
Arr.I := Arr.J
Arr.J := OldI
end
end
 
X = {Tuple.toArray unit(3 1 4 1 5 9 2 6 5)}
in
{BogoSort X}
{Show {Array.toRecord unit X}}

[edit] PARI/GP

This implementation sorts 9 distinct elements in only 600 milliseconds.

bogosort(v)={
while(1,
my(u=vecextract(v,numtoperm(#v,random((#v)!))));
for(i=2,#v,if(u[i]<u[i-1], next(2)));
return(u)
);
};

[edit] Pascal

program bogosort;
 
const
max = 5;
type
list = array [1..max] of integer;
 
{ Print a list }
procedure printa(a: list);
var
i: integer;
begin
for i := 1 to max do
write(a[i], ' ');
writeln
end;
 
{ Knuth shuffle }
procedure shuffle(var a: list);
var
i,k,tmp: integer;
begin
for i := max downto 2 do begin
k := random(i) + 1;
if (a[i] <> a[k]) then begin
tmp := a[i]; a[i] := a[k]; a[k] := tmp
end
end
end;
 
{ Check for sorted list }
function sorted(a: list): boolean;
var
i: integer;
begin
sorted := True;
for i := 2 to max do
if (a[i - 1] > a[i]) then begin
sorted := False; exit
end
end;
 
{ Bogosort }
procedure bogo(var a: list);
var
i: integer;
begin
i := 1; randomize;
write(i,': '); printa(a);
while not sorted(a) do begin
shuffle(a);
i := i + 1; write(i,': '); printa(a)
end
end;
 
{ Test and display }
var
a: list;
i: integer;
 
begin
for i := 1 to max do
a[i] := (max + 1) - i;
bogo(a);
end.
Output:
1: 5 4 3 2 1
2: 3 5 4 1 2
. . . . . .
22: 3 2 1 5 4
23: 1 2 3 4 5

[edit] Perl

use List::Util qw(shuffle);
 
sub bogosort
{my @l = @_;
@l = shuffle(@l) until in_order(@l);
return @l;}
 
sub in_order
{my $last = shift;
foreach (@_)
{$_ >= $last or return 0;
$last = $_;}
return 1;}

[edit] Perl 6

sub bogosort (@list is copy) {
@list .= pick(*) until [<=] @list;
return @list;
}
 
my @nums = (^5).map: { rand };
say @nums.sort.Str eq @nums.&bogosort.Str ?? 'ok' !! 'not ok';
 

[edit] PHP

function bogosort($l) {
while (!in_order($l))
shuffle($l);
return $l;
}
 
function in_order($l) {
for ($i = 1; $i < count($l); $i++)
if ($l[$i] < $l[$i-1])
return FALSE;
return TRUE;
}

[edit] PicoLisp

(de bogosort (Lst)
(loop
(map
'((L) (rot L (rand 1 (length L))))
Lst )
(T (apply <= Lst) Lst) ) )
Output:
: (bogosort (make (do 9 (link (rand 1 999)))))
-> (1 167 183 282 524 556 638 891 902)

: (bogosort (make (do 9 (link (rand 1 999)))))
-> (20 51 117 229 671 848 883 948 978)

: (bogosort (make (do 9 (link (rand 1 999)))))
-> (1 21 72 263 391 476 794 840 878)

[edit] PL/I

Translation of: REXX
*process source xref;
bogosort: Proc Options(main);
Dcl SYSPRINT Print;
Dcl (HBOUND,RANDOM,TIME) Builtin;
Dcl tim Pic'(9)9';
Dcl timms Pic'(3)9' def tim pos(7);
tim=time();
x=random(timms);
Dcl a(5) Dec Fixed(5,1) Init(-21,333,0,444.4,1);
Dcl (x,y,temp) Dec Fixed(5,1);
Dcl (n,bogo,j,u,v) Bin Fixed(31);
n=hbound(a);
Call tell('un-bogoed');
loop:
Do bogo=1 By 1;
Do j=1 To n-1;
jp=j+1;
x=a(j);
y=a(jp);
if y>=x Then
Iterate;
u=rand(1,n);
Do Until v^=u
v=rand(1,n);
End;
Temp=a(u);
a(u)=a(v);
a(v)=temp;
Iterate loop;
End;
Leave;
End;
 
Put Edit('number of bogo sorts performed =',bogo)(Skip,a,f(4));
call tell(' bogoed');
Return;
 
tell: Proc(txt);
Dcl txt Char(*);
Dcl t Bin Fixed(31);
Put Edit(txt)(skip,a);
Do t=1 to n;
Put Edit(a(t))(Skip,f(6,1));
End;
End;
 
rand: Proc(lo,hi) Returns(Bin Fixed(31));
Dcl (lo,hi,res) Bin Fixed(31);
Dcl r Bin Float(31);
r=random();
res=r*(hi-lo+1)+lo;
Return(res);
End;
End;
Output:
un-bogoed
 -21.0
 333.0
   0.0
 444.4
   1.0
number of bogo sorts performed =   8
   bogoed
 -21.0
   0.0
   1.0
 333.0
 444.4 

[edit] PowerShell

Shuffle taken from Knuth Shuffle

function shuffle ($a) { 
$c = $a.Clone() # make copy to avoid clobbering $a
1..($c.Length - 1) | ForEach-Object {
$i = Get-Random -Minimum $_ -Maximum $c.Length
$c[$_-1],$c[$i] = $c[$i],$c[$_-1]
$c[$_-1] # return newly-shuffled value
}
$c[-1] # last value
}
 
function isSorted( [Array] $data )
{
$sorted = $true
for( $i = 1; ( $i -lt $data.length ) -and $sorted; $i++ )
{
$sorted = $data[ $i - 1 ] -le $data[ $i ]
}
$sorted
}
 
function BogoSort ( [Array] $indata ) {
$data = $indata.Clone()
while( -not ( isSorted $data ) ) {
$data = shuffle $indata
}
$data
}
 
$l = 7; BogoSort ( 1..$l | ForEach-Object { $Rand = New-Object Random }{ $Rand.Next( 0, $l - 1 ) } )

[edit] PureBasic

Procedure KnuthShuffle (Array a(1))
Protected i, Size = ArraySize(a())
For i = 0 To Size
Swap a(i), a(Random(Size))
Next
EndProcedure
 
Procedure isSorted(Array a(1))
Protected i, Size = ArraySize(a())
For i = 1 To Size
If a(i) < a(i - 1)
ProcedureReturn #False
EndIf
Next
ProcedureReturn #True
EndProcedure
 
Procedure BogoSort(Array a(1))
Protected Size = ArraySize(a()) + 1, iter
 
While Not isSorted(a())
iter + 1
KnuthShuffle(a())
Wend
MessageRequester("Results","Array of " + Str(Size) + " integers required " + Str(iter) + " shuffles To SORT.")
EndProcedure
 
Dim b(10)
For i = 0 To 10
b(i) = Random(100)
Next
 
BogoSort(b())
Output:
Array of 10 integers required 2766901 shuffles To SORT.

[edit] Python

import random
 
def bogosort(l):
while not in_order(l):
random.shuffle(l)
return l
 
def in_order(l):
if not l:
return True
last = l[0]
for x in l[1:]:
if x < last:
return False
last = x
return True

Alternative definition for in_order (Python 2.5)

def in_order(l):
return all( l[i] <= l[i+1] for i in xrange(0,len(l)-1))

An alternative implementation for Python 2.5 or later:

import random
def bogosort(lst):
random.shuffle(lst) # must shuffle it first or it's a bug if lst was pre-sorted! :)
while lst != sorted(lst):
random.shuffle(lst)
return lst

Another alternative implementation, using iterators for maximum efficiency:

import operator
import random
from itertools import dropwhile, imap, islice, izip, repeat, starmap
 
def shuffled(x):
x = x[:]
random.shuffle(x)
return x
 
bogosort = lambda l: next(dropwhile(
lambda l: not all(starmap(operator.le, izip(l, islice(l, 1, None)))),
imap(shuffled, repeat(l))))

[edit] Qi

 
(define remove-element
0 [_ | R] -> R
Pos [A | R] -> [A | (remove-element (1- Pos) R)])
 
(define get-element
Pos R -> (nth (1+ Pos) R))
 
(define shuffle-0
Pos R -> [(get-element Pos R) | (shuffle (remove-element Pos R))])
 
(define shuffle
[] -> []
R -> (shuffle-0 (RANDOM (length R)) R))
 
(define in-order?
[] -> true
[A] -> true
[A B | R] -> (in-order? [B | R]) where (<= A B)
_ -> false)
 
(define bogosort
Suggestion -> Suggestion where (in-order? Suggestion)
Suggestion -> (bogosort (shuffle Suggestion)))
 

[edit] R

bogosort <- function(x)
{
is.sorted <- function(x) all(diff(x) >= 0)
while(!is.sorted(x)) x <- sample(x)
x
}
 
n <- c(1, 10, 9, 7, 3, 0)
print(bogosort(n))

[edit] Racket

Only the first line is needed to implement the bogo sort, the rest is unit tests and an example.

 
#lang racket
(define (bogo-sort l) (if (apply <= l) l (bogo-sort (shuffle l))))
 
(require rackunit)
(check-equal? (bogo-sort '(6 5 4 3 2 1)) '(1 2 3 4 5 6))
(check-equal? (bogo-sort (shuffle '(1 1 1 2 2 2))) '(1 1 1 2 2 2))
 
(let ((unsorted (for/list ((i 10)) (random 1000))))
(displayln unsorted)
(displayln (bogo-sort unsorted)))
 
Output:
(chances are you won't get quite this!):
(703 931 12 713 894 232 778 86 700 26)
(12 26 86 232 700 703 713 778 894 931)

[edit] REXX

[edit] true bogo sort

/*REXX program performs a type of  bogo sort  on  numbers in an array.  */
parse arg list /*obtain optional list from C.L. */
if list='' then list=-21 333 0 444.4 /*Not defined? Then use default.*/
#=words(list) /*the number of numbers in list. */
do i=1 for words(list); @.i=word(list,i); end /*create an array.*/
call tell 'before bogo sort'
 
do bogo=1
 
do j=1 for #-1; jp=j+1 /* [↓] compare a # with the next*/
if @.jp>=@.j then iterate /*so far, so good; keep looking.*/
/*get 2 unique random #s for swap*/
do until a\==b; a=random(1, #); b=random(1, #); end
 
parse value @.a @.b with @.b @.a /*swap 2 random numbers in array.*/
iterate bogo /*go and try another bogo sort. */
end /*j*/
 
leave /*we're finished with bogo sort. */
end /*bogo*/ /* [↓] show the # of bogo sorts.*/
 
say 'number of bogo sorts performed =' bogo
call tell ' after bogo sort'
exit /*stick a fork in it, we're done.*/
/*──────────────────────────────────TELL subroutine─────────────────────*/
tell: say; say center(arg(1), 50, '─')
do t=1 for #
say arg(1) 'element'right(t, length(#))'='right(@.t, 18)
end /*t*/
say
return
Output:
using the default input:
─────────────────before bogo sort─────────────────
before bogo sort element   1=               -21
before bogo sort element   2=               333
before bogo sort element   3=                 0
before bogo sort element   4=             444.4

number of bogo sorts performed = 6

───────────────── after bogo sort─────────────────
 after bogo sort element   1=               -21
 after bogo sort element   2=                 0
 after bogo sort element   3=               333
 after bogo sort element   4=             444.4

[edit] modified bogo sort


When a number is found out of order, two random numbers between the first number's position and
the position of the last number checked are swapped (in other words, swap two numbers within what
has already been sorted and including the number out-of-order.   The search then starts over.
This is repeated as often as it takes to finally get the array in order.

/*REXX program performs a type of  bogo sort  on numbers in an array.   */
@.1 = 0  ; @.11= -64  ; @.21= 4096  ; @.31= 6291456
@.2 = 0  ; @.12= 64  ; @.22= 40960  ; @.32= 5242880
@.3 = 1  ; @.13= 256  ; @.23= 16384  ; @.33= -15728640
@.4 = 2  ; @.14= 0  ; @.24= -114688  ; @.34= -27262976
@.5 = 0  ; @.15= -768  ; @.25= -131072  ; @.35= 29360128
@.6 = -4  ; @.16= -512  ; @.26= 262144  ; @.36= 104857600
@.7 = 0  ; @.17= 2048  ; @.27= 589824  ; @.37= -16777216
@.8 = 16  ; @.18= 3072  ; @.28= -393216  ; @.38= -335544320
@.9 = 16  ; @.19= -4096  ; @.29= -2097152  ; @.39= -184549376
@.10= -32  ; @.20= -12288  ; @.30= -262144  ; @.40= 905969664
/* [↑] @.1 is really the 0th Berstel number*/
#=40 /*we have a list of two score Berstel numbers.*/
call tell 'before bogo sort'
 
do bogo=1
 
do j=1 for #;  ?=@.j /*? is the next number in array.*/
 
do k=j+1 to #
if @.k>=? then iterate /*is this # in order? Get next. */
/*get 2 unique random #s for swap*/
do until a\==b; a=random(j, k); b=random(j, k); end
 
parse value @.a @.b with @.b @.a /*swap 2 random #s in array.*/
iterate bogo /*go and try another bogo sort. */
end /*k*/
end /*j*/
 
leave /*we're finished with bogo sort. */
end /*bogo*/ /* [↓] show the # of bogo sorts.*/
 
say 'number of bogo sorts performed =' bogo
call tell ' after bogo sort'
exit /*stick a fork in it, we're done.*/
/*──────────────────────────────────TELL subroutine─────────────────────*/
tell: say; say center(arg(1), 50, '─')
do t=1 for #
say arg(1) 'element'right(t, length(#))'='right(@.t, 18)
end /*t*/
say
return
Output:
─────────────────before bogo sort─────────────────
before bogo sort element 1=                 0
before bogo sort element 2=                 0
before bogo sort element 3=                 1
before bogo sort element 4=                 2
before bogo sort element 5=                 0
before bogo sort element 6=                -4
before bogo sort element 7=                 0
before bogo sort element 8=                16
before bogo sort element 9=                16
before bogo sort element10=               -32
before bogo sort element11=               -64
before bogo sort element12=                64
before bogo sort element13=               256
before bogo sort element14=                 0
before bogo sort element15=              -768
before bogo sort element16=              -512
before bogo sort element17=              2048
before bogo sort element18=              3072
before bogo sort element19=             -4096
before bogo sort element20=            -12288
before bogo sort element21=              4096
before bogo sort element22=             40960
before bogo sort element23=             16384
before bogo sort element24=           -114688
before bogo sort element25=           -131072
before bogo sort element26=            262144
before bogo sort element27=            589824
before bogo sort element28=           -393216
before bogo sort element29=          -2097152
before bogo sort element30=           -262144
before bogo sort element31=           6291456
before bogo sort element32=           5242880
before bogo sort element33=         -15728640
before bogo sort element34=         -27262976
before bogo sort element35=          29360128
before bogo sort element36=         104857600
before bogo sort element37=         -16777216
before bogo sort element38=        -335544320
before bogo sort element39=        -184549376
before bogo sort element40=         905969664

number of bogo sorts performed = 1891

───────────────── after bogo sort─────────────────
 after bogo sort element 1=        -335544320
 after bogo sort element 2=        -184549376
 after bogo sort element 3=         -27262976
 after bogo sort element 4=         -16777216
 after bogo sort element 5=         -15728640
 after bogo sort element 6=          -2097152
 after bogo sort element 7=           -393216
 after bogo sort element 8=           -262144
 after bogo sort element 9=           -131072
 after bogo sort element10=           -114688
 after bogo sort element11=            -12288
 after bogo sort element12=             -4096
 after bogo sort element13=              -768
 after bogo sort element14=              -512
 after bogo sort element15=               -64
 after bogo sort element16=               -32
 after bogo sort element17=                -4
 after bogo sort element18=                 0
 after bogo sort element19=                 0
 after bogo sort element20=                 0
 after bogo sort element21=                 0
 after bogo sort element22=                 0
 after bogo sort element23=                 1
 after bogo sort element24=                 2
 after bogo sort element25=                16
 after bogo sort element26=                16
 after bogo sort element27=                64
 after bogo sort element28=               256
 after bogo sort element29=              2048
 after bogo sort element30=              3072
 after bogo sort element31=              4096
 after bogo sort element32=             16384
 after bogo sort element33=             40960
 after bogo sort element34=            262144
 after bogo sort element35=            589824
 after bogo sort element36=           5242880
 after bogo sort element37=           6291456
 after bogo sort element38=          29360128
 after bogo sort element39=         104857600
 after bogo sort element40=         905969664

More tests showed that:

number of bogo sorts performed = 2583
number of bogo sorts performed = 2376
number of bogo sorts performed = 1791
number of bogo sorts performed = 2537
number of bogo sorts performed = 1856
number of bogo sorts performed = 2339
number of bogo sorts performed = 2511
number of bogo sorts performed = 2652
number of bogo sorts performed = 1697
number of bogo sorts performed = 1782
number of bogo sorts performed = 2074
number of bogo sorts performed = 4017
number of bogo sorts performed = 2469
number of bogo sorts performed = 3707
number of bogo sorts performed = 1729
number of bogo sorts performed = 1705
number of bogo sorts performed = 4071

[edit] Ruby

def shuffle(l)
l.sort_by { rand }
end
 
def bogosort(l)
l = shuffle(l) until in_order(l)
l
end
 
def in_order(l)
(0..l.length-2).all? {|i| l[i] <= l[i+1] }
end

An alternative implementation:

def shuffle(l)
l.sort_by { rand }
end
 
def bogosort(l)
l = shuffle(l) until l == l.sort
l
end
Works with: Ruby version 1.8.7+
def in_order(l)
(0..l.length-2).all? {|i| l[i] <= l[i+1] }
end
 
def bogosort(l)
l.shuffle! until in_order(l)
l
end

[edit] Scala

Works with: Scala version 2.8
def isSorted(l: List[Int]) = l.iterator sliding 2 forall (s => s.head <= s.last)
def bogosort(l: List[Int]): List[Int] = if (isSorted(l)) l else bogosort(scala.util.Random.shuffle(l))

[edit] Smalltalk

Works with: GNU Smalltalk

This implementation uses closures rather than extending collections to provide a bogosort method.

Smalltalk at: #isItSorted put: [ :c |
|isit|
isit := false.
(2 to: (c size)) detect: [ :i |
( (c at: ( i - 1 )) > (c at: i) )
] ifNone: [ isit := true ].
isit
].
Smalltalk at: #bogosort put: [ :c |
[ isItSorted value: c ] whileFalse: [
1 to: (c size) do: [ :i |
|r t|
r := (Random between: 1 and: (c size)).
t := (c at: i).
c at: i put: (c at: r).
c at: r put: t
]
]
].
 
|tobesorted|
tobesorted := { 2 . 7 . 5 . 3 . 4 . 8 . 6 . 1 }.
bogosort value: tobesorted.
tobesorted displayNl.

[edit] SNOBOL4

* Library for random()
-include 'Random.sno'
 
* # String -> array
define('s2a(str,n)i') :(s2a_end)
s2a s2a = array(n); str = str ' '
sa1 str break(' ') . s2a<i = i + 1> span(' ') = :s(sa1)f(return)
s2a_end
 
* # Array -> string
define('a2s(a)i') :(a2s_end)
a2s a2s = a2s a<i = i + 1> ' ' :s(a2s)f(return)
a2s_end
 
* # Knuth shuffle in-place
define('shuffle(a)alen,n,k,tmp') :(shuffle_end)
shuffle n = alen = prototype(a);
sh1 k = convert(random() * alen,'integer') + 1
eq(a<n>,a<k>) :s(sh2)
tmp = a<n>; a<n> = a<k>; a<k> = tmp
sh2 n = gt(n,1) n - 1 :s(sh1)
shuffle = a :(return)
shuffle_end
 
* # sorted( ) predicate -> Succeed/Fail
define('sorted(a)alen,i') :(sorted_end)
sorted alen = prototype(a); i = 1
std1 i = lt(i,alen) i + 1 :f(return)
gt(a<i - 1>,a<i>) :s(freturn)f(std1)
sorted_end
 
* # Bogosort
define('bogo(a)') :(bogo_end)
bogo output = (i = i + 1) ': ' a2s(a)
bogo = sorted(a) a :s(return)
shuffle(a) :(bogo)
bogo_end
 
* # Test and display
bogo(s2a('5 4 3 2 1',5))
end
Output:
1: 5 4 3 2 1
2: 2 1 4 3 5 
. . . . . .
117: 3 2 1 5 4
118: 1 2 3 4 5

[edit] Swift

import Darwin
 
func shuffle<T>(inout array: [T]) {
for i in 1..<array.count {
let j = Int(arc4random_uniform(UInt32(i)))
(array[i], array[j]) = (array[j], array[i])
}
}
 
func issorted<T:Comparable>(ary: [T]) -> Bool {
for i in 0..<(ary.count-1) {
if ary[i] > ary[i+1] {
return false
}
}
return true
}
 
func bogosort<T:Comparable>(inout ary: [T]) {
while !issorted(ary) {
shuffle(&ary)
}
}

[edit] Tcl

package require Tcl 8.5
 
proc shuffleInPlace {listName} {
upvar 1 $listName list
set len [set len2 [llength $list]]
for {set i 0} {$i < $len-1} {incr i; incr len2 -1} {
# Pick cell to swap with
set n [expr {int($i + $len2 * rand())}]
# Perform swap
set temp [lindex $list $i]
lset list $i [lindex $list $n]
lset list $n $temp
}
}
proc inOrder {list} {
set prev [lindex $list 0]
foreach item [lrange $list 1 end] {
if {$prev > $item} {
return false
}
set prev $item
}
return true
}
proc bogosort {list} {
while { ! [inOrder $list]} {
shuffleInPlace list
}
return $list
}

[edit] TI-83 BASIC

Same IO as BozoSort (below).

:"BOGO"
:L1→L2
:Lbl A
:dim(L2)→A
:For(B,1,dim(L2)-1)
:randInt(1,A)→C
:L2(C)→D
:L2(A)→L2(C)
:D→L2(A)
:A-1→A
:End
:For(D,1,dim(L2)-1)
:If L2(D)>L2(D+1)
:Goto A
:End
:DelVar A
:DelVar B
:DelVar C
:DelVar D
:Return

This isn't a bogosort, but a bozosort. Store input into L1, run prgmSORTBOZO, outputs to L2

:L1→L2
:Lbl T
:0→B
:For(A,1,dim(L2)-1)
:If L2(A)>L2(A+1)
:1→B
:End
:If B=0
:Goto E
:randInt(1,dim(L2))→C
:randInt(1,dim(L2))→D
:L2(C)→E
:L2(C+1)→L2(C)
:E→L2(C+1)
:Goto T
:Lbl E
:DelVar A
:DelVar B
:DelVar C
:DelVar D
:DelVar E
:Stop

[edit] Ursala

#import std
#import nat
 
shuffle = @iNX ~&l->r ^jrX/~&l ~&lK8PrC
 
bogosort = (not ordered nleq)-> shuffle
 
#cast %nL
 
example = bogosort <8,50,0,12,47,51>
Output:
<0,8,12,47,50,51>

[edit] VBScript

[edit] Implementation
sub swap( byref a, byref b )
dim tmp
tmp = a
a = b
b = tmp
end sub
 
'knuth shuffle (I think)
function shuffle( a )
dim i
dim r
randomize timer
for i = lbound( a ) to ubound( a )
r = int( rnd * ( ubound( a ) + 1 ) )
if r <> i then
swap a(i), a(r)
end if
next
shuffle = a
end function
 
function inOrder( a )
dim res
dim i
for i = 0 to ubound( a ) - 1
res = ( a(i) <= a(i+1) )
if res = false then exit for
next
inOrder = res
end function
[edit] Invocation
dim a
a = array(11, 1, 2, 3, 4, 4, 6, 7, 8)
 
dim t
t = timer
while not inorder( a )
shuffle a
wend
wscript.echo timer-t, "seconds"
wscript.echo join( a, ", " )
[edit] A few outputs (timed)
10.34766 seconds
1, 2, 3, 4, 4, 6, 7, 8, 11

0.5039063 seconds
1, 2, 3, 4, 4, 6, 7, 8, 11

1.980469 seconds
1, 2, 3, 4, 4, 6, 7, 8, 11

[edit] XPL0

code Ran=1, ChOut=8, IntOut=11;
 
proc BogoSort(A, L); \Sort array A of length L
int A, L;
int I, J, T;
[loop [I:= 0;
loop [if A(I) > A(I+1) then quit;
I:= I+1;
if I >= L-1 then return;
];
I:= Ran(L); J:= Ran(L);
T:= A(I); A(I):= A(J); A(J):= T;
];
];
 
int A, I;
[A:= [3, 1, 4, 1, -5, 9, 2, 6, 5, 4];
BogoSort(A, 10);
for I:= 0 to 10-1 do [IntOut(0, A(I)); ChOut(0, ^ )];
]
Output:
-5 1 1 2 3 4 4 5 6 9 

[edit] zkl

fcn increasing(list){
list.len()<2 or
list.reduce(fcn(a,b){ if(b<a) return(Void.Stop,False); b }).toBool()
}
 
ns:=L(5,23,1,6,123,7,23);
while(not increasing(ns)){ ns=ns.shuffle() }
ns.println();
Output:
L(1,5,6,7,23,23,123)
Personal tools
Namespaces

Variants
Actions
Community
Explore
Misc
Toolbox