Sorting algorithms/Bogosort: Difference between revisions
added php |
|||
(226 intermediate revisions by more than 100 users not shown) | |||
Line 1: | Line 1: | ||
{{task|Sorting Algorithms}} |
|||
{{task|Sorting Algorithms}}{{Sorting Algorithm}}Bogosort a list of numbers. Bogosort simply shuffles a collection until it is sorted. (read the article on [[wp:Bogosort|Wikipedia]]) |
|||
[[Category:Sorting]] |
|||
{{Sorting Algorithm}} |
|||
;Task: |
|||
[[wp:Bogosort|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. |
|||
It is worth noting that "Bogosort" is a perversely inefficient algorithm and only used as an "in joke" among computer enthusiasts (geeks and nerds). 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: |
Pseudocode: |
||
while not InOrder(list) do |
'''while not''' InOrder(list) '''do''' |
||
Shuffle(list) |
|||
'''done''' |
|||
<br> |
|||
The [[Knuth shuffle]] may be used to implement the shuffle part of this algorithm. |
|||
<br><br> |
|||
=={{header|11l}}== |
|||
<syntaxhighlight lang="11l">F is_sorted(data) |
|||
R all((0 .< data.len - 1).map(i -> @data[i] <= @data[i + 1])) |
|||
F bogosort(&data) |
|||
L !is_sorted(data) |
|||
random:shuffle(&data) |
|||
V arr = [2, 1, 3] |
|||
bogosort(&arr) |
|||
print(arr)</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
[1, 2, 3] |
|||
</pre> |
|||
=={{header|AArch64 Assembly}}== |
|||
{{works with|as|Raspberry Pi 3B version Buster 64 bits}} |
|||
<syntaxhighlight lang="aarch64 assembly"> |
|||
/* ARM assembly AARCH64 Raspberry PI 3B */ |
|||
/* program bogosort64.s */ |
|||
/*******************************************/ |
|||
/* Constantes file */ |
|||
/*******************************************/ |
|||
/* for this file see task include a file in language AArch64 assembly*/ |
|||
.include "../includeConstantesARM64.inc" |
|||
/*********************************/ |
|||
/* Initialized data */ |
|||
/*********************************/ |
|||
.data |
|||
sMessResult: .asciz "Value : @ \n" |
|||
szCarriageReturn: .asciz "\n" |
|||
.align 4 |
|||
qGraine: .quad 123456 |
|||
TableNumber: .quad 1,2,3,4,5,6,7,8,9,10 |
|||
.equ NBELEMENTS, (. - TableNumber) / 8 |
|||
/*********************************/ |
|||
/* UnInitialized data */ |
|||
/*********************************/ |
|||
.bss |
|||
sZoneConv: .skip 24 |
|||
/*********************************/ |
|||
/* code section */ |
|||
/*********************************/ |
|||
.text |
|||
.global main |
|||
main: // entry of program |
|||
1: |
|||
ldr x0,qAdrTableNumber // address number table |
|||
mov x1,#NBELEMENTS // number of élements |
|||
bl knuthShuffle |
|||
// table display elements |
|||
ldr x0,qAdrTableNumber // address number table |
|||
mov x1,#NBELEMENTS // number of élements |
|||
bl displayTable |
|||
ldr x0,qAdrTableNumber // address number table |
|||
mov x1,#NBELEMENTS // number of élements |
|||
bl isSorted // control sort |
|||
cmp x0,#1 // sorted ? |
|||
bne 1b // no -> loop |
|||
100: // standard end of the program |
|||
mov x0, #0 // return code |
|||
mov x8, #EXIT // request to exit program |
|||
svc #0 // perform the system call |
|||
qAdrszCarriageReturn: .quad szCarriageReturn |
|||
qAdrsMessResult: .quad sMessResult |
|||
qAdrTableNumber: .quad TableNumber |
|||
/******************************************************************/ |
|||
/* control sorted table */ |
|||
/******************************************************************/ |
|||
/* x0 contains the address of table */ |
|||
/* x1 contains the number of elements > 0 */ |
|||
/* x0 return 0 if not sorted 1 if sorted */ |
|||
isSorted: |
|||
stp x2,lr,[sp,-16]! // save registers |
|||
stp x3,x4,[sp,-16]! // save registers |
|||
mov x2,#0 |
|||
ldr x4,[x0,x2,lsl #3] // load A[0] |
|||
1: |
|||
add x2,x2,#1 |
|||
cmp x2,x1 // end ? |
|||
bge 99f |
|||
ldr x3,[x0,x2, lsl #3] // load A[i] |
|||
cmp x3,x4 // compare A[i],A[i-1] |
|||
blt 98f // smaller -> error -> return |
|||
mov x4,x3 // no -> A[i-1] = A[i] |
|||
b 1b // and loop |
|||
98: |
|||
mov x0,#0 // error |
|||
b 100f |
|||
99: |
|||
mov x0,#1 // ok -> return |
|||
100: |
|||
ldp x2,x3,[sp],16 // restaur 2 registers |
|||
ldp x1,lr,[sp],16 // restaur 2 registers |
|||
ret // return to address lr x30 |
|||
/******************************************************************/ |
|||
/* Display table elements */ |
|||
/******************************************************************/ |
|||
/* x0 contains the address of table */ |
|||
/* x1 contains elements number */ |
|||
displayTable: |
|||
stp x1,lr,[sp,-16]! // save registers |
|||
stp x2,x3,[sp,-16]! // save registers |
|||
mov x2,x0 // table address |
|||
mov x4,x1 // elements number |
|||
mov x3,#0 |
|||
1: // loop display table |
|||
ldr x0,[x2,x3,lsl #3] |
|||
ldr x1,qAdrsZoneConv |
|||
bl conversion10 // décimal conversion |
|||
ldr x0,qAdrsMessResult |
|||
ldr x1,qAdrsZoneConv // insert conversion |
|||
bl strInsertAtCharInc |
|||
bl affichageMess // display message |
|||
add x3,x3,#1 |
|||
cmp x3,x4 // end ? |
|||
blt 1b // no -> loop |
|||
ldr x0,qAdrszCarriageReturn |
|||
bl affichageMess |
|||
100: |
|||
ldp x2,x3,[sp],16 // restaur 2 registers |
|||
ldp x1,lr,[sp],16 // restaur 2 registers |
|||
ret // return to address lr x30 |
|||
qAdrsZoneConv: .quad sZoneConv |
|||
/******************************************************************/ |
|||
/* shuffle game */ |
|||
/******************************************************************/ |
|||
/* x0 contains boxs address */ |
|||
/* x1 contains elements number */ |
|||
knuthShuffle: |
|||
stp x1,lr,[sp,-16]! // save registers |
|||
stp x2,x3,[sp,-16]! // save registers |
|||
stp x4,x5,[sp,-16]! // save registers |
|||
mov x5,x0 // save table address |
|||
mov x2,#0 // start index |
|||
1: |
|||
mov x0,x2 // generate aleas |
|||
bl genereraleas |
|||
ldr x3,[x5,x2,lsl #3] // swap number on the table |
|||
ldr x4,[x5,x0,lsl #3] |
|||
str x4,[x5,x2,lsl #3] |
|||
str x3,[x5,x0,lsl #3] |
|||
add x2,x2,1 // next number |
|||
cmp x2,x1 // end ? |
|||
blt 1b // no -> loop |
|||
100: |
|||
ldp x4,x5,[sp],16 // restaur 2 registers |
|||
ldp x2,x3,[sp],16 // restaur 2 registers |
|||
ldp x1,lr,[sp],16 // restaur 2 registers |
|||
ret // return to address lr x30 |
|||
/***************************************************/ |
|||
/* Generation random number */ |
|||
/***************************************************/ |
|||
/* x0 contains limit */ |
|||
genereraleas: |
|||
stp x1,lr,[sp,-16]! // save registers |
|||
stp x2,x3,[sp,-16]! // save registers |
|||
ldr x1,qAdrqGraine |
|||
ldr x2,[x1] |
|||
ldr x3,qNbDep1 |
|||
mul x2,x3,x2 |
|||
ldr x3,qNbDep2 |
|||
add x2,x2,x3 |
|||
str x2,[x1] // maj de la graine pour l appel suivant |
|||
cmp x0,#0 |
|||
beq 100f |
|||
udiv x3,x2,x0 |
|||
msub x0,x3,x0,x2 // résult = remainder |
|||
100: // end function |
|||
ldp x2,x3,[sp],16 // restaur 2 registers |
|||
ldp x1,lr,[sp],16 // restaur 2 registers |
|||
ret // return to address lr x30 |
|||
qAdrqGraine: .quad qGraine |
|||
qNbDep1: .quad 0x0019660d |
|||
qNbDep2: .quad 0x3c6ef35f |
|||
/********************************************************/ |
|||
/* File Include fonctions */ |
|||
/********************************************************/ |
|||
/* for this file see task include a file in language AArch64 assembly */ |
|||
.include "../includeARM64.inc" |
|||
</syntaxhighlight> |
|||
=={{header|Action!}}== |
|||
<syntaxhighlight lang="action!">PROC PrintArray(INT ARRAY a INT size) |
|||
INT i |
|||
Put('[) |
|||
FOR i=0 TO size-1 |
|||
DO |
|||
IF i>0 THEN Put(' ) FI |
|||
PrintI(a(i)) |
|||
OD |
|||
Put(']) PutE() |
|||
RETURN |
|||
PROC KnuthShuffle(INT ARRAY tab BYTE size) |
|||
BYTE i,j |
|||
INT tmp |
|||
i=size-1 |
|||
WHILE i>0 |
|||
DO |
|||
j=Rand(i+1) |
|||
tmp=tab(i) |
|||
tab(i)=tab(j) |
|||
tab(j)=tmp |
|||
i==-1 |
|||
OD |
|||
RETURN |
|||
BYTE FUNC IsSorted(INT ARRAY tab BYTE size) |
|||
BYTE i |
|||
IF size<2 THEN |
|||
RETURN (1) |
|||
FI |
|||
FOR i=0 TO size-2 |
|||
DO |
|||
IF tab(i)>tab(i+1) THEN |
|||
RETURN (0) |
|||
FI |
|||
OD |
|||
RETURN (1) |
|||
PROC BogoSort(INT ARRAY a INT size) |
|||
WHILE IsSorted(a,size)=0 |
|||
DO |
|||
KnuthShuffle(a,size) |
|||
OD |
|||
RETURN |
|||
PROC Test(INT ARRAY a INT size) |
|||
PrintE("Array before sort:") |
|||
PrintArray(a,size) |
|||
BogoSort(a,size) |
|||
PrintE("Array after sort:") |
|||
PrintArray(a,size) |
|||
PutE() |
|||
RETURN |
|||
PROC Main() |
|||
INT ARRAY |
|||
a(10)=[1 4 65535 0 7 4 20 65530], |
|||
b(21)=[3 2 1 0 65535 65534 65533], |
|||
c(8)=[101 102 103 104 105 106 107 108], |
|||
d(12)=[1 65535 1 65535 1 65535 1 |
|||
65535 1 65535 1 65535] |
|||
Test(a,8) |
|||
Test(b,7) |
|||
Test(c,8) |
|||
Test(d,12) |
|||
RETURN</syntaxhighlight> |
|||
{{out}} |
|||
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Bogosort.png Screenshot from Atari 8-bit computer] |
|||
<pre> |
|||
Array before sort: |
|||
[1 4 -1 0 7 4 20 -6] |
|||
Array after sort: |
|||
[-6 -1 0 1 4 4 7 20] |
|||
Array before sort: |
|||
[3 2 1 0 -1 -2 -3] |
|||
Array after sort: |
|||
[-3 -2 -1 0 1 2 3] |
|||
Array before sort: |
|||
[101 102 103 104 105 106 107 108] |
|||
Array after sort: |
|||
[101 102 103 104 105 106 107 108] |
|||
Array before sort: |
|||
[1 -1 1 -1 1 -1 1 -1 1 -1 1 -1] |
|||
Array after sort: |
|||
[-1 -1 -1 -1 -1 -1 1 1 1 1 1 1] |
|||
</pre> |
|||
=={{header|ActionScript}}== |
|||
<syntaxhighlight 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; |
|||
}</syntaxhighlight> |
|||
=={{header|Ada}}== |
=={{header|Ada}}== |
||
<syntaxhighlight lang="ada">with Ada.Text_IO; use Ada.Text_IO; |
|||
<ada> |
|||
with Ada.Text_IO; use Ada.Text_IO; |
|||
with Ada.Numerics.Discrete_Random; |
with Ada.Numerics.Discrete_Random; |
||
Line 57: | Line 403: | ||
Put (Integer'Image (Sequence (I))); |
Put (Integer'Image (Sequence (I))); |
||
end loop; |
end loop; |
||
end Test_Bogosort; |
end Test_Bogosort;</syntaxhighlight> |
||
The solution is generic. |
|||
</ada> |
|||
The procedure Bogosort can be instantiated |
|||
with any copyable comparable type. |
|||
In the example given it is the standard Integer type. |
|||
{{out}} |
|||
<pre> |
<pre> |
||
3 6 7 9 |
3 6 7 9 |
||
</pre> |
</pre> |
||
=={{header|C++}}== |
|||
The following algorithm actually works for all sequences of comparable types; restricting to lists of integers would not make the code simpler. |
|||
<cpp>#include <iterator> |
|||
#include <algorithm> |
|||
=={{header|ALGOL 68}}== |
|||
template<typename ForwardIterator> |
|||
{{trans|python}} |
|||
void bogosort(ForwardIterator begin, ForwardIterator end) |
|||
{{works with|ALGOL 68|Standard - no extensions to language used}} |
|||
{{works with|ALGOL 68G|Any - tested with release mk15-0.8b.fc9.i386}} |
|||
{{works with|ELLA ALGOL 68|Any (with appropriate job cards) - tested with release 1.8.8d.fc9.i386}} |
|||
<syntaxhighlight 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))</syntaxhighlight> |
|||
{{out}} |
|||
+18 +46 +52 +61 +63 +94 |
|||
=={{header|ARM Assembly}}== |
|||
{{works with|as|Raspberry Pi}} |
|||
<syntaxhighlight lang="arm assembly"> |
|||
/* ARM assembly Raspberry PI */ |
|||
/* program bogosort.s */ |
|||
/************************************/ |
|||
/* Constantes */ |
|||
/************************************/ |
|||
.equ STDOUT, 1 @ Linux output console |
|||
.equ EXIT, 1 @ Linux syscall |
|||
.equ WRITE, 4 @ Linux syscall |
|||
/*********************************/ |
|||
/* Initialized data */ |
|||
/*********************************/ |
|||
.data |
|||
sMessResult: .ascii "Value : " |
|||
sMessValeur: .fill 11, 1, ' ' @ size => 11 |
|||
szCarriageReturn: .asciz "\n" |
|||
.align 4 |
|||
iGraine: .int 123456 |
|||
.equ NBELEMENTS, 6 |
|||
TableNumber: .int 1,2,3,4,5,6,7,8,9,10 |
|||
/*********************************/ |
|||
/* UnInitialized data */ |
|||
/*********************************/ |
|||
.bss |
|||
/*********************************/ |
|||
/* code section */ |
|||
/*********************************/ |
|||
.text |
|||
.global main |
|||
main: @ entry of program |
|||
1: |
|||
ldr r0,iAdrTableNumber @ address number table |
|||
mov r1,#NBELEMENTS @ number of élements |
|||
bl knuthShuffle |
|||
@ table display elements |
|||
ldr r2,iAdrTableNumber |
|||
mov r3,#0 |
|||
2: @ loop display table |
|||
ldr r0,[r2,r3,lsl #2] |
|||
ldr r1,iAdrsMessValeur @ display value |
|||
bl conversion10 @ call function |
|||
ldr r0,iAdrsMessResult |
|||
bl affichageMess @ display message |
|||
add r3,#1 |
|||
cmp r3,#NBELEMENTS - 1 |
|||
ble 2b |
|||
ldr r0,iAdrszCarriageReturn |
|||
bl affichageMess |
|||
ldr r0,iAdrTableNumber @ address number table |
|||
mov r1,#NBELEMENTS @ number of élements |
|||
bl isSorted @ control sort |
|||
cmp r0,#1 @ sorted ? |
|||
bne 1b @ no -> loop |
|||
100: @ standard end of the program |
|||
mov r0, #0 @ return code |
|||
mov r7, #EXIT @ request to exit program |
|||
svc #0 @ perform the system call |
|||
iAdrsMessValeur: .int sMessValeur |
|||
iAdrszCarriageReturn: .int szCarriageReturn |
|||
iAdrsMessResult: .int sMessResult |
|||
iAdrTableNumber: .int TableNumber |
|||
/******************************************************************/ |
|||
/* control sorted table */ |
|||
/******************************************************************/ |
|||
/* r0 contains the address of table */ |
|||
/* r1 contains the number of elements > 0 */ |
|||
/* r0 return 0 if not sorted 1 if sorted */ |
|||
isSorted: |
|||
push {r2-r4,lr} @ save registers |
|||
mov r2,#0 |
|||
ldr r4,[r0,r2,lsl #2] |
|||
1: |
|||
add r2,#1 |
|||
cmp r2,r1 |
|||
movge r0,#1 |
|||
bge 100f |
|||
ldr r3,[r0,r2, lsl #2] |
|||
cmp r3,r4 |
|||
movlt r0,#0 |
|||
blt 100f |
|||
mov r4,r3 |
|||
b 1b |
|||
100: |
|||
pop {r2-r4,lr} |
|||
bx lr @ return |
|||
/******************************************************************/ |
|||
/* knuthShuffle Shuffle */ |
|||
/******************************************************************/ |
|||
/* r0 contains the address of table */ |
|||
/* r1 contains the number of elements */ |
|||
knuthShuffle: |
|||
push {r2-r5,lr} @ save registers |
|||
mov r5,r0 @ save table address |
|||
mov r2,#0 @ start index |
|||
1: |
|||
mov r0,r2 @ generate aleas |
|||
bl genereraleas |
|||
ldr r3,[r5,r2,lsl #2] @ swap number on the table |
|||
ldr r4,[r5,r0,lsl #2] |
|||
str r4,[r5,r2,lsl #2] |
|||
str r3,[r5,r0,lsl #2] |
|||
add r2,#1 @ next number |
|||
cmp r2,r1 @ end ? |
|||
blt 1b @ no -> loop |
|||
100: |
|||
pop {r2-r5,lr} |
|||
bx lr @ return |
|||
/******************************************************************/ |
|||
/* display text with size calculation */ |
|||
/******************************************************************/ |
|||
/* r0 contains the address of the message */ |
|||
affichageMess: |
|||
push {r0,r1,r2,r7,lr} @ save registres |
|||
mov r2,#0 @ counter length |
|||
1: @ loop length calculation |
|||
ldrb r1,[r0,r2] @ read octet start position + index |
|||
cmp r1,#0 @ if 0 its over |
|||
addne r2,r2,#1 @ else add 1 in the length |
|||
bne 1b @ and loop |
|||
@ so here r2 contains the length of the message |
|||
mov r1,r0 @ address message in r1 |
|||
mov r0,#STDOUT @ code to write to the standard output Linux |
|||
mov r7, #WRITE @ code call system "write" |
|||
svc #0 @ call systeme |
|||
pop {r0,r1,r2,r7,lr} @ restaur des 2 registres */ |
|||
bx lr @ return |
|||
/******************************************************************/ |
|||
/* Converting a register to a decimal unsigned */ |
|||
/******************************************************************/ |
|||
/* r0 contains value and r1 address area */ |
|||
/* r0 return size of result (no zero final in area) */ |
|||
/* area size => 11 bytes */ |
|||
.equ LGZONECAL, 10 |
|||
conversion10: |
|||
push {r1-r4,lr} @ save registers |
|||
mov r3,r1 |
|||
mov r2,#LGZONECAL |
|||
1: @ start loop |
|||
bl divisionpar10U @ unsigned r0 <- dividende. quotient ->r0 reste -> r1 |
|||
add r1,#48 @ digit |
|||
strb r1,[r3,r2] @ store digit on area |
|||
cmp r0,#0 @ stop if quotient = 0 |
|||
subne r2,#1 @ else previous position |
|||
bne 1b @ and loop |
|||
@ and move digit from left of area |
|||
mov r4,#0 |
|||
2: |
|||
ldrb r1,[r3,r2] |
|||
strb r1,[r3,r4] |
|||
add r2,#1 |
|||
add r4,#1 |
|||
cmp r2,#LGZONECAL |
|||
ble 2b |
|||
@ and move spaces in end on area |
|||
mov r0,r4 @ result length |
|||
mov r1,#' ' @ space |
|||
3: |
|||
strb r1,[r3,r4] @ store space in area |
|||
add r4,#1 @ next position |
|||
cmp r4,#LGZONECAL |
|||
ble 3b @ loop if r4 <= area size |
|||
100: |
|||
pop {r1-r4,lr} @ restaur registres |
|||
bx lr @return |
|||
/***************************************************/ |
|||
/* division par 10 unsigned */ |
|||
/***************************************************/ |
|||
/* r0 dividende */ |
|||
/* r0 quotient */ |
|||
/* r1 remainder */ |
|||
divisionpar10U: |
|||
push {r2,r3,r4, lr} |
|||
mov r4,r0 @ save value |
|||
//mov r3,#0xCCCD @ r3 <- magic_number lower raspberry 3 |
|||
//movt r3,#0xCCCC @ r3 <- magic_number higter raspberry 3 |
|||
ldr r3,iMagicNumber @ r3 <- magic_number raspberry 1 2 |
|||
umull r1, r2, r3, r0 @ r1<- Lower32Bits(r1*r0) r2<- Upper32Bits(r1*r0) |
|||
mov r0, r2, LSR #3 @ r2 <- r2 >> shift 3 |
|||
add r2,r0,r0, lsl #2 @ r2 <- r0 * 5 |
|||
sub r1,r4,r2, lsl #1 @ r1 <- r4 - (r2 * 2) = r4 - (r0 * 10) |
|||
pop {r2,r3,r4,lr} |
|||
bx lr @ leave function |
|||
iMagicNumber: .int 0xCCCCCCCD |
|||
/***************************************************/ |
|||
/* Generation random number */ |
|||
/***************************************************/ |
|||
/* r0 contains limit */ |
|||
genereraleas: |
|||
push {r1-r4,lr} @ save registers |
|||
ldr r4,iAdriGraine |
|||
ldr r2,[r4] |
|||
ldr r3,iNbDep1 |
|||
mul r2,r3,r2 |
|||
ldr r3,iNbDep1 |
|||
add r2,r2,r3 |
|||
str r2,[r4] @ maj de la graine pour l appel suivant |
|||
cmp r0,#0 |
|||
beq 100f |
|||
mov r1,r0 @ divisor |
|||
mov r0,r2 @ dividende |
|||
bl division |
|||
mov r0,r3 @ résult = remainder |
|||
100: @ end function |
|||
pop {r1-r4,lr} @ restaur registers |
|||
bx lr @ return |
|||
/*****************************************************/ |
|||
iAdriGraine: .int iGraine |
|||
iNbDep1: .int 0x343FD |
|||
iNbDep2: .int 0x269EC3 |
|||
/***************************************************/ |
|||
/* integer division unsigned */ |
|||
/***************************************************/ |
|||
division: |
|||
/* r0 contains dividend */ |
|||
/* r1 contains divisor */ |
|||
/* r2 returns quotient */ |
|||
/* r3 returns remainder */ |
|||
push {r4, lr} |
|||
mov r2, #0 @ init quotient |
|||
mov r3, #0 @ init remainder |
|||
mov r4, #32 @ init counter bits |
|||
b 2f |
|||
1: @ loop |
|||
movs r0, r0, LSL #1 @ r0 <- r0 << 1 updating cpsr (sets C if 31st bit of r0 was 1) |
|||
adc r3, r3, r3 @ r3 <- r3 + r3 + C. This is equivalent to r3 ? (r3 << 1) + C |
|||
cmp r3, r1 @ compute r3 - r1 and update cpsr |
|||
subhs r3, r3, r1 @ if r3 >= r1 (C=1) then r3 <- r3 - r1 |
|||
adc r2, r2, r2 @ r2 <- r2 + r2 + C. This is equivalent to r2 <- (r2 << 1) + C |
|||
2: |
|||
subs r4, r4, #1 @ r4 <- r4 - 1 |
|||
bpl 1b @ if r4 >= 0 (N=0) then loop |
|||
pop {r4, lr} |
|||
bx lr |
|||
</syntaxhighlight> |
|||
=={{header|Arturo}}== |
|||
<syntaxhighlight lang="rebol">bogoSort: function [items][ |
|||
a: new items |
|||
while [not? sorted? a]-> shuffle 'a |
|||
return a |
|||
] |
|||
print bogoSort [3 1 2 8 5 7 9 4 6]</syntaxhighlight> |
|||
{{out}} |
|||
<pre>1 2 3 4 5 6 7 8 9</pre> |
|||
=={{header|AutoHotkey}}== |
|||
<syntaxhighlight 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 |
|||
}</syntaxhighlight> |
|||
=={{header|AWK}}== |
|||
Sort standard input and output to the standard output |
|||
<syntaxhighlight lang="awk">function randint(n) |
|||
{ |
{ |
||
return int(n * rand()) |
|||
typedef std::iterator_traits<ForwardIterator>::value_type value_type; |
|||
} |
|||
function sorted(sa, sn) |
|||
// 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) |
|||
for(si=1; si < sn; si++) { |
|||
std::random_shuffle(begin, end); |
|||
if ( sa[si] > sa[si+1] ) return 0; |
|||
}</cpp> |
|||
} |
|||
Using the is_sorted function, part of the SGI STL implementation: |
|||
return 1 |
|||
} |
|||
{ |
|||
{{works with|GCC}} |
|||
line[NR] = $0 |
|||
<cpp>#include <algorithm> |
|||
} |
|||
#include <ext/algorithm> |
|||
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] |
|||
} |
|||
}</syntaxhighlight> |
|||
=={{header|BASIC256}}== |
|||
template<typename ForwardIterator> |
|||
{{trans|FreeBASIC}} |
|||
void bogosort(ForwardIterator begin, ForwardIterator end) |
|||
<syntaxhighlight lang="vb">global array |
|||
dim array = {10, 1, 2, -6, 3} |
|||
lb = array[?,]-1 : ub = array[?]-1 |
|||
print "unsort "; |
|||
for i = lb to ub |
|||
print rjust(array[i], 4); |
|||
next i |
|||
call Bogosort(array) # ordenar el array |
|||
print chr(10); " sort "; |
|||
for i = lb to ub |
|||
print rjust(array[i], 4); |
|||
next i |
|||
end |
|||
subroutine shuffle(array) |
|||
n = array[?] : m = array[?]*2 |
|||
for k = 1 to m |
|||
i = int(Rand*n) |
|||
j = int(Rand*n) |
|||
tmp = array[i] #swap lb(i), lb(j) |
|||
array[i] = array[j] |
|||
array[j] = tmp |
|||
next k |
|||
end subroutine |
|||
function inorder(array) |
|||
n = array[?] |
|||
for i = 0 to n-2 |
|||
if array[i] > array[i+1] then return false |
|||
next i |
|||
return true |
|||
end function |
|||
subroutine Bogosort(array) |
|||
while not inorder(array) |
|||
call shuffle(array) |
|||
end while |
|||
end subroutine</syntaxhighlight> |
|||
=={{header|BBC BASIC}}== |
|||
<syntaxhighlight lang="bbcbasic"> 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</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
383150 shuffles required to sort 10 items. |
|||
</pre> |
|||
=={{header|BQN}}== |
|||
Requires the <code>_while_</code> idiom because the recursive version <code>{(𝕊𝕩⊏˜•rand.Deal∘≠)⍟(𝕩≢∧𝕩)𝕩}</code> quickly runs out of stack depth. |
|||
<syntaxhighlight lang="bqn">_while_←{𝔽⍟𝔾∘𝔽_𝕣_𝔾∘𝔽⍟𝔾𝕩} |
|||
Bogo←{𝕩⊏˜•rand.Deal≠𝕩}_while_(≢⟜∧)</syntaxhighlight> |
|||
=={{header|Brat}}== |
|||
<syntaxhighlight lang="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]</syntaxhighlight> |
|||
=={{header|C}}== |
|||
<syntaxhighlight lang="c">#include <stdio.h> |
|||
#include <stdlib.h> |
|||
#include <stdbool.h> |
|||
bool is_sorted(int *a, int n) |
|||
{ |
{ |
||
while ( |
while ( --n >= 1 ) { |
||
if ( a[n] < a[n-1] ) return false; |
|||
std::random_shuffle(begin, end); |
|||
} |
|||
}</cpp> |
|||
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"); |
|||
}</syntaxhighlight> |
|||
=={{header|C sharp|C#}}== |
=={{header|C sharp|C#}}== |
||
{{works with|C sharp|C#|3.0+}} |
{{works with|C sharp|C#|3.0+}} |
||
<syntaxhighlight lang="csharp">using System; |
|||
<csharp> |
|||
using System; |
|||
using System.Collections.Generic; |
using System.Collections.Generic; |
||
Line 140: | Line 977: | ||
} |
} |
||
}</syntaxhighlight> |
|||
=={{header|C++}}== |
|||
Uses C++11. Compile with |
|||
g++ -std=c++11 bogo.cpp |
|||
<syntaxhighlight lang="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); |
|||
} |
|||
} |
} |
||
</csharp> |
|||
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"; |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
-199 -52 2 3 33 56 99 100 177 200 |
|||
</pre> |
|||
=={{header|Clojure}}== |
|||
<syntaxhighlight lang="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]))</syntaxhighlight> |
|||
=={{header|COBOL}}== |
|||
This program generates an array of ten pseudo-random numbers in the range 0 to 999 and then sorts them into ascending order. Eventually. |
|||
<syntaxhighlight lang="cobol">identification division. |
|||
program-id. bogo-sort-program. |
|||
data division. |
|||
working-storage section. |
|||
01 array-to-sort. |
|||
05 item-table. |
|||
10 item pic 999 |
|||
occurs 10 times. |
|||
01 randomization. |
|||
05 random-seed pic 9(8). |
|||
05 random-index pic 9. |
|||
01 flags-counters-etc. |
|||
05 array-index pic 99. |
|||
05 adjusted-index pic 99. |
|||
05 temporary-storage pic 999. |
|||
05 shuffles pic 9(8) |
|||
value zero. |
|||
05 sorted pic 9. |
|||
01 numbers-without-leading-zeros. |
|||
05 item-no-zeros pic z(4). |
|||
05 shuffles-no-zeros pic z(8). |
|||
procedure division. |
|||
control-paragraph. |
|||
accept random-seed from time. |
|||
move function random(random-seed) to item(1). |
|||
perform random-item-paragraph varying array-index from 2 by 1 |
|||
until array-index is greater than 10. |
|||
display 'BEFORE SORT:' with no advancing. |
|||
perform show-array-paragraph varying array-index from 1 by 1 |
|||
until array-index is greater than 10. |
|||
display ''. |
|||
perform shuffle-paragraph through is-it-sorted-paragraph |
|||
until sorted is equal to 1. |
|||
display 'AFTER SORT: ' with no advancing. |
|||
perform show-array-paragraph varying array-index from 1 by 1 |
|||
until array-index is greater than 10. |
|||
display ''. |
|||
move shuffles to shuffles-no-zeros. |
|||
display shuffles-no-zeros ' SHUFFLES PERFORMED.' |
|||
stop run. |
|||
random-item-paragraph. |
|||
move function random to item(array-index). |
|||
show-array-paragraph. |
|||
move item(array-index) to item-no-zeros. |
|||
display item-no-zeros with no advancing. |
|||
shuffle-paragraph. |
|||
perform shuffle-items-paragraph, |
|||
varying array-index from 1 by 1 |
|||
until array-index is greater than 10. |
|||
add 1 to shuffles. |
|||
is-it-sorted-paragraph. |
|||
move 1 to sorted. |
|||
perform item-in-order-paragraph varying array-index from 1 by 1, |
|||
until sorted is equal to zero |
|||
or array-index is equal to 10. |
|||
shuffle-items-paragraph. |
|||
move function random to random-index. |
|||
add 1 to random-index giving adjusted-index. |
|||
move item(array-index) to temporary-storage. |
|||
move item(adjusted-index) to item(array-index). |
|||
move temporary-storage to item(adjusted-index). |
|||
item-in-order-paragraph. |
|||
add 1 to array-index giving adjusted-index. |
|||
if item(array-index) is greater than item(adjusted-index) |
|||
then move zero to sorted.</syntaxhighlight> |
|||
{{out}} |
|||
<pre>BEFORE SORT: 141 503 930 105 78 518 180 907 791 361 |
|||
AFTER SORT: 78 105 141 180 361 503 518 791 907 930 |
|||
237262 SHUFFLES PERFORMED.</pre> |
|||
=={{header|Common Lisp}}== |
|||
Sortedp checks that each element of a list is related by predicate to the next element of the list. I.e., <code>(sortedp (x<sub>1</sub> x<sub>2</sub> … x<sub>n</sub>) pred)</code> is true when each of <code>(pred x<sub>1</sub> x<sub>2</sub>)</code>, …, <code>(pred x<sub>n-1</sub> x<sub>n</sub>)</code> is true. |
|||
<code>nshuffle</code> is the same code as in [[Knuth shuffle#Common Lisp|Knuth shuffle]]. |
|||
<syntaxhighlight 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)))</syntaxhighlight> |
|||
=={{header|Crystal}}== |
|||
<syntaxhighlight lang="crystal">def knuthShuffle(items : Array) |
|||
i = items.size-1 |
|||
while i > 1 |
|||
j = Random.rand(0..i) |
|||
items.swap(i, j) |
|||
i -= 1 |
|||
end |
|||
end |
|||
def sorted?(items : Array) |
|||
prev = items[0] |
|||
items.each do |item| |
|||
if item < prev |
|||
return false |
|||
end |
|||
prev = item |
|||
end |
|||
return true |
|||
end |
|||
def bogoSort(items : Array) |
|||
while !sorted?(items) |
|||
knuthShuffle(items) |
|||
end |
|||
end</syntaxhighlight> |
|||
=={{header|D}}== |
=={{header|D}}== |
||
<syntaxhighlight lang="d">import std.stdio, std.algorithm, std.random; |
|||
<d>module bogosort ; |
|||
import std.stdio, std.random ; |
|||
void bogoSort(T)(T[] data) { |
|||
bool isSorted(T)(inout T[] a) { // test if a is already sorted |
|||
while (!isSorted(data)) |
|||
if(a.length <= 1) return true ; // 1-elemented/empty array is defined as sorted |
|||
randomShuffle(data); |
|||
for(int i = 1 ; i < a.length ; i++) if(a[i] < a[i-1]) return false ; |
|||
return true ; |
|||
} |
} |
||
void main() { |
|||
T[] bogosort(T)(T[] s) { |
|||
auto array = [2, 7, 41, 11, 3, 1, 6, 5, 8]; |
|||
while(!isSorted(s)) { |
|||
bogoSort(array); |
|||
for(int n = s.length ; n > 1 ; n--) { |
|||
writeln(array); |
|||
int i = rand() % n ; // random shuffling |
|||
}</syntaxhighlight> |
|||
T tmp = s[i] ; s[i] = s[n - 1] ; s[n - 1] = tmp ; |
|||
{{out}} |
|||
<pre>[1, 2, 3, 5, 6, 7, 8, 11, 41]</pre> |
|||
=={{header|Delphi}}== |
|||
See [https://rosettacode.org/wiki/Sorting_algorithms/Bogosort#Pascal Pascal]. |
|||
=={{header|E}}== |
|||
Using the shuffle from [[Knuth shuffle#E]]. |
|||
<syntaxhighlight 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 |
|||
} |
|||
return s ; |
|||
} |
} |
||
def bogosort(list, random) { |
|||
void main() { |
|||
while (!isSorted(list)) { |
|||
auto b = [2,7,4,3] ; |
|||
shuffle(list, random) |
|||
writefln("%s", bogosort(b)) ; |
|||
} |
|||
writefln("%s", b) ; // sort is in place |
|||
}</syntaxhighlight> |
|||
}</d> |
|||
=={{header| |
=={{header|EasyLang}}== |
||
<syntaxhighlight lang=text> |
|||
{{works with|Fortran|90 and later}} |
|||
proc shuffle . l[] . |
|||
MODULE BOGO |
|||
for i = len l[] downto 2 |
|||
IMPLICIT NONE |
|||
r = random i |
|||
CONTAINS |
|||
swap l[i] l[r] |
|||
FUNCTION Sorted(a) |
|||
. |
|||
LOGICAL :: Sorted |
|||
. |
|||
INTEGER, INTENT(IN) :: a(:) |
|||
proc issorted . l[] r . |
|||
INTEGER :: i |
|||
for i = 2 to len l[] |
|||
if l[i] < l[i - 1] |
|||
r = 0 |
|||
return |
|||
. |
|||
. |
|||
r = 1 |
|||
. |
|||
proc bogosort . l[] . |
|||
repeat |
|||
issorted l[] r |
|||
until r = 1 |
|||
shuffle l[] |
|||
. |
|||
. |
|||
list[] = [ 2 7 41 11 3 1 6 5 8 ] |
|||
bogosort list[] |
|||
print list[] |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
[ 1 2 3 5 6 7 8 11 41 ] |
|||
</pre> |
|||
=={{header|Eiffel}}== |
|||
<syntaxhighlight lang="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 |
|||
</syntaxhighlight> |
|||
TEST: |
|||
<syntaxhighlight lang="eiffel"> |
|||
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 |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
Unsorted: 3 2 5 7 1 |
|||
Sorted: 1 2 3 5 7 |
|||
</pre> |
|||
=={{header|Elena}}== |
|||
ELENA 5.0 : |
|||
<syntaxhighlight lang="elena">import extensions; |
|||
import system'routines; |
|||
extension op |
|||
Sorted = .TRUE. |
|||
{ |
|||
DO i = 1, SIZE(a)-1 |
|||
bogoSorter() |
|||
IF(a(i) > a(i+1)) THEN |
|||
{ |
|||
Sorted = .FALSE. |
|||
var list := self; |
|||
END IF |
|||
END DO |
|||
END FUNCTION Sorted |
|||
until (list.isAscendant()) |
|||
SUBROUTINE SHUFFLE(a) |
|||
{ |
|||
list := list.randomize(list.Length) |
|||
INTEGER :: i, rand, temp |
|||
}; |
|||
^ list |
|||
} |
|||
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 |
|||
public program() |
|||
PROGRAM BOGOSORT |
|||
{ |
|||
var list := new int[]{3, 4, 1, 8, 7, -2, 0}; |
|||
console.printLine("before:", list.asEnumerable()); |
|||
USE BOGO |
|||
console.printLine("after :", list.bogoSorter().asEnumerable()) |
|||
IMPLICIT NONE |
|||
}</syntaxhighlight> |
|||
INTEGER :: iter = 0 |
|||
{{out}} |
|||
INTEGER :: array(8) = (/2, 7, 5, 3, 4, 8, 6, 1/) |
|||
<pre> |
|||
LOGICAL :: s |
|||
before:3,4,1,8,7,-2,0 |
|||
after :-2,0,1,3,4,7,8 |
|||
</pre> |
|||
=={{header|Elixir}}== |
|||
<syntaxhighlight lang="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 |
|||
DO |
|||
defp sorted?([x, y | _]) when x>y, do: false |
|||
s = Sorted(array) |
|||
defp sorted?([_, y | rest]), do: sorted?([y | rest]) |
|||
IF (s) EXIT |
|||
end</syntaxhighlight> |
|||
CALL SHUFFLE(array) |
|||
iter = iter + 1 |
|||
END DO |
|||
WRITE (*,*) "Array required", iter, " shuffles to sort" |
|||
END PROGRAM BOGOSORT |
|||
Example: |
|||
=={{header|Haskell}}== |
|||
<pre> |
|||
iex(114)> Sort.bogo_sort([5,3,9,4,1,6,8,2,7]) |
|||
[1, 2, 3, 4, 5, 6, 7, 8, 9] |
|||
</pre> |
|||
=={{header|EMal}}== |
|||
<syntaxhighlight lang="emal"> |
|||
type BogoSorter |
|||
fun isOrdered ← logic by List list |
|||
if list.length ≤ 1 do return true end |
|||
for int i ← 1; i < list.length; ++i |
|||
if list[i] < list[i - 1] do return false end |
|||
end |
|||
return true |
|||
end |
|||
fun shuffle ← <List list|list.shuffle() |
|||
fun sort ← void by List list |
|||
while not isOrdered(list) |
|||
shuffle(list) |
|||
end |
|||
end |
|||
type Main |
|||
List sample ← int[3, 4, 1, 8, 7, 4, -2] |
|||
BogoSorter.sort(sample) |
|||
sample.list(<int n|write(n + " ")) |
|||
writeLine() |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
<pre> |
||
-2 1 3 4 4 7 8 |
|||
import System.Random |
|||
</pre> |
|||
=={{header|Euphoria}}== |
|||
<syntaxhighlight lang="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}))</syntaxhighlight> |
|||
{{out}} |
|||
<pre>{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} |
|||
</pre> |
|||
=={{header|Factor}}== |
|||
<syntaxhighlight lang="factor">USING: grouping kernel math random sequences ; |
|||
: sorted? ( seq -- ? ) 2 <clumps> [ first2 <= ] all? ; |
|||
: bogosort ( seq -- newseq ) [ dup sorted? ] [ randomize ] until ;</syntaxhighlight> |
|||
=={{header|Fantom}}== |
|||
<syntaxhighlight lang="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])) |
|||
} |
|||
} |
|||
</syntaxhighlight> |
|||
=={{header|Fortran}}== |
|||
{{works with|Fortran|90 and later}} |
|||
<syntaxhighlight 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</syntaxhighlight> |
|||
=={{header|FreeBASIC}}== |
|||
<syntaxhighlight lang="freebasic">sub shuffle( a() as long ) |
|||
dim as ulong n = ubound(a), i, j, k, m = ubound(a)*2 |
|||
dim as ulong tmp |
|||
randomize timer |
|||
for k=1 to m |
|||
i=int(rnd*n) |
|||
j=int(rnd*n) |
|||
tmp = a(i) |
|||
a(i) = a(j) |
|||
a(j) = tmp |
|||
next k |
|||
end sub |
|||
function inorder( a() as long ) as boolean |
|||
dim as ulong i, n = ubound(a) |
|||
for i = 0 to n-2 |
|||
if a(i)>a(i+1) then |
|||
return false |
|||
end if |
|||
next i |
|||
return true |
|||
end function |
|||
sub bogosort( a() as long ) |
|||
while not inorder(a()) |
|||
shuffle(a()) |
|||
wend |
|||
end sub |
|||
dim as long a(5) = {10, 1, 2, -6, 3} |
|||
dim as long i |
|||
bogosort(a()) |
|||
for i=0 to ubound(a) - 1 |
|||
print a(i) |
|||
next i</syntaxhighlight> |
|||
=={{header|Gambas}}== |
|||
'''[https://gambas-playground.proko.eu/?gist=b2b766f379d809cbf054c2d32d76c453 Click this link to run this code]''' |
|||
<syntaxhighlight lang="gambas">Public Sub Main() |
|||
Dim sSorted As String = "123456789" 'The desired outcome |
|||
Dim sTest, sChr As String 'Various strings |
|||
Dim iCounter As Integer 'Loop counter |
|||
Do |
|||
Inc iCounter 'Increase counter value |
|||
Repeat 'Repeat |
|||
sChr = Chr(Rand(49, 57)) 'Get a random number and convert it to a character e.g. 49="1" |
|||
If Not InStr(sTest, sChr) Then sTest &= sChr 'If the random character is not in sTest then add it |
|||
Until Len(sTest) = 9 'Loop until sTest has 9 characters |
|||
Print sTest 'Print the string to test |
|||
If sTest = sSorted Then Break 'If sTest = sSorted then get out of the loop |
|||
sTest = "" 'Empty sTest and try again |
|||
Loop |
|||
Print "Solved in " & Str(iCounter) & " loops" 'Print the result |
|||
End</syntaxhighlight> |
|||
Output: (This example was completed in under 2 seconds) |
|||
<pre> |
|||
......... |
|||
129536487 |
|||
345218769 |
|||
482713659 |
|||
286745931 |
|||
123456789 |
|||
Solved in 155283 loops |
|||
</pre> |
|||
=={{header|Go}}== |
|||
<syntaxhighlight lang="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) |
|||
}</syntaxhighlight> |
|||
{{out}} (sometimes takes a few seconds) |
|||
<pre> |
|||
unsorted: [31 41 59 26 53 58 97 93 23 84] |
|||
sorted! [23 26 31 41 53 58 59 84 93 97] |
|||
</pre> |
|||
=={{header|Groovy}}== |
|||
Solution (also implicitly tracks the number of shuffles required): |
|||
<syntaxhighlight lang="groovy">def bogosort = { list -> |
|||
def n = list.size() |
|||
while (n > 1 && (1..<n).any{ list[it-1] > list[it] }) { |
|||
print '.'*n |
|||
Collections.shuffle(list) |
|||
} |
|||
list |
|||
}</syntaxhighlight> |
|||
Test Program: |
|||
<syntaxhighlight lang="groovy">println (bogosort([3,1,2]))</syntaxhighlight> |
|||
{{out}} trial 1: |
|||
<pre>..............................[1, 2, 3]</pre> |
|||
{{out}} trial 2: |
|||
<pre>...................................................[1, 2, 3]</pre> |
|||
=={{header|Haskell}}== |
|||
<syntaxhighlight lang="haskell">import System.Random |
|||
import Data.Array.IO |
import Data.Array.IO |
||
import Control.Monad |
import Control.Monad |
||
isSortedBy :: (a -> a -> Bool) -> [a] -> Bool |
|||
isSortedBy _ [] = True |
|||
isSortedBy f xs = all (uncurry f) . (zip <*> tail) $ xs |
|||
isSorted :: (Ord a) => [a] -> Bool |
|||
-- from http://www.haskell.org/haskellwiki/Random_shuffle |
|||
isSorted (e1:e2:r) = e1 <= e2 && isSorted (e2:r) |
|||
isSorted _ = True |
|||
-- Plagiarized from http://www.haskell.org/haskellwiki/Random_shuffle |
|||
shuffle :: [a] -> IO [a] |
shuffle :: [a] -> IO [a] |
||
shuffle xs = do |
shuffle xs = do |
||
Line 247: | Line 1,688: | ||
newArray :: Int -> [a] -> IO (IOArray Int a) |
newArray :: Int -> [a] -> IO (IOArray Int a) |
||
newArray n xs = newListArray (1,n) xs |
newArray n xs = newListArray (1,n) xs |
||
bogosortBy :: (a -> a -> Bool) -> [a] -> IO [a] |
|||
bogosortBy f xs | isSortedBy f xs = return xs |
|||
| otherwise = shuffle xs >>= bogosortBy f |
|||
bogosort :: |
bogosort :: Ord a => [a] -> IO [a] |
||
bogosort = bogosortBy (<)</syntaxhighlight> |
|||
bogosort li | isSorted li = return li |
|||
| otherwise = shuffle li >>= bogosort |
|||
</pre> |
|||
Example: |
Example: |
||
<pre> |
<pre> |
||
Line 257: | Line 1,700: | ||
[1,2,4,5,7,12,18,23] |
[1,2,4,5,7,12,18,23] |
||
</pre> |
</pre> |
||
=={{header|Icon}} and {{header|Unicon}}== |
|||
<syntaxhighlight 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</syntaxhighlight> |
|||
=={{header|Inform 6}}== |
|||
<syntaxhighlight lang="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); |
|||
} |
|||
];</syntaxhighlight> |
|||
=={{header|Insitux}}== |
|||
{{Trans|Clojure}} |
|||
<syntaxhighlight lang="insitux">(function bogo-sort order list |
|||
(return-unless (1 list) []) |
|||
(if (... order list) |
|||
list |
|||
(recur order (shuffle list)))) |
|||
(bogo-sort < [7 5 12 1 4 2 23 18])</syntaxhighlight> |
|||
Even with this small list the web REPL sometimes exceeds its default recur budget (1e4 - 10000): |
|||
<pre>4:6 (recur order (shuffle list)))) |
|||
Budget Error: recurred too many times.</pre> |
|||
=={{header|Io}}== |
|||
<syntaxhighlight lang="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 :)</syntaxhighlight> |
|||
=={{header|J}}== |
=={{header|J}}== |
||
{{eff note|J|/:~}} |
|||
bogo=: 3 : 0 |
|||
<syntaxhighlight lang="j">bogo=: monad define |
|||
whilst. -. *./ 2 </\ Ry do. Ry=. (A.~ ?@!@#) y end. Ry |
|||
whilst. +./ 2 >/\ Ry do. Ry=. (A.~ ?@!@#) y end. Ry |
|||
) |
|||
)</syntaxhighlight> |
|||
=={{header|Java}}== |
=={{header|Java}}== |
||
Without Collections, Lists or Iterators. With a counter. |
|||
<syntaxhighlight lang="java"> |
|||
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(); |
|||
} |
|||
} |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre>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 </pre> |
|||
{{works with|Java|1.5+}} |
{{works with|Java|1.5+}} |
||
This implementation works for all comparable types (types with <tt>compareTo</tt> defined). |
This implementation works for all comparable types (types with <tt>compareTo</tt> defined). |
||
< |
<syntaxhighlight lang="java5">import java.util.Collections; |
||
import java.util.List; |
import java.util.List; |
||
import java.util.Iterator; |
import java.util.Iterator; |
||
Line 287: | Line 1,881: | ||
Collections.shuffle(list); |
Collections.shuffle(list); |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
=={{header|JavaScript}}== |
|||
<syntaxhighlight lang="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; |
|||
}</syntaxhighlight> |
|||
=={{header|Julia}}== |
|||
{{works with|Julia|0.6}} |
|||
<syntaxhighlight lang="julia">function bogosort!(arr::AbstractVector) |
|||
while !issorted(arr) |
|||
shuffle!(arr) |
|||
end |
|||
return arr |
|||
end |
|||
v = rand(-10:10, 10) |
|||
println("# unordered: $v\n -> ordered: ", bogosort!(v))</syntaxhighlight> |
|||
{{out}} |
|||
<pre># unordered: [-7, 0, -6, -1, -6, -1, -3, -1, 4, 8] |
|||
-> ordered: [-7, -6, -6, -3, -1, -1, -1, 0, 4, 8]</pre> |
|||
=={{header|Kotlin}}== |
|||
{{trans|C}} |
|||
<syntaxhighlight lang="scala">// version 1.1.2 |
|||
const val RAND_MAX = 32768 // big enough for this |
|||
val rand = java.util.Random() |
|||
fun isSorted(a: IntArray): Boolean { |
|||
val n = a.size |
|||
if (n < 2) return true |
|||
for (i in 1 until n) { |
|||
if (a[i] < a[i - 1]) return false |
|||
} |
|||
return true |
|||
} |
|||
fun shuffle(a: IntArray) { |
|||
val n = a.size |
|||
if (n < 2) return |
|||
for (i in 0 until n) { |
|||
val t = a[i] |
|||
val r = rand.nextInt(RAND_MAX) % n |
|||
a[i] = a[r] |
|||
a[r] = t |
|||
} |
|||
} |
|||
fun bogosort(a: IntArray) { |
|||
while (!isSorted(a)) shuffle(a) |
|||
} |
|||
fun main(args: Array<String>) { |
|||
val a = intArrayOf(1, 10, 9, 7, 3, 0) |
|||
println("Before sorting : ${a.contentToString()}") |
|||
bogosort(a) |
|||
println("After sorting : ${a.contentToString()}") |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
Before sorting : [1, 10, 9, 7, 3, 0] |
|||
After sorting : [0, 1, 3, 7, 9, 10] |
|||
</pre> |
|||
=={{header|Lua}}== |
|||
<syntaxhighlight 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</syntaxhighlight> |
|||
=={{header|M4}}== |
|||
<syntaxhighlight 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')</syntaxhighlight> |
|||
=={{header|Maple}}== |
|||
<syntaxhighlight lang="maple">arr := Array([2,3,1]): |
|||
len := numelems(arr): |
|||
#Translation of C, random swapping |
|||
shuffle_arr := proc(arr, len) |
|||
local i, r, temp: |
|||
for i from 1 to len do |
|||
temp := arr[i]: |
|||
r := rand(1..len)(): |
|||
arr[i] := arr[r]: |
|||
arr[r] := temp: |
|||
end do: |
|||
end proc: |
|||
while(not ListTools:-Sorted(convert(arr, list))) do |
|||
shuffle_arr(arr, len): |
|||
end do: |
|||
arr;</syntaxhighlight> |
|||
{{Out|Output}} |
|||
<pre>[1 2 3]</pre> |
|||
=={{header|Mathematica}}/{{header|Wolfram Language}}== |
|||
<syntaxhighlight 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}</syntaxhighlight> |
|||
=={{header|MATLAB}} / {{header|Octave}}== |
|||
<syntaxhighlight lang="matlab">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</syntaxhighlight> |
|||
{{out}} |
|||
<syntaxhighlight lang="matlab">bogoSort([5 3 8 4 9 7 6 2 1]) |
|||
ans = |
|||
1 2 3 4 5 6 7 8 9 |
|||
</syntaxhighlight> |
|||
=={{header|MAXScript}}== |
|||
<syntaxhighlight 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 |
|||
)</syntaxhighlight> |
|||
=={{header|Modula-3}}== |
|||
<syntaxhighlight lang="modula3">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.</syntaxhighlight> |
|||
=={{header|Nanoquery}}== |
|||
<syntaxhighlight lang="nanoquery">def sorted(list) |
|||
if len(list) = 0 |
|||
return true |
|||
end |
|||
for i in range(0, len(list) - 2) |
|||
if list[i] > list[i + 1] |
|||
return false |
|||
end |
|||
end |
|||
return true |
|||
end |
|||
def bogosort(list) |
|||
while not sorted(list) |
|||
list = list.shuffle() |
|||
end |
|||
return list |
|||
end</syntaxhighlight> |
|||
=={{header|Nemerle}}== |
|||
<syntaxhighlight lang="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 "); |
|||
} |
|||
}</syntaxhighlight> |
|||
=={{header|NetRexx}}== |
|||
{{trans|Java}} |
|||
<syntaxhighlight lang="netrexx">/* 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 |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
unsorted: [31, 41, 59, 26, 53, 58, 97, 93, 23, 84] |
|||
sorted: [23, 26, 31, 41, 53, 58, 59, 84, 93, 97] |
|||
</pre> |
|||
=={{header|Nim}}== |
|||
<syntaxhighlight lang="nim">import random |
|||
randomize() |
|||
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</syntaxhighlight> |
|||
{{out}} |
|||
<pre>@[-31, 0, 2, 2, 4, 65, 83, 99, 782]</pre> |
|||
=={{header|Oberon-2}}== |
=={{header|Oberon-2}}== |
||
{{Works with|Oxford Oberon-2 Compiler}} |
{{Works with|Oxford Oberon-2 Compiler}} |
||
< |
<syntaxhighlight lang="oberon2">MODULE Bogo; |
||
IMPORT Out, Random; |
IMPORT Out, Random; |
||
Line 318: | Line 2,335: | ||
RETURN TRUE; |
RETURN TRUE; |
||
END Sorted; |
END Sorted; |
||
PROCEDURE PrintArray(VAR a: ARRAY OF INTEGER); |
|||
VAR i: INTEGER; |
|||
BEGIN |
|||
FOR i := 0 TO LEN(a) - 1 DO |
|||
Out.Int(a[i], 0); |
|||
Out.String(" "); |
|||
END; |
|||
END PrintArray; |
|||
PROCEDURE Shuffle*(VAR a: ARRAY OF INTEGER); |
PROCEDURE Shuffle*(VAR a: ARRAY OF INTEGER); |
||
Line 345: | Line 2,353: | ||
Shuffle(a); |
Shuffle(a); |
||
END; |
END; |
||
FOR i := 0 TO LEN(a) - 1 DO |
|||
PrintArray(a); |
|||
Out.Int(a[i], 0); |
|||
Out.String(" "); |
|||
END; |
|||
Out.Ln; |
Out.Ln; |
||
END Bogo.</ |
END Bogo.</syntaxhighlight> |
||
Init initializes the array as 1 |
Init initializes the array as 1 thru 10, then it is shuffled, and then the while loop continually shuffles until Sorted returns true. |
||
=={{header|OCaml}}== |
=={{header|OCaml}}== |
||
<syntaxhighlight lang="ocaml">let rec is_sorted comp = function |
|||
<ocaml> |
|||
let rec is_sorted comp = function |
|||
| e1 :: e2 :: r -> comp e1 e2 <= 0 && is_sorted comp (e2 :: r) |
| e1 :: e2 :: r -> comp e1 e2 <= 0 && is_sorted comp (e2 :: r) |
||
| _ -> true |
| _ -> true |
||
Line 373: | Line 2,382: | ||
li |
li |
||
else |
else |
||
bogosort (shuffle li) |
bogosort (shuffle li)</syntaxhighlight> |
||
</ocaml> |
|||
Example: |
Example: |
||
<pre> |
<pre> |
||
Line 380: | Line 2,388: | ||
- : int list = [1; 2; 4; 5; 7; 12; 18; 23] |
- : int list = [1; 2; 4; 5; 7; 12; 18; 23] |
||
</pre> |
</pre> |
||
=={{header|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. |
|||
<syntaxhighlight 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}}</syntaxhighlight> |
|||
=={{header|PARI/GP}}== |
|||
This implementation sorts 9 distinct elements in only 600 milliseconds. |
|||
<syntaxhighlight lang="parigp">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) |
|||
); |
|||
};</syntaxhighlight> |
|||
=={{header|Pascal}}== |
|||
<syntaxhighlight lang="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.</syntaxhighlight> |
|||
{{out}} |
|||
<pre>1: 5 4 3 2 1 |
|||
2: 3 5 4 1 2 |
|||
. . . . . . |
|||
22: 3 2 1 5 4 |
|||
23: 1 2 3 4 5</pre> |
|||
=={{header|Perl}}== |
=={{header|Perl}}== |
||
<syntaxhighlight lang="perl">use List::Util qw(shuffle); |
|||
<perl>sub bogosort |
|||
sub bogosort |
|||
{my @l = @_; |
{my @l = @_; |
||
shuffle( |
@l = shuffle(@l) until in_order(@l); |
||
return @l;} |
return @l;} |
||
sub in_order |
sub in_order |
||
{my $last = shift |
{my $last = shift; |
||
foreach (@_) |
foreach (@_) |
||
{$_ >= $last or return 0; |
{$_ >= $last or return 0; |
||
$last = $_;} |
$last = $_;} |
||
return 1;} |
return 1;}</syntaxhighlight> |
||
=={{header|Phix}}== |
|||
sub shuffle |
|||
<!--<syntaxhighlight lang="phix">(phixonline)--> |
|||
# This uses the algorithm described at: |
|||
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
|||
# http://en.wikipedia.org/wiki/Fisher-Yates_shuffle#The_modern_algorithm |
|||
{our @l; local *l = shift; |
|||
<span style="color: #008080;">function</span> <span style="color: #000000;">inOrder</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">)</span> |
|||
# @l is now an alias of the original argument. |
|||
<span style="color: #008080;">return</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">==</span><span style="color: #7060A8;">sort</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">))</span> <span style="color: #000080;font-style:italic;">-- <snigger></span> |
|||
for (my $n = $#l ; $n ; --$n) |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
|||
{my $k = int rand($n + 1); |
|||
@l[$k, $n] = @l[$n, $k] if $k != $n;}}</perl> |
|||
<span style="color: #008080;">function</span> <span style="color: #000000;">bogosort</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #008080;">while</span> <span style="color: #008080;">not</span> <span style="color: #000000;">inOrder</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span> |
|||
<span style="color: #0000FF;">?</span> <span style="color: #000000;">s</span> |
|||
<span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">shuffle</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span> |
|||
<span style="color: #008080;">return</span> <span style="color: #000000;">s</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
|||
<span style="color: #0000FF;">?</span> <span style="color: #000000;">bogosort</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">shuffle</span><span style="color: #0000FF;">({</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">4</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">6</span><span style="color: #0000FF;">}))</span> |
|||
<!--</syntaxhighlight>--> |
|||
{{out}} |
|||
<pre> |
|||
... |
|||
{4,3,1,5,2,6} |
|||
{1,3,4,6,5,2} |
|||
{2,3,4,1,5,6} |
|||
{1,2,3,4,5,6} |
|||
</pre> |
|||
=={{header|PHP}}== |
=={{header|PHP}}== |
||
<php>function bogosort($l) { |
<syntaxhighlight lang="php">function bogosort($l) { |
||
while (!in_order($l)) |
while (!in_order($l)) |
||
shuffle($l); |
shuffle($l); |
||
Line 415: | Line 2,564: | ||
return FALSE; |
return FALSE; |
||
return TRUE; |
return TRUE; |
||
}</ |
}</syntaxhighlight> |
||
=={{header|PicoLisp}}== |
|||
<syntaxhighlight lang="picolisp">(de bogosort (Lst) |
|||
(loop |
|||
(map |
|||
'((L) (rot L (rand 1 (length L)))) |
|||
Lst ) |
|||
(T (apply <= Lst) Lst) ) )</syntaxhighlight> |
|||
{{out}} |
|||
<pre>: (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)</pre> |
|||
=={{header|PL/I}}== |
|||
{{trans|REXX}} |
|||
<syntaxhighlight lang="pli">*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;</syntaxhighlight> |
|||
{{out}} |
|||
<pre>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 </pre> |
|||
=={{header|PowerShell}}== |
|||
Shuffle taken from [[Knuth Shuffle]] |
|||
<syntaxhighlight lang="powershell">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 ) } )</syntaxhighlight> |
|||
=={{header|Prolog}}== |
|||
<syntaxhighlight lang="prolog">bogo_sort(L,Rl) :- |
|||
min_list(L,Min), |
|||
repeat, |
|||
random_permutation(L,Rl), |
|||
is_sorted(Rl,Min), |
|||
!. |
|||
is_sorted([],_). |
|||
is_sorted([N|T],P) :- |
|||
N >= P, |
|||
is_sorted(T,N).</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
?- bogo_sort( [703,931,12,713,894,232,778,86,700,26] ,Sorted). |
|||
Sorted = [12,26,86,232,700,703,713,778,894,931] . |
|||
</pre> |
|||
=={{header|PureBasic}}== |
|||
<syntaxhighlight 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())</syntaxhighlight> |
|||
{{out}} |
|||
<pre>Array of 10 integers required 2766901 shuffles To SORT.</pre> |
|||
=={{header|Python}}== |
=={{header|Python}}== |
||
<python>import random |
<syntaxhighlight lang="python">import random |
||
def bogosort(l): |
def bogosort(l): |
||
Line 433: | Line 2,757: | ||
return False |
return False |
||
last = x |
last = x |
||
return True</ |
return True</syntaxhighlight> |
||
Alternative definition for ''in_order'' (Python 2.5) |
Alternative definition for ''in_order'' (Python 2.5) |
||
<python>def in_order(l): |
<syntaxhighlight lang="python">def in_order(l): |
||
return |
return all( l[i] <= l[i+1] for i in xrange(0,len(l)-1))</syntaxhighlight> |
||
An alternative implementation for Python 2.5 or later: |
An alternative implementation for Python 2.5 or later: |
||
<syntaxhighlight lang="python">import random |
|||
<python> |
|||
import random |
|||
def bogosort(lst): |
def bogosort(lst): |
||
random.shuffle(lst) # must shuffle it first or it's a bug if lst was pre-sorted! :) |
random.shuffle(lst) # must shuffle it first or it's a bug if lst was pre-sorted! :) |
||
while lst != sorted(lst): |
while lst != sorted(lst): |
||
random.shuffle(lst) |
random.shuffle(lst) |
||
return lst |
return lst</syntaxhighlight> |
||
</python> |
|||
Another alternative implementation, using iterators for maximum efficiency: |
|||
<syntaxhighlight lang="python">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))))</syntaxhighlight> |
|||
=={{header|Qi}}== |
|||
<syntaxhighlight lang="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))) |
|||
</syntaxhighlight> |
|||
=={{header|Quackery}}== |
|||
<syntaxhighlight lang="quackery">[ true swap |
|||
dup [] != if |
|||
[ behead swap witheach |
|||
[ tuck > if |
|||
[ dip not |
|||
conclude ] ] ] |
|||
drop ] is inorder ( [ --> b ) |
|||
[ dup inorder not while shuffle again ] is bogosort ( [ --> [ )</syntaxhighlight> |
|||
=={{header|R}}== |
|||
<syntaxhighlight lang="r">bogosort <- function(x) { |
|||
while(is.unsorted(x)) x <- sample(x) |
|||
x |
|||
} |
|||
n <- c(1, 10, 9, 7, 3, 0) |
|||
bogosort(n)</syntaxhighlight> |
|||
=={{header|Racket}}== |
|||
Only the first line is needed to implement the bogo sort, the rest |
|||
is unit tests and an example. |
|||
<syntaxhighlight lang="racket"> |
|||
#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))) |
|||
</syntaxhighlight> |
|||
{{out}} (chances are you won't get quite this!): |
|||
<pre> |
|||
(703 931 12 713 894 232 778 86 700 26) |
|||
(12 26 86 232 700 703 713 778 894 931) |
|||
</pre> |
|||
=={{header|Raku}}== |
|||
(formerly Perl 6) |
|||
<syntaxhighlight lang="raku" line>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'; |
|||
</syntaxhighlight> |
|||
=={{header|REXX}}== |
|||
===true bogo sort=== |
|||
<syntaxhighlight lang="rexx">/*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</syntaxhighlight> |
|||
{{out}} using the default input: |
|||
<pre> |
|||
─────────────────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 |
|||
</pre> |
|||
===modified bogo sort=== |
|||
<br>When a number is found out of order, two random numbers between the first number's position and |
|||
<br>the position of the last number checked are swapped (in other words, swap two numbers within what |
|||
<br>has already been sorted and including the number out-of-order. The search then starts over. |
|||
<br>This is repeated as often as it takes to finally get the array in order. |
|||
<syntaxhighlight lang="rexx">/*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</syntaxhighlight> |
|||
{{out}} |
|||
<pre style="height:30ex"> |
|||
─────────────────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 |
|||
</pre> |
|||
More tests showed that: |
|||
<pre> |
|||
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 |
|||
</pre> |
|||
=={{header|Ring}}== |
|||
<syntaxhighlight lang="ring"> |
|||
# Project : Sorting algorithms/Bogosort |
|||
test = [4, 65, 2, 31, 0, 99, 2, 83, 782, 1] |
|||
shuffles = 0 |
|||
while ! sorted(test) |
|||
shuffles = shuffles + 1 |
|||
shuffle(test) |
|||
end |
|||
see "" + shuffles + " shuffles required to sort " + len(test) + " items:" + nl |
|||
showarray(test) |
|||
func shuffle(d) |
|||
for i = len(d) to 2 step -1 |
|||
item = random(i) + 1 |
|||
if item <= len(d) |
|||
temp = d[i-1] |
|||
d[i-1] = d[item] |
|||
d[item] = temp |
|||
else |
|||
i = i -1 |
|||
ok |
|||
next |
|||
func sorted(d) |
|||
for j = 2 to len(d) |
|||
if d[j] < d[j-1] |
|||
return false |
|||
ok |
|||
next |
|||
return true |
|||
func showarray(vect) |
|||
see "[" |
|||
svect = "" |
|||
for n = 1 to len(vect) |
|||
svect = svect + vect[n] + ", " |
|||
next |
|||
svect = left(svect, len(svect) - 2) |
|||
see svect |
|||
see "]" + nl |
|||
</syntaxhighlight> |
|||
Output: |
|||
<pre> |
|||
508888 shuffles required to sort 10 items: |
|||
[0, 1, 2, 2, 4, 31, 65, 83, 99, 782] |
|||
</pre> |
|||
=={{header|RPL}}== |
|||
<code>KNUTH</code> is defined at [[Knuth shuffle#RPL|Knuth shuffle]] |
|||
{{works with|HP|48G}} |
|||
≪ '''WHILE''' DUP ΔLIST ≪ MIN ≫ STREAM 0 < '''REPEAT''' |
|||
<span style="color:blue">KNUTH</span> |
|||
'''END''' |
|||
≫ '<span style="color:blue">BOGOSORT</span>' STO |
|||
=={{header|Ruby}}== |
|||
<syntaxhighlight 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</syntaxhighlight> |
|||
An alternative implementation: |
|||
<syntaxhighlight lang="ruby">def shuffle(l) |
|||
l.sort_by { rand } |
|||
end |
|||
def bogosort(l) |
|||
l = shuffle(l) until l == l.sort |
|||
l |
|||
end</syntaxhighlight> |
|||
{{works with|Ruby|1.8.7+}} |
|||
<syntaxhighlight 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</syntaxhighlight> |
|||
=={{header|Rust}}== |
|||
Works with Rust 1.11+, requires rand module |
|||
{{libheader|rand}} |
|||
<syntaxhighlight lang="rust">extern crate rand; |
|||
use rand::Rng; |
|||
fn bogosort_by<T,F>(order: F, coll: &mut [T]) |
|||
where F: Fn(&T, &T) -> bool |
|||
{ |
|||
let mut rng = rand::thread_rng(); |
|||
while !is_sorted_by(&order, coll) { |
|||
rng.shuffle(coll); |
|||
} |
|||
} |
|||
#[inline] |
|||
fn is_sorted_by<T,F>(order: F, coll: &[T]) -> bool |
|||
where F: Fn(&T,&T) -> bool, |
|||
{ |
|||
coll[..].iter().zip(&coll[1..]).all(|(x,y)| order(x,y)) |
|||
} |
|||
fn main() { |
|||
let mut testlist = [1,55,88,24,990876,312,67,0,854,13,4,7]; |
|||
bogosort_by(|x,y| x < y, &mut testlist); |
|||
println!("{:?}", testlist); |
|||
bogosort_by(|x,y| x > y, &mut testlist); |
|||
println!("{:?}", testlist); |
|||
} |
|||
</syntaxhighlight> |
|||
=={{header|Scala}}== |
|||
{{works with|Scala|2.8}} |
|||
<syntaxhighlight 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))</syntaxhighlight> |
|||
=={{header|Sidef}}== |
|||
<syntaxhighlight lang="ruby">func in_order(a) { |
|||
return true if (a.len <= 1) |
|||
var first = a[0] |
|||
a.last(-1).all { |elem| first <= elem ? do { first = elem; true } : false } |
|||
} |
|||
func bogosort(a) { |
|||
a.shuffle! while !in_order(a) |
|||
return a |
|||
} |
|||
var arr = 5.of { 100.irand } |
|||
say "Before: #{arr}" |
|||
say "After: #{bogosort(arr)}"</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
Before: 57 45 83 85 33 |
|||
After: 33 45 57 83 85 |
|||
</pre> |
|||
=={{header|Scheme}}== |
|||
Uses [[Knuth shuffle]] to shuffle the list. |
|||
<syntaxhighlight lang="scheme">(import (rnrs base (6)) |
|||
(srfi :27 random-bits)) |
|||
(define (shuffle lst) |
|||
(define (swap! vec i j) |
|||
(let ((tmp (vector-ref vec i))) |
|||
(vector-set! vec i (vector-ref vec j)) |
|||
(vector-set! vec j tmp))) |
|||
(define vec (list->vector lst)) |
|||
(let loop ((i (sub1 (vector-length vec)))) |
|||
(unless (zero? i) |
|||
(swap! vec i (random-integer (add1 i))) |
|||
(loop (sub1 i)))) |
|||
(vector->list vec)) |
|||
(define (sorted? lst pred?) |
|||
(cond |
|||
((null? (cdr lst)) #t) |
|||
((pred? (car lst) (cadr lst)) (sorted? (cdr lst) pred?)) |
|||
(else #f))) |
|||
(define (bogosort lst) |
|||
(if (sorted? lst <) |
|||
lst |
|||
(bogosort (shuffle lst)))) |
|||
(let ((input '(5 4 3 2 1))) |
|||
(display "Input: ") |
|||
(display input) |
|||
(newline) |
|||
(display "Output: ") |
|||
(display (bogosort input)) |
|||
(newline))</syntaxhighlight> |
|||
{{out}} |
|||
<pre>Input: (5 4 3 2 1) |
|||
Output: (1 2 3 4 5)</pre> |
|||
=={{header|Smalltalk}}== |
|||
{{works with|GNU Smalltalk}} |
|||
This implementation uses closures rather than extending collections to provide a bogosort method. |
|||
<syntaxhighlight 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.</syntaxhighlight> |
|||
=={{header|SNOBOL4}}== |
|||
<syntaxhighlight lang="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</syntaxhighlight> |
|||
{{out}} |
|||
<pre>1: 5 4 3 2 1 |
|||
2: 2 1 4 3 5 |
|||
. . . . . . |
|||
117: 3 2 1 5 4 |
|||
118: 1 2 3 4 5</pre> |
|||
=={{header|Swift}}== |
|||
<syntaxhighlight lang="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) |
|||
} |
|||
}</syntaxhighlight> |
|||
=={{header|Tcl}}== |
|||
<syntaxhighlight 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 |
|||
}</syntaxhighlight> |
|||
=={{header|TI-83 BASIC}}== |
|||
Same IO as BozoSort (below). |
|||
:"BOGO" |
|||
:L<sub>1</sub>→L<sub>2</sub> |
|||
:Lbl A |
|||
:dim(L<sub>2</sub>)→A |
|||
:For(B,1,dim(L<sub>2</sub>)-1) |
|||
:randInt(1,A)→C |
|||
:L<sub>2</sub>(C)→D |
|||
:L<sub>2</sub>(A)→L<sub>2</sub>(C) |
|||
:D→L<sub>2</sub>(A) |
|||
:A-1→A |
|||
:End |
|||
:For(D,1,dim(L<sub>2</sub>)-1) |
|||
:If L<sub>2</sub>(D)>L<sub>2</sub>(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 L<sub>1</sub>, run prgmSORTBOZO, outputs to L<sub>2</sub> |
|||
:L<sub>1</sub>→L<sub>2</sub> |
|||
:Lbl T |
|||
:0→B |
|||
:For(A,1,dim(L<sub>2</sub>)-1) |
|||
:If L<sub>2</sub>(A)>L<sub>2</sub>(A+1) |
|||
:1→B |
|||
:End |
|||
:If B=0 |
|||
:Goto E |
|||
:randInt(1,dim(L<sub>2</sub>))→C |
|||
:randInt(1,dim(L<sub>2</sub>))→D |
|||
:L<sub>2</sub>(C)→E |
|||
:L<sub>2</sub>(C+1)→L<sub>2</sub>(C) |
|||
:E→L<sub>2</sub>(C+1) |
|||
:Goto T |
|||
:Lbl E |
|||
:DelVar A |
|||
:DelVar B |
|||
:DelVar C |
|||
:DelVar D |
|||
:DelVar E |
|||
:Stop |
|||
=={{header|Ursala}}== |
|||
<syntaxhighlight 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></syntaxhighlight> |
|||
{{out}} |
|||
<pre><0,8,12,47,50,51></pre> |
|||
=={{header|VBA}}== |
|||
{{trans|Phix}}<syntaxhighlight lang="vb">Private Function Knuth(a As Variant) As Variant |
|||
Dim t As Variant, i As Integer |
|||
If Not IsMissing(a) Then |
|||
For i = UBound(a) To LBound(a) + 1 Step -1 |
|||
j = Int((UBound(a) - LBound(a) + 1) * Rnd + LBound(a)) |
|||
t = a(i) |
|||
a(i) = a(j) |
|||
a(j) = t |
|||
Next i |
|||
End If |
|||
Knuth = a |
|||
End Function |
|||
Private Function inOrder(s As Variant) |
|||
i = 2 |
|||
Do While i <= UBound(s) |
|||
If s(i) < s(i - 1) Then |
|||
inOrder = False |
|||
Exit Function |
|||
End If |
|||
i = i + 1 |
|||
Loop |
|||
inOrder = True |
|||
End Function |
|||
Private Function bogosort(ByVal s As Variant) As Variant |
|||
Do While Not inOrder(s) |
|||
Debug.Print Join(s, ", ") |
|||
s = Knuth(s) |
|||
Loop |
|||
bogosort = s |
|||
End Function |
|||
Public Sub main() |
|||
Debug.Print Join(bogosort(Knuth([{1,2,3,4,5,6}])), ", ") |
|||
End Sub</syntaxhighlight> |
|||
<pre>... |
|||
1, 3, 2, 5, 6, 4 |
|||
6, 2, 1, 3, 4, 5 |
|||
2, 6, 5, 4, 1, 3 |
|||
2, 6, 3, 4, 1, 5 |
|||
1, 2, 3, 4, 5, 6</pre> |
|||
=={{header|VBScript}}== |
|||
=====Implementation===== |
|||
<syntaxhighlight 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</syntaxhighlight> |
|||
=====Invocation===== |
|||
<syntaxhighlight 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, ", " )</syntaxhighlight> |
|||
=====A few outputs (timed)===== |
|||
<pre> |
|||
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 |
|||
</pre> |
|||
=={{header|V (Vlang)}}== |
|||
Updated for V (Vlang) version 0.2.2 |
|||
<syntaxhighlight lang="go">import rand |
|||
fn shuffle_array(mut arr []int) { |
|||
for i := arr.len - 1; i >= 0; i-- { |
|||
j := rand.intn(i + 1) |
|||
arr[i], arr[j] = arr[j], arr[i] |
|||
} |
|||
} |
|||
fn is_sorted(arr []int) bool { |
|||
for i := 0; i < arr.len - 1; i++ { |
|||
if arr[i] > arr[i + 1] { |
|||
return false |
|||
} |
|||
} |
|||
return true |
|||
} |
|||
fn sort_array(mut arr []int) { |
|||
for !is_sorted(arr) { |
|||
shuffle_array(mut arr) |
|||
println('After Shuffle: $arr') |
|||
} |
|||
} |
|||
fn main() { |
|||
mut array := [6, 9, 1, 4] |
|||
println('Input: $array') |
|||
sort_array(mut array) |
|||
println('Output: $array') |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre>Input: [6, 9, 1, 4] |
|||
After Shuffle: [1, 9, 6, 4] |
|||
After Shuffle: [4, 1, 6, 9] |
|||
After Shuffle: [1, 9, 4, 6] |
|||
After Shuffle: [9, 1, 4, 6] |
|||
After Shuffle: [9, 6, 1, 4] |
|||
After Shuffle: [1, 4, 6, 9] |
|||
Output: [1, 4, 6, 9]</pre> |
|||
=={{header|Wren}}== |
|||
{{libheader|Wren-sort}} |
|||
<syntaxhighlight lang="wren">import "random" for Random |
|||
import "./sort" for Sort |
|||
var bogoSort = Fn.new { |a| |
|||
var rand = Random.new() |
|||
while (!Sort.isSorted(a)) rand.shuffle(a) |
|||
} |
|||
var a = [31, 41, 59, 26, 53, 58, 97, 93, 23, 84] |
|||
System.print("Before: %(a)") |
|||
bogoSort.call(a) |
|||
System.print("After : %(a)")</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
Before: [31, 41, 59, 26, 53, 58, 97, 93, 23, 84] |
|||
After : [23, 26, 31, 41, 53, 58, 59, 84, 93, 97] |
|||
</pre> |
|||
=={{header|XPL0}}== |
|||
<syntaxhighlight lang="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, ^ )]; |
|||
]</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
-5 1 1 2 3 4 4 5 6 9 |
|||
</pre> |
|||
=={{header|Yabasic}}== |
|||
{{trans|FreeBASIC}} |
|||
<syntaxhighlight lang="yabasic">dim a(5) |
|||
a (0) = 10: a (1) = 1: a (2) = 2: a (3) = -6: a (4) = 3 |
|||
Bogosort(a()) |
|||
for i = 0 to arraysize(a(),1) - 1 |
|||
print a(i), " "; |
|||
next i |
|||
end |
|||
sub shuffle(a()) |
|||
n = arraysize(a(),1) |
|||
m = arraysize(a(),1)*2 |
|||
for k = 1 to m |
|||
i = int(Ran(n)) |
|||
j = int(Ran(n)) |
|||
tmp = a(i) //swap a(i), a(j) |
|||
a(i) = a(j) |
|||
a(j) = tmp |
|||
next k |
|||
end sub |
|||
sub inorder(a()) |
|||
n = arraysize(a(),1) |
|||
for i = 0 to n-2 |
|||
if a(i) > a(i+1) return false |
|||
next i |
|||
return true |
|||
end sub |
|||
sub Bogosort(a()) |
|||
while not inorder(a()) |
|||
shuffle(a()) |
|||
wend |
|||
end sub</syntaxhighlight> |
|||
=={{header|zkl}}== |
|||
<syntaxhighlight lang="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();</syntaxhighlight> |
|||
{{out}} |
|||
<pre>L(1,5,6,7,23,23,123)</pre> |
|||
{{omit from|GUISS}} |
Latest revision as of 11:15, 28 July 2024
![Task](http://static.miraheze.org/rosettacodewiki/thumb/b/ba/Rcode-button-task-crushed.png/64px-Rcode-button-task-crushed.png)
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
- Task
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.
11l
F is_sorted(data)
R all((0 .< data.len - 1).map(i -> @data[i] <= @data[i + 1]))
F bogosort(&data)
L !is_sorted(data)
random:shuffle(&data)
V arr = [2, 1, 3]
bogosort(&arr)
print(arr)
- Output:
[1, 2, 3]
AArch64 Assembly
/* ARM assembly AARCH64 Raspberry PI 3B */
/* program bogosort64.s */
/*******************************************/
/* Constantes file */
/*******************************************/
/* for this file see task include a file in language AArch64 assembly*/
.include "../includeConstantesARM64.inc"
/*********************************/
/* Initialized data */
/*********************************/
.data
sMessResult: .asciz "Value : @ \n"
szCarriageReturn: .asciz "\n"
.align 4
qGraine: .quad 123456
TableNumber: .quad 1,2,3,4,5,6,7,8,9,10
.equ NBELEMENTS, (. - TableNumber) / 8
/*********************************/
/* UnInitialized data */
/*********************************/
.bss
sZoneConv: .skip 24
/*********************************/
/* code section */
/*********************************/
.text
.global main
main: // entry of program
1:
ldr x0,qAdrTableNumber // address number table
mov x1,#NBELEMENTS // number of élements
bl knuthShuffle
// table display elements
ldr x0,qAdrTableNumber // address number table
mov x1,#NBELEMENTS // number of élements
bl displayTable
ldr x0,qAdrTableNumber // address number table
mov x1,#NBELEMENTS // number of élements
bl isSorted // control sort
cmp x0,#1 // sorted ?
bne 1b // no -> loop
100: // standard end of the program
mov x0, #0 // return code
mov x8, #EXIT // request to exit program
svc #0 // perform the system call
qAdrszCarriageReturn: .quad szCarriageReturn
qAdrsMessResult: .quad sMessResult
qAdrTableNumber: .quad TableNumber
/******************************************************************/
/* control sorted table */
/******************************************************************/
/* x0 contains the address of table */
/* x1 contains the number of elements > 0 */
/* x0 return 0 if not sorted 1 if sorted */
isSorted:
stp x2,lr,[sp,-16]! // save registers
stp x3,x4,[sp,-16]! // save registers
mov x2,#0
ldr x4,[x0,x2,lsl #3] // load A[0]
1:
add x2,x2,#1
cmp x2,x1 // end ?
bge 99f
ldr x3,[x0,x2, lsl #3] // load A[i]
cmp x3,x4 // compare A[i],A[i-1]
blt 98f // smaller -> error -> return
mov x4,x3 // no -> A[i-1] = A[i]
b 1b // and loop
98:
mov x0,#0 // error
b 100f
99:
mov x0,#1 // ok -> return
100:
ldp x2,x3,[sp],16 // restaur 2 registers
ldp x1,lr,[sp],16 // restaur 2 registers
ret // return to address lr x30
/******************************************************************/
/* Display table elements */
/******************************************************************/
/* x0 contains the address of table */
/* x1 contains elements number */
displayTable:
stp x1,lr,[sp,-16]! // save registers
stp x2,x3,[sp,-16]! // save registers
mov x2,x0 // table address
mov x4,x1 // elements number
mov x3,#0
1: // loop display table
ldr x0,[x2,x3,lsl #3]
ldr x1,qAdrsZoneConv
bl conversion10 // décimal conversion
ldr x0,qAdrsMessResult
ldr x1,qAdrsZoneConv // insert conversion
bl strInsertAtCharInc
bl affichageMess // display message
add x3,x3,#1
cmp x3,x4 // end ?
blt 1b // no -> loop
ldr x0,qAdrszCarriageReturn
bl affichageMess
100:
ldp x2,x3,[sp],16 // restaur 2 registers
ldp x1,lr,[sp],16 // restaur 2 registers
ret // return to address lr x30
qAdrsZoneConv: .quad sZoneConv
/******************************************************************/
/* shuffle game */
/******************************************************************/
/* x0 contains boxs address */
/* x1 contains elements number */
knuthShuffle:
stp x1,lr,[sp,-16]! // save registers
stp x2,x3,[sp,-16]! // save registers
stp x4,x5,[sp,-16]! // save registers
mov x5,x0 // save table address
mov x2,#0 // start index
1:
mov x0,x2 // generate aleas
bl genereraleas
ldr x3,[x5,x2,lsl #3] // swap number on the table
ldr x4,[x5,x0,lsl #3]
str x4,[x5,x2,lsl #3]
str x3,[x5,x0,lsl #3]
add x2,x2,1 // next number
cmp x2,x1 // end ?
blt 1b // no -> loop
100:
ldp x4,x5,[sp],16 // restaur 2 registers
ldp x2,x3,[sp],16 // restaur 2 registers
ldp x1,lr,[sp],16 // restaur 2 registers
ret // return to address lr x30
/***************************************************/
/* Generation random number */
/***************************************************/
/* x0 contains limit */
genereraleas:
stp x1,lr,[sp,-16]! // save registers
stp x2,x3,[sp,-16]! // save registers
ldr x1,qAdrqGraine
ldr x2,[x1]
ldr x3,qNbDep1
mul x2,x3,x2
ldr x3,qNbDep2
add x2,x2,x3
str x2,[x1] // maj de la graine pour l appel suivant
cmp x0,#0
beq 100f
udiv x3,x2,x0
msub x0,x3,x0,x2 // résult = remainder
100: // end function
ldp x2,x3,[sp],16 // restaur 2 registers
ldp x1,lr,[sp],16 // restaur 2 registers
ret // return to address lr x30
qAdrqGraine: .quad qGraine
qNbDep1: .quad 0x0019660d
qNbDep2: .quad 0x3c6ef35f
/********************************************************/
/* File Include fonctions */
/********************************************************/
/* for this file see task include a file in language AArch64 assembly */
.include "../includeARM64.inc"
Action!
PROC PrintArray(INT ARRAY a INT size)
INT i
Put('[)
FOR i=0 TO size-1
DO
IF i>0 THEN Put(' ) FI
PrintI(a(i))
OD
Put(']) PutE()
RETURN
PROC KnuthShuffle(INT ARRAY tab BYTE size)
BYTE i,j
INT tmp
i=size-1
WHILE i>0
DO
j=Rand(i+1)
tmp=tab(i)
tab(i)=tab(j)
tab(j)=tmp
i==-1
OD
RETURN
BYTE FUNC IsSorted(INT ARRAY tab BYTE size)
BYTE i
IF size<2 THEN
RETURN (1)
FI
FOR i=0 TO size-2
DO
IF tab(i)>tab(i+1) THEN
RETURN (0)
FI
OD
RETURN (1)
PROC BogoSort(INT ARRAY a INT size)
WHILE IsSorted(a,size)=0
DO
KnuthShuffle(a,size)
OD
RETURN
PROC Test(INT ARRAY a INT size)
PrintE("Array before sort:")
PrintArray(a,size)
BogoSort(a,size)
PrintE("Array after sort:")
PrintArray(a,size)
PutE()
RETURN
PROC Main()
INT ARRAY
a(10)=[1 4 65535 0 7 4 20 65530],
b(21)=[3 2 1 0 65535 65534 65533],
c(8)=[101 102 103 104 105 106 107 108],
d(12)=[1 65535 1 65535 1 65535 1
65535 1 65535 1 65535]
Test(a,8)
Test(b,7)
Test(c,8)
Test(d,12)
RETURN
- Output:
Screenshot from Atari 8-bit computer
Array before sort: [1 4 -1 0 7 4 20 -6] Array after sort: [-6 -1 0 1 4 4 7 20] Array before sort: [3 2 1 0 -1 -2 -3] Array after sort: [-3 -2 -1 0 1 2 3] Array before sort: [101 102 103 104 105 106 107 108] Array after sort: [101 102 103 104 105 106 107 108] Array before sort: [1 -1 1 -1 1 -1 1 -1 1 -1 1 -1] Array after sort: [-1 -1 -1 -1 -1 -1 1 1 1 1 1 1]
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;
}
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
ALGOL 68
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
ARM Assembly
/* ARM assembly Raspberry PI */
/* program bogosort.s */
/************************************/
/* Constantes */
/************************************/
.equ STDOUT, 1 @ Linux output console
.equ EXIT, 1 @ Linux syscall
.equ WRITE, 4 @ Linux syscall
/*********************************/
/* Initialized data */
/*********************************/
.data
sMessResult: .ascii "Value : "
sMessValeur: .fill 11, 1, ' ' @ size => 11
szCarriageReturn: .asciz "\n"
.align 4
iGraine: .int 123456
.equ NBELEMENTS, 6
TableNumber: .int 1,2,3,4,5,6,7,8,9,10
/*********************************/
/* UnInitialized data */
/*********************************/
.bss
/*********************************/
/* code section */
/*********************************/
.text
.global main
main: @ entry of program
1:
ldr r0,iAdrTableNumber @ address number table
mov r1,#NBELEMENTS @ number of élements
bl knuthShuffle
@ table display elements
ldr r2,iAdrTableNumber
mov r3,#0
2: @ loop display table
ldr r0,[r2,r3,lsl #2]
ldr r1,iAdrsMessValeur @ display value
bl conversion10 @ call function
ldr r0,iAdrsMessResult
bl affichageMess @ display message
add r3,#1
cmp r3,#NBELEMENTS - 1
ble 2b
ldr r0,iAdrszCarriageReturn
bl affichageMess
ldr r0,iAdrTableNumber @ address number table
mov r1,#NBELEMENTS @ number of élements
bl isSorted @ control sort
cmp r0,#1 @ sorted ?
bne 1b @ no -> loop
100: @ standard end of the program
mov r0, #0 @ return code
mov r7, #EXIT @ request to exit program
svc #0 @ perform the system call
iAdrsMessValeur: .int sMessValeur
iAdrszCarriageReturn: .int szCarriageReturn
iAdrsMessResult: .int sMessResult
iAdrTableNumber: .int TableNumber
/******************************************************************/
/* control sorted table */
/******************************************************************/
/* r0 contains the address of table */
/* r1 contains the number of elements > 0 */
/* r0 return 0 if not sorted 1 if sorted */
isSorted:
push {r2-r4,lr} @ save registers
mov r2,#0
ldr r4,[r0,r2,lsl #2]
1:
add r2,#1
cmp r2,r1
movge r0,#1
bge 100f
ldr r3,[r0,r2, lsl #2]
cmp r3,r4
movlt r0,#0
blt 100f
mov r4,r3
b 1b
100:
pop {r2-r4,lr}
bx lr @ return
/******************************************************************/
/* knuthShuffle Shuffle */
/******************************************************************/
/* r0 contains the address of table */
/* r1 contains the number of elements */
knuthShuffle:
push {r2-r5,lr} @ save registers
mov r5,r0 @ save table address
mov r2,#0 @ start index
1:
mov r0,r2 @ generate aleas
bl genereraleas
ldr r3,[r5,r2,lsl #2] @ swap number on the table
ldr r4,[r5,r0,lsl #2]
str r4,[r5,r2,lsl #2]
str r3,[r5,r0,lsl #2]
add r2,#1 @ next number
cmp r2,r1 @ end ?
blt 1b @ no -> loop
100:
pop {r2-r5,lr}
bx lr @ return
/******************************************************************/
/* display text with size calculation */
/******************************************************************/
/* r0 contains the address of the message */
affichageMess:
push {r0,r1,r2,r7,lr} @ save registres
mov r2,#0 @ counter length
1: @ loop length calculation
ldrb r1,[r0,r2] @ read octet start position + index
cmp r1,#0 @ if 0 its over
addne r2,r2,#1 @ else add 1 in the length
bne 1b @ and loop
@ so here r2 contains the length of the message
mov r1,r0 @ address message in r1
mov r0,#STDOUT @ code to write to the standard output Linux
mov r7, #WRITE @ code call system "write"
svc #0 @ call systeme
pop {r0,r1,r2,r7,lr} @ restaur des 2 registres */
bx lr @ return
/******************************************************************/
/* Converting a register to a decimal unsigned */
/******************************************************************/
/* r0 contains value and r1 address area */
/* r0 return size of result (no zero final in area) */
/* area size => 11 bytes */
.equ LGZONECAL, 10
conversion10:
push {r1-r4,lr} @ save registers
mov r3,r1
mov r2,#LGZONECAL
1: @ start loop
bl divisionpar10U @ unsigned r0 <- dividende. quotient ->r0 reste -> r1
add r1,#48 @ digit
strb r1,[r3,r2] @ store digit on area
cmp r0,#0 @ stop if quotient = 0
subne r2,#1 @ else previous position
bne 1b @ and loop
@ and move digit from left of area
mov r4,#0
2:
ldrb r1,[r3,r2]
strb r1,[r3,r4]
add r2,#1
add r4,#1
cmp r2,#LGZONECAL
ble 2b
@ and move spaces in end on area
mov r0,r4 @ result length
mov r1,#' ' @ space
3:
strb r1,[r3,r4] @ store space in area
add r4,#1 @ next position
cmp r4,#LGZONECAL
ble 3b @ loop if r4 <= area size
100:
pop {r1-r4,lr} @ restaur registres
bx lr @return
/***************************************************/
/* division par 10 unsigned */
/***************************************************/
/* r0 dividende */
/* r0 quotient */
/* r1 remainder */
divisionpar10U:
push {r2,r3,r4, lr}
mov r4,r0 @ save value
//mov r3,#0xCCCD @ r3 <- magic_number lower raspberry 3
//movt r3,#0xCCCC @ r3 <- magic_number higter raspberry 3
ldr r3,iMagicNumber @ r3 <- magic_number raspberry 1 2
umull r1, r2, r3, r0 @ r1<- Lower32Bits(r1*r0) r2<- Upper32Bits(r1*r0)
mov r0, r2, LSR #3 @ r2 <- r2 >> shift 3
add r2,r0,r0, lsl #2 @ r2 <- r0 * 5
sub r1,r4,r2, lsl #1 @ r1 <- r4 - (r2 * 2) = r4 - (r0 * 10)
pop {r2,r3,r4,lr}
bx lr @ leave function
iMagicNumber: .int 0xCCCCCCCD
/***************************************************/
/* Generation random number */
/***************************************************/
/* r0 contains limit */
genereraleas:
push {r1-r4,lr} @ save registers
ldr r4,iAdriGraine
ldr r2,[r4]
ldr r3,iNbDep1
mul r2,r3,r2
ldr r3,iNbDep1
add r2,r2,r3
str r2,[r4] @ maj de la graine pour l appel suivant
cmp r0,#0
beq 100f
mov r1,r0 @ divisor
mov r0,r2 @ dividende
bl division
mov r0,r3 @ résult = remainder
100: @ end function
pop {r1-r4,lr} @ restaur registers
bx lr @ return
/*****************************************************/
iAdriGraine: .int iGraine
iNbDep1: .int 0x343FD
iNbDep2: .int 0x269EC3
/***************************************************/
/* integer division unsigned */
/***************************************************/
division:
/* r0 contains dividend */
/* r1 contains divisor */
/* r2 returns quotient */
/* r3 returns remainder */
push {r4, lr}
mov r2, #0 @ init quotient
mov r3, #0 @ init remainder
mov r4, #32 @ init counter bits
b 2f
1: @ loop
movs r0, r0, LSL #1 @ r0 <- r0 << 1 updating cpsr (sets C if 31st bit of r0 was 1)
adc r3, r3, r3 @ r3 <- r3 + r3 + C. This is equivalent to r3 ? (r3 << 1) + C
cmp r3, r1 @ compute r3 - r1 and update cpsr
subhs r3, r3, r1 @ if r3 >= r1 (C=1) then r3 <- r3 - r1
adc r2, r2, r2 @ r2 <- r2 + r2 + C. This is equivalent to r2 <- (r2 << 1) + C
2:
subs r4, r4, #1 @ r4 <- r4 - 1
bpl 1b @ if r4 >= 0 (N=0) then loop
pop {r4, lr}
bx lr
Arturo
bogoSort: function [items][
a: new items
while [not? sorted? a]-> shuffle 'a
return a
]
print bogoSort [3 1 2 8 5 7 9 4 6]
- Output:
1 2 3 4 5 6 7 8 9
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
}
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]
}
}
BASIC256
global array
dim array = {10, 1, 2, -6, 3}
lb = array[?,]-1 : ub = array[?]-1
print "unsort ";
for i = lb to ub
print rjust(array[i], 4);
next i
call Bogosort(array) # ordenar el array
print chr(10); " sort ";
for i = lb to ub
print rjust(array[i], 4);
next i
end
subroutine shuffle(array)
n = array[?] : m = array[?]*2
for k = 1 to m
i = int(Rand*n)
j = int(Rand*n)
tmp = array[i] #swap lb(i), lb(j)
array[i] = array[j]
array[j] = tmp
next k
end subroutine
function inorder(array)
n = array[?]
for i = 0 to n-2
if array[i] > array[i+1] then return false
next i
return true
end function
subroutine Bogosort(array)
while not inorder(array)
call shuffle(array)
end while
end subroutine
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.
BQN
Requires the _while_
idiom because the recursive version {(𝕊𝕩⊏˜•rand.Deal∘≠)⍟(𝕩≢∧𝕩)𝕩}
quickly runs out of stack depth.
_while_←{𝔽⍟𝔾∘𝔽_𝕣_𝔾∘𝔽⍟𝔾𝕩}
Bogo←{𝕩⊏˜•rand.Deal≠𝕩}_while_(≢⟜∧)
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]
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");
}
C#
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 + " ");
}
}
}
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
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]))
COBOL
This program generates an array of ten pseudo-random numbers in the range 0 to 999 and then sorts them into ascending order. Eventually.
identification division.
program-id. bogo-sort-program.
data division.
working-storage section.
01 array-to-sort.
05 item-table.
10 item pic 999
occurs 10 times.
01 randomization.
05 random-seed pic 9(8).
05 random-index pic 9.
01 flags-counters-etc.
05 array-index pic 99.
05 adjusted-index pic 99.
05 temporary-storage pic 999.
05 shuffles pic 9(8)
value zero.
05 sorted pic 9.
01 numbers-without-leading-zeros.
05 item-no-zeros pic z(4).
05 shuffles-no-zeros pic z(8).
procedure division.
control-paragraph.
accept random-seed from time.
move function random(random-seed) to item(1).
perform random-item-paragraph varying array-index from 2 by 1
until array-index is greater than 10.
display 'BEFORE SORT:' with no advancing.
perform show-array-paragraph varying array-index from 1 by 1
until array-index is greater than 10.
display ''.
perform shuffle-paragraph through is-it-sorted-paragraph
until sorted is equal to 1.
display 'AFTER SORT: ' with no advancing.
perform show-array-paragraph varying array-index from 1 by 1
until array-index is greater than 10.
display ''.
move shuffles to shuffles-no-zeros.
display shuffles-no-zeros ' SHUFFLES PERFORMED.'
stop run.
random-item-paragraph.
move function random to item(array-index).
show-array-paragraph.
move item(array-index) to item-no-zeros.
display item-no-zeros with no advancing.
shuffle-paragraph.
perform shuffle-items-paragraph,
varying array-index from 1 by 1
until array-index is greater than 10.
add 1 to shuffles.
is-it-sorted-paragraph.
move 1 to sorted.
perform item-in-order-paragraph varying array-index from 1 by 1,
until sorted is equal to zero
or array-index is equal to 10.
shuffle-items-paragraph.
move function random to random-index.
add 1 to random-index giving adjusted-index.
move item(array-index) to temporary-storage.
move item(adjusted-index) to item(array-index).
move temporary-storage to item(adjusted-index).
item-in-order-paragraph.
add 1 to array-index giving adjusted-index.
if item(array-index) is greater than item(adjusted-index)
then move zero to sorted.
- Output:
BEFORE SORT: 141 503 930 105 78 518 180 907 791 361 AFTER SORT: 78 105 141 180 361 503 518 791 907 930 237262 SHUFFLES PERFORMED.
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)))
Crystal
def knuthShuffle(items : Array)
i = items.size-1
while i > 1
j = Random.rand(0..i)
items.swap(i, j)
i -= 1
end
end
def sorted?(items : Array)
prev = items[0]
items.each do |item|
if item < prev
return false
end
prev = item
end
return true
end
def bogoSort(items : Array)
while !sorted?(items)
knuthShuffle(items)
end
end
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]
Delphi
See Pascal.
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)
}
}
EasyLang
proc shuffle . l[] .
for i = len l[] downto 2
r = random i
swap l[i] l[r]
.
.
proc issorted . l[] r .
for i = 2 to len l[]
if l[i] < l[i - 1]
r = 0
return
.
.
r = 1
.
proc bogosort . l[] .
repeat
issorted l[] r
until r = 1
shuffle l[]
.
.
list[] = [ 2 7 41 11 3 1 6 5 8 ]
bogosort list[]
print list[]
- Output:
[ 1 2 3 5 6 7 8 11 41 ]
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
Elena
ELENA 5.0 :
import extensions;
import system'routines;
extension op
{
bogoSorter()
{
var list := self;
until (list.isAscendant())
{
list := list.randomize(list.Length)
};
^ list
}
}
public program()
{
var list := new int[]{3, 4, 1, 8, 7, -2, 0};
console.printLine("before:", list.asEnumerable());
console.printLine("after :", list.bogoSorter().asEnumerable())
}
- Output:
before:3,4,1,8,7,-2,0 after :-2,0,1,3,4,7,8
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]
EMal
type BogoSorter
fun isOrdered ← logic by List list
if list.length ≤ 1 do return true end
for int i ← 1; i < list.length; ++i
if list[i] < list[i - 1] do return false end
end
return true
end
fun shuffle ← <List list|list.shuffle()
fun sort ← void by List list
while not isOrdered(list)
shuffle(list)
end
end
type Main
List sample ← int[3, 4, 1, 8, 7, 4, -2]
BogoSorter.sort(sample)
sample.list(<int n|write(n + " "))
writeLine()
- Output:
-2 1 3 4 4 7 8
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}
Factor
USING: grouping kernel math random sequences ;
: sorted? ( seq -- ? ) 2 <clumps> [ first2 <= ] all? ;
: bogosort ( seq -- newseq ) [ dup sorted? ] [ randomize ] until ;
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]))
}
}
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
FreeBASIC
sub shuffle( a() as long )
dim as ulong n = ubound(a), i, j, k, m = ubound(a)*2
dim as ulong tmp
randomize timer
for k=1 to m
i=int(rnd*n)
j=int(rnd*n)
tmp = a(i)
a(i) = a(j)
a(j) = tmp
next k
end sub
function inorder( a() as long ) as boolean
dim as ulong i, n = ubound(a)
for i = 0 to n-2
if a(i)>a(i+1) then
return false
end if
next i
return true
end function
sub bogosort( a() as long )
while not inorder(a())
shuffle(a())
wend
end sub
dim as long a(5) = {10, 1, 2, -6, 3}
dim as long i
bogosort(a())
for i=0 to ubound(a) - 1
print a(i)
next i
Gambas
Click this link to run this code
Public Sub Main()
Dim sSorted As String = "123456789" 'The desired outcome
Dim sTest, sChr As String 'Various strings
Dim iCounter As Integer 'Loop counter
Do
Inc iCounter 'Increase counter value
Repeat 'Repeat
sChr = Chr(Rand(49, 57)) 'Get a random number and convert it to a character e.g. 49="1"
If Not InStr(sTest, sChr) Then sTest &= sChr 'If the random character is not in sTest then add it
Until Len(sTest) = 9 'Loop until sTest has 9 characters
Print sTest 'Print the string to test
If sTest = sSorted Then Break 'If sTest = sSorted then get out of the loop
sTest = "" 'Empty sTest and try again
Loop
Print "Solved in " & Str(iCounter) & " loops" 'Print the result
End
Output: (This example was completed in under 2 seconds)
......... 129536487 345218769 482713659 286745931 123456789 Solved in 155283 loops
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]
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]
Haskell
import System.Random
import Data.Array.IO
import Control.Monad
isSortedBy :: (a -> a -> Bool) -> [a] -> Bool
isSortedBy _ [] = True
isSortedBy f xs = all (uncurry f) . (zip <*> tail) $ xs
-- 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
bogosortBy :: (a -> a -> Bool) -> [a] -> IO [a]
bogosortBy f xs | isSortedBy f xs = return xs
| otherwise = shuffle xs >>= bogosortBy f
bogosort :: Ord a => [a] -> IO [a]
bogosort = bogosortBy (<)
Example:
*Main> bogosort [7,5,12,1,4,2,23,18] [1,2,4,5,7,12,18,23]
Icon and Unicon
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);
}
];
Insitux
(function bogo-sort order list
(return-unless (1 list) [])
(if (... order list)
list
(recur order (shuffle list))))
(bogo-sort < [7 5 12 1 4 2 23 18])
Even with this small list the web REPL sometimes exceeds its default recur budget (1e4 - 10000):
4:6 (recur order (shuffle list)))) Budget Error: recurred too many times.
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 :)
J
bogo=: monad define
whilst. +./ 2 >/\ Ry do. Ry=. (A.~ ?@!@#) y end. Ry
)
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
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);
}
}
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;
}
Julia
function bogosort!(arr::AbstractVector)
while !issorted(arr)
shuffle!(arr)
end
return arr
end
v = rand(-10:10, 10)
println("# unordered: $v\n -> ordered: ", bogosort!(v))
- Output:
# unordered: [-7, 0, -6, -1, -6, -1, -3, -1, 4, 8] -> ordered: [-7, -6, -6, -3, -1, -1, -1, 0, 4, 8]
Kotlin
// version 1.1.2
const val RAND_MAX = 32768 // big enough for this
val rand = java.util.Random()
fun isSorted(a: IntArray): Boolean {
val n = a.size
if (n < 2) return true
for (i in 1 until n) {
if (a[i] < a[i - 1]) return false
}
return true
}
fun shuffle(a: IntArray) {
val n = a.size
if (n < 2) return
for (i in 0 until n) {
val t = a[i]
val r = rand.nextInt(RAND_MAX) % n
a[i] = a[r]
a[r] = t
}
}
fun bogosort(a: IntArray) {
while (!isSorted(a)) shuffle(a)
}
fun main(args: Array<String>) {
val a = intArrayOf(1, 10, 9, 7, 3, 0)
println("Before sorting : ${a.contentToString()}")
bogosort(a)
println("After sorting : ${a.contentToString()}")
}
- Output:
Before sorting : [1, 10, 9, 7, 3, 0] After sorting : [0, 1, 3, 7, 9, 10]
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
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')
Maple
arr := Array([2,3,1]):
len := numelems(arr):
#Translation of C, random swapping
shuffle_arr := proc(arr, len)
local i, r, temp:
for i from 1 to len do
temp := arr[i]:
r := rand(1..len)():
arr[i] := arr[r]:
arr[r] := temp:
end do:
end proc:
while(not ListTools:-Sorted(convert(arr, list))) do
shuffle_arr(arr, len):
end do:
arr;
- Output:
[1 2 3]
Mathematica /Wolfram Language
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}
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
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
)
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.
Nanoquery
def sorted(list)
if len(list) = 0
return true
end
for i in range(0, len(list) - 2)
if list[i] > list[i + 1]
return false
end
end
return true
end
def bogosort(list)
while not sorted(list)
list = list.shuffle()
end
return list
end
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 ");
}
}
NetRexx
/* 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]
Nim
import random
randomize()
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]
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.
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]
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}}
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)
);
};
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
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;}
Phix
with javascript_semantics function inOrder(sequence s) return s==sort(deep_copy(s)) -- <snigger> 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:
... {4,3,1,5,2,6} {1,3,4,6,5,2} {2,3,4,1,5,6} {1,2,3,4,5,6}
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;
}
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)
PL/I
*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
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 ) } )
Prolog
bogo_sort(L,Rl) :-
min_list(L,Min),
repeat,
random_permutation(L,Rl),
is_sorted(Rl,Min),
!.
is_sorted([],_).
is_sorted([N|T],P) :-
N >= P,
is_sorted(T,N).
- Output:
?- bogo_sort( [703,931,12,713,894,232,778,86,700,26] ,Sorted). Sorted = [12,26,86,232,700,703,713,778,894,931] .
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.
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))))
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)))
Quackery
[ true swap
dup [] != if
[ behead swap witheach
[ tuck > if
[ dip not
conclude ] ] ]
drop ] is inorder ( [ --> b )
[ dup inorder not while shuffle again ] is bogosort ( [ --> [ )
R
bogosort <- function(x) {
while(is.unsorted(x)) x <- sample(x)
x
}
n <- c(1, 10, 9, 7, 3, 0)
bogosort(n)
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)
Raku
(formerly 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';
REXX
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
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
Ring
# Project : Sorting algorithms/Bogosort
test = [4, 65, 2, 31, 0, 99, 2, 83, 782, 1]
shuffles = 0
while ! sorted(test)
shuffles = shuffles + 1
shuffle(test)
end
see "" + shuffles + " shuffles required to sort " + len(test) + " items:" + nl
showarray(test)
func shuffle(d)
for i = len(d) to 2 step -1
item = random(i) + 1
if item <= len(d)
temp = d[i-1]
d[i-1] = d[item]
d[item] = temp
else
i = i -1
ok
next
func sorted(d)
for j = 2 to len(d)
if d[j] < d[j-1]
return false
ok
next
return true
func showarray(vect)
see "["
svect = ""
for n = 1 to len(vect)
svect = svect + vect[n] + ", "
next
svect = left(svect, len(svect) - 2)
see svect
see "]" + nl
Output:
508888 shuffles required to sort 10 items: [0, 1, 2, 2, 4, 31, 65, 83, 99, 782]
RPL
KNUTH
is defined at Knuth shuffle
≪ WHILE DUP ΔLIST ≪ MIN ≫ STREAM 0 < REPEAT KNUTH END ≫ 'BOGOSORT' STO
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
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
Rust
Works with Rust 1.11+, requires rand module
extern crate rand;
use rand::Rng;
fn bogosort_by<T,F>(order: F, coll: &mut [T])
where F: Fn(&T, &T) -> bool
{
let mut rng = rand::thread_rng();
while !is_sorted_by(&order, coll) {
rng.shuffle(coll);
}
}
#[inline]
fn is_sorted_by<T,F>(order: F, coll: &[T]) -> bool
where F: Fn(&T,&T) -> bool,
{
coll[..].iter().zip(&coll[1..]).all(|(x,y)| order(x,y))
}
fn main() {
let mut testlist = [1,55,88,24,990876,312,67,0,854,13,4,7];
bogosort_by(|x,y| x < y, &mut testlist);
println!("{:?}", testlist);
bogosort_by(|x,y| x > y, &mut testlist);
println!("{:?}", testlist);
}
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))
Sidef
func in_order(a) {
return true if (a.len <= 1)
var first = a[0]
a.last(-1).all { |elem| first <= elem ? do { first = elem; true } : false }
}
func bogosort(a) {
a.shuffle! while !in_order(a)
return a
}
var arr = 5.of { 100.irand }
say "Before: #{arr}"
say "After: #{bogosort(arr)}"
- Output:
Before: 57 45 83 85 33 After: 33 45 57 83 85
Scheme
Uses Knuth shuffle to shuffle the list.
(import (rnrs base (6))
(srfi :27 random-bits))
(define (shuffle lst)
(define (swap! vec i j)
(let ((tmp (vector-ref vec i)))
(vector-set! vec i (vector-ref vec j))
(vector-set! vec j tmp)))
(define vec (list->vector lst))
(let loop ((i (sub1 (vector-length vec))))
(unless (zero? i)
(swap! vec i (random-integer (add1 i)))
(loop (sub1 i))))
(vector->list vec))
(define (sorted? lst pred?)
(cond
((null? (cdr lst)) #t)
((pred? (car lst) (cadr lst)) (sorted? (cdr lst) pred?))
(else #f)))
(define (bogosort lst)
(if (sorted? lst <)
lst
(bogosort (shuffle lst))))
(let ((input '(5 4 3 2 1)))
(display "Input: ")
(display input)
(newline)
(display "Output: ")
(display (bogosort input))
(newline))
- Output:
Input: (5 4 3 2 1) Output: (1 2 3 4 5)
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.
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
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)
}
}
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
}
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
#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>
VBA
Private Function Knuth(a As Variant) As Variant
Dim t As Variant, i As Integer
If Not IsMissing(a) Then
For i = UBound(a) To LBound(a) + 1 Step -1
j = Int((UBound(a) - LBound(a) + 1) * Rnd + LBound(a))
t = a(i)
a(i) = a(j)
a(j) = t
Next i
End If
Knuth = a
End Function
Private Function inOrder(s As Variant)
i = 2
Do While i <= UBound(s)
If s(i) < s(i - 1) Then
inOrder = False
Exit Function
End If
i = i + 1
Loop
inOrder = True
End Function
Private Function bogosort(ByVal s As Variant) As Variant
Do While Not inOrder(s)
Debug.Print Join(s, ", ")
s = Knuth(s)
Loop
bogosort = s
End Function
Public Sub main()
Debug.Print Join(bogosort(Knuth([{1,2,3,4,5,6}])), ", ")
End Sub
... 1, 3, 2, 5, 6, 4 6, 2, 1, 3, 4, 5 2, 6, 5, 4, 1, 3 2, 6, 3, 4, 1, 5 1, 2, 3, 4, 5, 6
VBScript
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
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, ", " )
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
V (Vlang)
Updated for V (Vlang) version 0.2.2
import rand
fn shuffle_array(mut arr []int) {
for i := arr.len - 1; i >= 0; i-- {
j := rand.intn(i + 1)
arr[i], arr[j] = arr[j], arr[i]
}
}
fn is_sorted(arr []int) bool {
for i := 0; i < arr.len - 1; i++ {
if arr[i] > arr[i + 1] {
return false
}
}
return true
}
fn sort_array(mut arr []int) {
for !is_sorted(arr) {
shuffle_array(mut arr)
println('After Shuffle: $arr')
}
}
fn main() {
mut array := [6, 9, 1, 4]
println('Input: $array')
sort_array(mut array)
println('Output: $array')
}
- Output:
Input: [6, 9, 1, 4] After Shuffle: [1, 9, 6, 4] After Shuffle: [4, 1, 6, 9] After Shuffle: [1, 9, 4, 6] After Shuffle: [9, 1, 4, 6] After Shuffle: [9, 6, 1, 4] After Shuffle: [1, 4, 6, 9] Output: [1, 4, 6, 9]
Wren
import "random" for Random
import "./sort" for Sort
var bogoSort = Fn.new { |a|
var rand = Random.new()
while (!Sort.isSorted(a)) rand.shuffle(a)
}
var a = [31, 41, 59, 26, 53, 58, 97, 93, 23, 84]
System.print("Before: %(a)")
bogoSort.call(a)
System.print("After : %(a)")
- Output:
Before: [31, 41, 59, 26, 53, 58, 97, 93, 23, 84] After : [23, 26, 31, 41, 53, 58, 59, 84, 93, 97]
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
Yabasic
dim a(5)
a (0) = 10: a (1) = 1: a (2) = 2: a (3) = -6: a (4) = 3
Bogosort(a())
for i = 0 to arraysize(a(),1) - 1
print a(i), " ";
next i
end
sub shuffle(a())
n = arraysize(a(),1)
m = arraysize(a(),1)*2
for k = 1 to m
i = int(Ran(n))
j = int(Ran(n))
tmp = a(i) //swap a(i), a(j)
a(i) = a(j)
a(j) = tmp
next k
end sub
sub inorder(a())
n = arraysize(a(),1)
for i = 0 to n-2
if a(i) > a(i+1) return false
next i
return true
end sub
sub Bogosort(a())
while not inorder(a())
shuffle(a())
wend
end sub
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)
- Programming Tasks
- Sorting Algorithms
- Sorting
- 11l
- AArch64 Assembly
- Action!
- ActionScript
- Ada
- ALGOL 68
- ARM Assembly
- Arturo
- AutoHotkey
- AWK
- BASIC256
- BBC BASIC
- BQN
- Brat
- C
- C sharp
- C++
- Clojure
- COBOL
- Common Lisp
- Crystal
- D
- Delphi
- E
- EasyLang
- Eiffel
- Elena
- Elixir
- EMal
- Euphoria
- Factor
- Fantom
- Fortran
- FreeBASIC
- Gambas
- Go
- Groovy
- Haskell
- Icon
- Unicon
- Inform 6
- Insitux
- Io
- J
- Java
- JavaScript
- Julia
- Kotlin
- Lua
- M4
- Maple
- Mathematica
- Wolfram Language
- MATLAB
- Octave
- MAXScript
- Modula-3
- Nanoquery
- Nemerle
- NetRexx
- Nim
- Oberon-2
- OCaml
- Oz
- PARI/GP
- Pascal
- Perl
- Phix
- PHP
- PicoLisp
- PL/I
- PowerShell
- Prolog
- PureBasic
- Python
- Qi
- Quackery
- R
- Racket
- Raku
- REXX
- Ring
- RPL
- Ruby
- Rust
- Rand
- Scala
- Sidef
- Scheme
- Smalltalk
- SNOBOL4
- Swift
- Tcl
- TI-83 BASIC
- Ursala
- VBA
- VBScript
- V (Vlang)
- Wren
- Wren-sort
- XPL0
- Yabasic
- Zkl
- GUISS/Omit