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 comparing various sorts, see compare sorts.
For other sorting algorithms, see sorting algorithms, or:
Heap sort | Merge sort | Patience sort | Quick sort
O(n log2n) sorts
Shell Sort
O(n2) sorts
Bubble sort |
Cocktail sort |
Cocktail sort with shifting bounds |
Comb sort |
Cycle sort |
Gnome sort |
Insertion sort |
Selection sort |
Strand sort
other sorts
Bead sort |
Bogo sort |
Common sorted list |
Composite structures sort |
Custom comparator sort |
Counting sort |
Disjoint sublist sort |
External sort |
Jort sort |
Lexicographical sort |
Natural sorting |
Order by pair comparisons |
Order disjoint list items |
Order two numerical lists |
Object identifier (OID) sort |
Pancake sort |
Quickselect |
Permutation sort |
Radix sort |
Ranking methods |
Remove duplicate elements |
Sleep sort |
Stooge sort |
[Sort letters of a string] |
Three variable sort |
Topological sort |
Tree sort
Bogosort a list of numbers. Bogosort simply shuffles a collection until it is sorted. (read the article on Wikipedia)
It is worth noting that "Bogosort" is a perversely inefficient algorithm and only used as an "in joke". Its typical run-time efficiency would be O(n!) ... the chances that any given shuffle of a set will end up in sorted order is about one in n factorial! Worst case is infinite! (We can never guarantee that a random shuffling will ever produce a sorted sequence).
Pseudocode:
while not InOrder(list) do Shuffle(list) done
See also
- Knuth shuffle (which may be used to implement the shuffle part of this algorithm)
ActionScript
<lang 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;
}</lang>
Ada
<lang 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;</lang> 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. Sample output:
3 6 7 9
ALGOL 68
<lang algol68>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))</lang> Output:
+18 +46 +52 +61 +63 +94
AutoHotkey
<lang 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
}</lang>
AWK
Sort standard input and output to the standard output <lang awk>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]
}
}</lang>
C
<lang 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");
}</lang>
C++
The following algorithm actually works for all sequences of comparable types; restricting to lists of integers would not make the code simpler. <lang cpp>#include <iterator>
- include <algorithm>
template<typename ForwardIterator>
void bogosort(ForwardIterator begin, ForwardIterator end)
{
typedef std::iterator_traits<ForwardIterator>::value_type value_type;
// if we find two adjacent values where the first is greater than the second, the sequence isn't sorted. while (std::adjacent_find(begin, end, std::greater<value_type>()) != end) std::random_shuffle(begin, end);
}</lang> Using the is_sorted function, part of the SGI STL implementation:
<lang cpp>#include <algorithm>
- include <ext/algorithm>
template<typename ForwardIterator>
void bogosort(ForwardIterator begin, ForwardIterator end)
{
while (!__gnu_cxx::is_sorted(begin, end)) std::random_shuffle(begin, end);
}</lang>
C#
<lang csharp>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 + " ");
}
}
}</lang>
Clojure
We use seq-utils' shuffle, which initializes a Java ArrayList with the input sequence, shuffle it, and then return a sequence of the result.
<lang clojure>(ns bogosort
(:use [clojure.contrib.seq-utils :only (shuffle)]))
(defn in-order? [less xs]
(or (empty? xs)
(empty? (next xs))
(and (less (first xs) (second xs))
(recur less (next xs)))))
(defn bogosort
([xs]
(bogosort < xs))
([less xs]
(if (in-order? less xs) xs
(recur less (shuffle xs)))))
(println (bogosort [7,5,12,1,4,2,23,18]))</lang>
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.
<lang lisp>(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)))</lang>
D
<lang d>module bogosort ; import std.stdio, std.random ;
bool isSorted(T)(inout T[] a) { // test if a is already sorted
if(a.length <= 1) return true ; // 1-elemented/empty array is defined as sorted for(int i = 1 ; i < a.length ; i++) if(a[i] < a[i-1]) return false ; return true ;
}
T[] bogosort(T)(T[] s) {
while(!isSorted(s)) {
for(int n = s.length ; n > 1 ; n--) {
int i = rand() % n ; // random shuffling
T tmp = s[i] ; s[i] = s[n - 1] ; s[n - 1] = tmp ;
}
}
return s ;
}
void main() {
auto b = [2,7,4,3] ;
writefln("%s", bogosort(b)) ;
writefln("%s", b) ; // sort is in place
}</lang>
E
Using the shuffle from Knuth shuffle#E.
<lang 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)
}
}</lang>
Factor
<lang factor>USING: grouping kernel math random sequences ;
- sorted? ( seq -- ? ) 2 <clumps> [ first2 <= ] all? ;
- bogosort ( seq -- newseq ) [ dup sorted? ] [ randomize ] until ;</lang>
Fortran
<lang fortran>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</lang>
Groovy
Solution (also implicitly tracks the number of shuffles required): <lang groovy>def bogosort = { list ->
def n = list.size()
if (n > 1) {
while ((1..<n).any{ list[it-1] > list[it] }) {
Collections.shuffle(list)
print '.'
}
}
list
}</lang>
Test Program: <lang groovy>println bogosort([3,1,2])</lang>
Output, trial 1:
....[1, 2, 3]
Output, trial 2:
..........................[1, 2, 3]
Haskell
<lang 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</lang>
Example:
*Main> bogosort [7,5,12,1,4,2,23,18] [1,2,4,5,7,12,18,23]
Icon
<lang icon>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</lang>
J
<lang j>bogo=: monad define
whilst. -. *./ 2 </\ Ry do. Ry=. (A.~ ?@!@#) y end. Ry
)</lang>
Java
This implementation works for all comparable types (types with compareTo defined). <lang java5>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);
}
}</lang>
JavaScript
<lang javascript>shuffle = function(v) {
for(var j, x, i = v.length; i; j = parseInt(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;
}</lang>
Lua
<lang 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</lang>
M4
<lang 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')</lang>
Mathematica
<lang 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}</lang>
MAXScript
<lang 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
)</lang>
Modula-3
<lang modula3>MODULE Bogo EXPORTS Main;
IMPORT IO, Random;
VAR a := ARRAY [1..10] OF INTEGER {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
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 LAST(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);
END;
FOR i := FIRST(a) TO LAST(a) DO
IO.PutInt(a[i]);
IO.Put(" ");
END;
IO.PutChar('\n');
END Bogo.</lang>
Oberon-2
<lang oberon2>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.</lang>
Init initializes the array as 1 thru 10, then it is shuffled, and then the while loop continually shuffles until Sorted returns true.
OCaml
<lang 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)</lang>
Example:
# bogosort [7;5;12;1;4;2;23;18] ;; - : int list = [1; 2; 4; 5; 7; 12; 18; 23]
Octave
<lang octave>function y = is_sorted(v)
y = true;
for i = 2:length(v)
if ( v(i-1) > v(i) )
y = false;
return
endif
endfor
endfunction
function r = shuffle(v)
l = length(v); for i = 1:l t = v(i); r = unidrnd(l); v(i) = v(r); v(r) = t; endfor r = v;
endfunction
function s = bogosort(v)
while( !is_sorted(v) ) v = shuffle(v); endwhile s = v;
endfunction</lang>
<lang octave>n = [ 1, 10, 9, 7, 3, 0 ]; disp(bogosort(n));</lang>
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.
<lang 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}}</lang>
Perl
<lang perl>sub bogosort
{my @l = @_;
shuffle(\@l) until in_order(@l);
return @l;}
sub in_order
{my $last = shift(@_);
foreach (@_)
{$_ >= $last or return 0;
$last = $_;}
return 1;}
sub shuffle
- This uses the algorithm described at:
- http://en.wikipedia.org/wiki/Fisher-Yates_shuffle#The_modern_algorithm
{our @l; local *l = shift;
# @l is now an alias of the original argument.
for (my $n = $#l ; $n ; --$n)
{my $k = int rand($n + 1);
@l[$k, $n] = @l[$n, $k] if $k != $n;}}</lang>
PHP
<lang 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;
}</lang>
PureBasic
<lang 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())</lang> Sample output:
Array of 10 integers required 2766901 shuffles To SORT.
Python
<lang 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</lang>
Alternative definition for in_order (Python 2.5) <lang python>def in_order(l):
return all( l[i] <= l[i+1] for i in xrange(0,len(l)-1))</lang>
An alternative implementation for Python 2.5 or later: <lang python>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</lang>
R
<lang 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))</lang>
Ruby
<lang 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</lang>
An alternative implementation:
<lang ruby>def shuffle(l)
l.sort_by { rand }
end
def bogosort(l)
l = shuffle(l) until l == l.sort l
end</lang>
<lang ruby>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</lang>
Scala
<lang scala>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))</lang>
Smalltalk
This implementation uses closures rather than extending collections to provide a bogosort method. <lang smalltalk>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.</lang>
Tcl
<lang 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
}</lang>
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
Ursala
<lang 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></lang> output:
<0,8,12,47,50,51>
VBScript
Implementation
<lang vb> 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 </lang>
Invocation
<lang vb> 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, ", " ) </lang>
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