Sorting algorithms/Bogosort: Difference between revisions
Content deleted Content added
Add Factor |
No edit summary |
||
(208 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}}== |
=={{header|ActionScript}}== |
||
<syntaxhighlight lang="actionscript">public function bogoSort(arr:Array):Array |
|||
<lang actionscript> |
|||
public function bogoSort(arr:Array):Array |
|||
{ |
{ |
||
while (!sorted(arr)) |
while (!sorted(arr)) |
||
Line 44: | Line 351: | ||
return true; |
return true; |
||
}</syntaxhighlight> |
|||
} |
|||
</lang> |
|||
=={{header|Ada}}== |
=={{header|Ada}}== |
||
<syntaxhighlight lang="ada">with Ada.Text_IO; use Ada.Text_IO; |
|||
<lang ada> |
|||
with Ada.Text_IO; use Ada.Text_IO; |
|||
with Ada.Numerics.Discrete_Random; |
with Ada.Numerics.Discrete_Random; |
||
Line 98: | 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. |
|||
</lang> |
|||
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|ALGOL 68}}== |
|||
{{trans|python}} |
|||
{{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()) |
|||
} |
|||
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] |
|||
} |
|||
}</syntaxhighlight> |
|||
=={{header|BASIC256}}== |
|||
{{trans|FreeBASIC}} |
|||
<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}}== |
=={{header|C}}== |
||
< |
<syntaxhighlight lang="c">#include <stdio.h> |
||
#include <stdlib.h> |
#include <stdlib.h> |
||
#include <stdbool.h> |
#include <stdbool.h> |
||
Line 141: | Line 926: | ||
for (i=0; i < 6; i++) printf("%d ", numbers[i]); |
for (i=0; i < 6; i++) printf("%d ", numbers[i]); |
||
printf("\n"); |
printf("\n"); |
||
}</ |
}</syntaxhighlight> |
||
=={{header|C++}}== |
|||
The following algorithm actually works for all sequences of comparable types; restricting to lists of integers would not make the code simpler. |
|||
<lang cpp>#include <iterator> |
|||
#include <algorithm> |
|||
template<typename ForwardIterator> |
|||
void bogosort(ForwardIterator begin, ForwardIterator end) |
|||
{ |
|||
typedef std::iterator_traits<ForwardIterator>::value_type value_type; |
|||
// if we find two adjacent values where the first is greater than the second, the sequence isn't sorted. |
|||
while (std::adjacent_find(begin, end, std::greater<value_type>()) != end) |
|||
std::random_shuffle(begin, end); |
|||
}</lang> |
|||
Using the is_sorted function, part of the SGI STL implementation: |
|||
{{works with|GCC}} |
|||
<lang cpp>#include <algorithm> |
|||
#include <ext/algorithm> |
|||
template<typename ForwardIterator> |
|||
void bogosort(ForwardIterator begin, ForwardIterator end) |
|||
{ |
|||
while (!__gnu_cxx::is_sorted(begin, end)) |
|||
std::random_shuffle(begin, end); |
|||
}</lang> |
|||
=={{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; |
||
using System; |
|||
using System.Collections.Generic; |
using System.Collections.Generic; |
||
Line 220: | 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); |
|||
} |
|||
} |
} |
||
</lang> |
|||
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; |
|||
<lang 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> |
|||
=={{header|EasyLang}}== |
|||
<syntaxhighlight> |
|||
proc shuffle . l[] . |
|||
for i = len l[] downto 2 |
|||
r = randint 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[] |
|||
</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 |
|||
{ |
|||
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()) |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
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 |
|||
}</lang> |
|||
defp sorted?([x, y | _]) when x>y, do: false |
|||
defp sorted?([_, y | rest]), do: sorted?([y | rest]) |
|||
end</syntaxhighlight> |
|||
Example: |
|||
<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 inOrder ← 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 inOrder(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> |
|||
-2 1 3 4 4 7 8 |
|||
</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}}== |
=={{header|Factor}}== |
||
<syntaxhighlight lang="factor">USING: grouping kernel math random sequences ; |
|||
<lang factor> |
|||
USING: grouping kernel math random sequences ; |
|||
: sorted? ( seq -- ? ) 2 <clumps> [ first2 <= ] all? ; |
: sorted? ( seq -- ? ) 2 <clumps> [ first2 <= ] all? ; |
||
: bogosort ( seq -- newseq ) [ dup sorted? ] [ randomize ] until ; |
: bogosort ( seq -- newseq ) [ dup sorted? ] [ randomize ] until ;</syntaxhighlight> |
||
</lang> |
|||
=={{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}}== |
=={{header|Fortran}}== |
||
{{works with|Fortran|90 and later}} |
{{works with|Fortran|90 and later}} |
||
<lang |
<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 |
|||
Sorted = .TRUE. |
|||
s = Sorted(array) |
|||
IF (s) EXIT |
|||
CALL SHUFFLE(array) |
|||
Sorted = .FALSE. |
|||
iter = iter + 1 |
|||
END DO |
|||
WRITE (*,*) "Array required", iter, " shuffles to sort" |
|||
END DO |
|||
END FUNCTION Sorted |
|||
END PROGRAM BOGOSORT</syntaxhighlight> |
|||
SUBROUTINE SHUFFLE(a) |
|||
INTEGER, INTENT(IN OUT) :: a(:) |
|||
INTEGER :: i, rand, temp |
|||
REAL :: x |
|||
DO i = SIZE(a), 1, -1 |
|||
CALL RANDOM_NUMBER(x) |
|||
rand = INT(x * i) + 1 |
|||
temp = a(rand) |
|||
a(rand) = a(i) |
|||
a(i) = temp |
|||
END DO |
|||
END SUBROUTINE |
|||
END MODULE |
|||
PROGRAM BOGOSORT |
|||
USE BOGO |
|||
IMPLICIT NONE |
|||
INTEGER :: iter = 0 |
|||
INTEGER :: array(8) = (/2, 7, 5, 3, 4, 8, 6, 1/) |
|||
LOGICAL :: s |
|||
DO |
|||
s = Sorted(array) |
|||
IF (s) EXIT |
|||
CALL SHUFFLE(array) |
|||
iter = iter + 1 |
|||
END DO |
|||
WRITE (*,*) "Array required", iter, " shuffles to sort" |
|||
END PROGRAM BOGOSORT</lang> |
|||
=={{header| |
=={{header|FreeBASIC}}== |
||
<syntaxhighlight lang="freebasic">sub shuffle( a() as long ) |
|||
<lang haskell>import System.Random |
|||
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 |
|||
isSorted (e1:e2:r) = e1 <= e2 && isSorted (e2:r) |
|||
isSorted _ = True |
|||
-- from http://www.haskell.org/haskellwiki/Random_shuffle |
-- from http://www.haskell.org/haskellwiki/Random_shuffle |
||
shuffle :: [a] -> IO [a] |
shuffle :: [a] -> IO [a] |
||
Line 334: | 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</lang> |
|||
Example: |
Example: |
||
<pre> |
<pre> |
||
Line 344: | Line 1,701: | ||
</pre> |
</pre> |
||
=={{header|Icon}}== |
=={{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 |
|||
!l :=: ?l |
|||
end |
|||
suspend l |
|||
} |
|||
procedure main() |
|||
end |
|||
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> |
|||
procedure sorted(l) |
|||
local i |
|||
Even with this small list the web REPL sometimes exceeds its default recur budget (1e4 - 10000): |
|||
if (i := 2 to *l & l[i] >= l[i-1]) then return &fail else return 1 |
|||
end |
|||
<pre>4:6 (recur order (shuffle list)))) |
|||
Budget Error: recurred too many times.</pre> |
|||
procedure main() |
|||
local l |
|||
=={{header|Io}}== |
|||
l := [6,3,4,5,1] |
|||
<syntaxhighlight lang="io">List do( |
|||
|( shuffle(l) & sorted(l)) \1 & every writes(" ",!l) |
|||
isSorted := method( |
|||
end |
|||
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 395: | Line 1,881: | ||
Collections.shuffle(list); |
Collections.shuffle(list); |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
=={{header|JavaScript}}== |
=={{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); |
|||
shuffle = function(v){ |
|||
for(var j, x, i = v.length; i; j = parseInt(Math.random() * i), x = v[--i], v[i] = v[j], v[j] = x); |
|||
return v; |
return v; |
||
}; |
}; |
||
Line 419: | Line 1,903: | ||
} |
} |
||
return 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 = |
|||
</lang> |
|||
( |
|||
while notSorted arr do |
|||
( |
|||
arr = shuffle arr |
|||
) |
|||
arr |
|||
)</syntaxhighlight> |
|||
=={{header|Modula-3}}== |
=={{header|Modula-3}}== |
||
< |
<syntaxhighlight lang="modula3">MODULE Bogo EXPORTS Main; |
||
IMPORT IO, Random; |
IMPORT IO, Fmt, Random; |
||
VAR a := ARRAY [1.. |
VAR a := ARRAY [1..5] OF INTEGER {1, 2, 3, 4, 5}; |
||
count := 0; |
|||
PROCEDURE Shuffle(VAR a: ARRAY OF INTEGER) = |
PROCEDURE Shuffle(VAR a: ARRAY OF INTEGER) = |
||
Line 447: | Line 2,141: | ||
PROCEDURE Sorted(VAR a: ARRAY OF INTEGER): BOOLEAN = |
PROCEDURE Sorted(VAR a: ARRAY OF INTEGER): BOOLEAN = |
||
BEGIN |
BEGIN |
||
IF |
IF NUMBER(a) <= 1 THEN |
||
RETURN TRUE; |
RETURN TRUE; |
||
END; |
END; |
||
Line 462: | Line 2,156: | ||
WHILE NOT Sorted(a) DO |
WHILE NOT Sorted(a) DO |
||
Shuffle(a); |
Shuffle(a); |
||
INC(count); |
|||
END; |
END; |
||
FOR i := FIRST(a) TO LAST(a) DO |
FOR i := FIRST(a) TO LAST(a) DO |
||
Line 467: | Line 2,162: | ||
IO.Put(" "); |
IO.Put(" "); |
||
END; |
END; |
||
IO.Put("\nRequired " & Fmt.Int(count) & " shuffles\n"); |
|||
IO.PutChar('\n'); |
|||
END Bogo.</ |
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 522: | Line 2,358: | ||
END; |
END; |
||
Out.Ln; |
Out.Ln; |
||
END Bogo.</ |
END Bogo.</syntaxhighlight> |
||
Init initializes the array as 1 thru 10, then it is shuffled, and then the while loop continually shuffles until Sorted returns true. |
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 |
|||
<lang 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 548: | Line 2,382: | ||
li |
li |
||
else |
else |
||
bogosort (shuffle li) |
bogosort (shuffle li)</syntaxhighlight> |
||
</lang> |
|||
Example: |
Example: |
||
<pre> |
<pre> |
||
Line 555: | 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); |
|||
<lang 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;}}</lang> |
|||
<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}}== |
||
< |
<syntaxhighlight lang="php">function bogosort($l) { |
||
while (!in_order($l)) |
while (!in_order($l)) |
||
shuffle($l); |
shuffle($l); |
||
Line 590: | 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}}== |
||
< |
<syntaxhighlight lang="python">import random |
||
def bogosort(l): |
def bogosort(l): |
||
Line 608: | 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) |
||
< |
<syntaxhighlight lang="python">def in_order(l): |
||
return all( l[i] <= l[i+1] for i in xrange(0,len(l)-1))</ |
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 |
|||
<lang 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> |
||
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}}== |
=={{header|Ruby}}== |
||
< |
<syntaxhighlight lang="ruby">def shuffle(l) |
||
l.sort_by { rand } |
l.sort_by { rand } |
||
end |
end |
||
Line 635: | Line 3,143: | ||
def in_order(l) |
def in_order(l) |
||
(0..l.length-2).all? {|i| l[i] <= l[i+1] } |
(0..l.length-2).all? {|i| l[i] <= l[i+1] } |
||
end</ |
end</syntaxhighlight> |
||
An alternative implementation: |
An alternative implementation: |
||
< |
<syntaxhighlight lang="ruby">def shuffle(l) |
||
l.sort_by { rand } |
l.sort_by { rand } |
||
end |
end |
||
Line 646: | Line 3,154: | ||
l = shuffle(l) until l == l.sort |
l = shuffle(l) until l == l.sort |
||
l |
l |
||
end</ |
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}} |