Sorting algorithms/Bogosort: Difference between revisions
no edit summary
No edit summary |
|||
(157 intermediate revisions by 80 users not shown) | |||
Line 1:
{{task|Sorting Algorithms}}
[[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.
Pseudocode:
Line 8 ⟶ 21:
'''done'''
<br>
<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}}==
<
{
while (!sorted(arr))
Line 51 ⟶ 351:
return true;
}</
=={{header|Ada}}==
<
with Ada.Numerics.Discrete_Random;
Line 103 ⟶ 403:
Put (Integer'Image (Sequence (I)));
end loop;
end Test_Bogosort;</
The solution is generic.
The procedure Bogosort can be instantiated
with any copyable comparable type.
In the example given it is the standard Integer type.
{{out}}
<pre>
3 6 7 9
</pre>
=={{header|ALGOL 68}}==
{{trans|python}}
Line 117 ⟶ 422:
{{works with|ELLA ALGOL 68|Any (with appropriate job cards) - tested with release 1.8.8d.fc9.i386}}
<
PROC random shuffle = (REF[]TYPE l)VOID: (
Line 153 ⟶ 458:
[6]TYPE sample := (61, 52, 63, 94, 46, 18);
print((bogo sort(sample), new line))</
{{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}}==
<
MsgBox % Bogosort("319208")
MsgBox % Bogosort("fedcba")
Line 191 ⟶ 764:
}
Return Found
}</
=={{header|AWK}}==
Sort standard input and output to the standard output
<
{
return int(n * rand())
Line 224 ⟶ 797:
print line[i]
}
}</
=={{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}}==
<
#include <stdlib.h>
#include <stdbool.h>
Line 263 ⟶ 926:
for (i=0; i < 6; i++) printf("%d ", numbers[i]);
printf("\n");
}</
=={{header|C sharp|C#}}==
{{works with|C sharp|C#|3.0+}}
<
using System.Collections.Generic;
Line 341 ⟶ 977:
}
}</
=={{header|
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);
}
}
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
(
(recur order (
(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}}==
Line 371 ⟶ 1,106:
<code>nshuffle</code> is the same code as in [[Knuth shuffle#Common Lisp|Knuth shuffle]].
<
(loop for i from (length sequence) downto 2
do (rotatef (elt sequence (random i))
Line 382 ⟶ 1,117:
(defun bogosort (list predicate)
(do ((list list (nshuffle list)))
((sortedp list predicate) list)))</
=={{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}}==
<syntaxhighlight lang="d">import std.stdio, std.algorithm, std.random;
void bogoSort(T)(T[] data) {
while (!isSorted(data))
randomShuffle(data);
}
void main() {
auto
bogoSort(array);
writeln(array);
}</syntaxhighlight>
{{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}}==
Line 415 ⟶ 1,169:
Using the shuffle from [[Knuth shuffle#E]].
<
if (list.size() == 0) { return true }
var a := list[0]
Line 430 ⟶ 1,184:
shuffle(list, random)
}
}</
=={{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
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}}==
<
: sorted? ( seq -- ? ) 2 <clumps> [ first2 <= ] all? ;
: bogosort ( seq -- newseq ) [ dup sorted? ] [ randomize ] until ;</
=={{header|Fantom}}==
<syntaxhighlight lang="fantom">
class Main
{
Bool in_order (Int[] items)
{
(0..<(items.size-1)).toList.all |Int i -> Bool|
{
items[i] <= items[i+1]
}
}
Int[] bogosort (Int[] items)
{
while (!in_order(items))
{
items.shuffle
}
return items
}
Void main ()
{
// example
echo ("Sorting [3,4,2,1] gives " + bogosort ([3,4,2,1]))
}
}
</syntaxhighlight>
=={{header|Fortran}}==
{{works with|Fortran|90 and later}}
<
IMPLICIT NONE
CONTAINS
Line 488 ⟶ 1,541:
WRITE (*,*) "Array required", iter, " shuffles to sort"
END PROGRAM BOGOSORT</
=={{header|FreeBASIC}}==
<syntaxhighlight lang="freebasic">sub shuffle( a() as long )
dim as ulong n = ubound(a), i, j, k, m = ubound(a)*2
dim as ulong tmp
randomize timer
for k=1 to m
i=int(rnd*n)
j=int(rnd*n)
tmp = a(i)
a(i) = a(j)
a(j) = tmp
next k
end sub
function inorder( a() as long ) as boolean
dim as ulong i, n = ubound(a)
for i = 0 to n-2
if a(i)>a(i+1) then
return false
end if
next i
return true
end function
sub bogosort( a() as long )
while not inorder(a())
shuffle(a())
wend
end sub
dim as long a(5) = {10, 1, 2, -6, 3}
dim as long i
bogosort(a())
for i=0 to ubound(a) - 1
print a(i)
next i</syntaxhighlight>
=={{header|Gambas}}==
'''[https://gambas-playground.proko.eu/?gist=b2b766f379d809cbf054c2d32d76c453 Click this link to run this code]'''
<syntaxhighlight lang="gambas">Public Sub Main()
Dim sSorted As String = "123456789" 'The desired outcome
Dim sTest, sChr As String 'Various strings
Dim iCounter As Integer 'Loop counter
Do
Inc iCounter 'Increase counter value
Repeat 'Repeat
sChr = Chr(Rand(49, 57)) 'Get a random number and convert it to a character e.g. 49="1"
If Not InStr(sTest, sChr) Then sTest &= sChr 'If the random character is not in sTest then add it
Until Len(sTest) = 9 'Loop until sTest has 9 characters
Print sTest 'Print the string to test
If sTest = sSorted Then Break 'If sTest = sSorted then get out of the loop
sTest = "" 'Empty sTest and try again
Loop
Print "Solved in " & Str(iCounter) & " loops" 'Print the result
End</syntaxhighlight>
Output: (This example was completed in under 2 seconds)
<pre>
.........
129536487
345218769
482713659
286745931
123456789
Solved in 155283 loops
</pre>
=={{header|Go}}==
<syntaxhighlight lang="go">package main
import (
"fmt"
"math/rand"
"sort"
"time"
)
func main() {
list := []int{31, 41, 59, 26, 53, 58, 97, 93, 23, 84}
rand.Seed(time.Now().UnixNano())
fmt.Println("unsorted:", list)
temp := make([]int, len(list))
copy(temp, list)
for !sort.IntsAreSorted(temp) {
for i, v := range rand.Perm(len(list)) {
temp[i] = list[v]
}
}
fmt.Println("sorted! ", temp)
}</syntaxhighlight>
{{out}} (sometimes takes a few seconds)
<pre>
unsorted: [31 41 59 26 53 58 97 93 23 84]
sorted! [23 26 31 41 53 58 59 84 93 97]
</pre>
=={{header|Groovy}}==
Solution (also implicitly tracks the number of shuffles required):
<
def n = list.size()
}
list
}</
Test Program:
<
<pre>..............................[1, 2, 3]</pre>
<pre>...................................................[1, 2, 3]</pre>
=={{header|Haskell}}==
<
import Data.Array.IO
import Control.Monad
isSortedBy :: (a -> a -> Bool) -> [a] -> Bool
isSortedBy _ [] = True
isSortedBy f xs = all (uncurry f) . (zip <*> tail) $ xs
-- from http://www.haskell.org/haskellwiki/Random_shuffle
shuffle :: [a] -> IO [a]
Line 535 ⟶ 1,688:
newArray :: Int -> [a] -> IO (IOArray Int a)
newArray n xs = newListArray (1,n) xs
bogosortBy :: (a -> a -> Bool) -> [a] -> IO [a]
bogosortBy f xs | isSortedBy f xs = return xs
| otherwise = shuffle xs >>= bogosortBy f
bogosort ::
bogosort = bogosortBy (<)</syntaxhighlight>
Example:
<pre>
Line 545 ⟶ 1,701:
</pre>
==
<syntaxhighlight lang="icon">procedure shuffle(l)
repeat {
!l :=: ?l
Line 563 ⟶ 1,718:
l := [6,3,4,5,1]
|( shuffle(l) & sorted(l)) \1 & every writes(" ",!l)
end</
=={{header|Inform 6}}==
<syntaxhighlight lang="inform 6">[ shuffle a n i j tmp;
for(i = n - 1: i > 0: i--)
{
j = random(i + 1) - 1;
tmp = a->j;
a->j = a->i;
a->i = tmp;
}
];
[ is_sorted a n i;
for(i = 0: i < n - 1: i++)
{
if(a->i > a->(i + 1)) rfalse;
}
rtrue;
];
[ bogosort a n;
while(~~is_sorted(a, n))
{
shuffle(a, n);
}
];</syntaxhighlight>
=={{header|Insitux}}==
{{Trans|Clojure}}
<syntaxhighlight lang="insitux">(function bogo-sort order list
(return-unless (1 list) [])
(if (... order list)
list
(recur order (shuffle list))))
(bogo-sort < [7 5 12 1 4 2 23 18])</syntaxhighlight>
Even with this small list the web REPL sometimes exceeds its default recur budget (1e4 - 10000):
<pre>4:6 (recur order (shuffle list))))
Budget Error: recurred too many times.</pre>
=={{header|Io}}==
<
isSorted := method(
slice(1) foreach(i, x,
Line 584 ⟶ 1,782:
lst := list(2, 1, 4, 3)
lst bogoSortInPlace println # ==> list(1, 2, 3, 4), hopefully :)</
=={{header|J}}==
{{eff note|J|/:~}}
<
whilst.
)</
=={{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+}}
This implementation works for all comparable types (types with <tt>compareTo</tt> defined).
<
import java.util.List;
import java.util.Iterator;
Line 618 ⟶ 1,881:
Collections.shuffle(list);
}
}</
=={{header|JavaScript}}==
<
for(var j, x, i = v.length; i; j =
return v;
};
Line 640 ⟶ 1,903:
}
return v;
}</
=={{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}}==
<
if type (list) ~= 'table' then return list end
Line 668 ⟶ 1,993:
return list
end</
=={{header|M4}}==
<
define(`randSeed',141592653)
define(`setRand',
Line 710 ⟶ 2,035:
show(`b')
bogosort(`b')
show(`b')</
=={{header|
<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}</
=={{header|MATLAB}} / {{header|Octave}}==
<
while( ~issorted(list) ) %Check to see if it is sorted
list = list( randperm(numel(list)) ); %Randomly sort the list
end
end</
{{out}}
<
ans =
1 2 3 4 5 6 7 8 9
</syntaxhighlight>
=={{header|MAXScript}}==
<
(
if arr.count > 0 then
Line 770 ⟶ 2,114:
)
arr
)</
=={{header|Modula-3}}==
<
IMPORT IO, Fmt, Random;
Line 819 ⟶ 2,163:
END;
IO.Put("\nRequired " & Fmt.Int(count) & " shuffles\n");
END Bogo.</
=={{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}}==
{{Works with|Oxford Oberon-2 Compiler}}
<
IMPORT Out, Random;
Line 873 ⟶ 2,358:
END;
Out.Ln;
END Bogo.</
Init initializes the array as 1 thru 10, then it is shuffled, and then the while loop continually shuffles until Sorted returns true.
=={{header|OCaml}}==
<
| e1 :: e2 :: r -> comp e1 e2 <= 0 && is_sorted comp (e2 :: r)
| _ -> true
Line 897 ⟶ 2,382:
li
else
bogosort (shuffle li)</
Example:
<pre>
Line 903 ⟶ 2,388:
- : int list = [1; 2; 4; 5; 7; 12; 18; 23]
</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.
<
proc {BogoSort Arr}
for while:{Not {InOrder Arr}} do
Line 970 ⟶ 2,423:
in
{BogoSort X}
{Show {Array.toRecord unit X}}</
=={{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}}==
<
sub bogosort
Line 985 ⟶ 2,523:
{$_ >= $last or return 0;
$last = $_;}
return 1;}</
=={{header|Phix}}==
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<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>
<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>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<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}}==
<
while (!in_order($l))
shuffle($l);
Line 999 ⟶ 2,564:
return FALSE;
return TRUE;
}</
=={{header|PicoLisp}}==
<
(loop
(map
'((L) (rot L (rand 1 (length L))))
Lst )
(T (apply <= Lst) Lst) ) )</
{{out}}
<pre>: (bogosort (make (do 9 (link (rand 1 999)))))
-> (1 167 183 282 524 556 638 891 902)
Line 1,017 ⟶ 2,582:
: (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}}==
<
Protected i, Size = ArraySize(a())
For i = 0 To Size
Line 1,051 ⟶ 2,737:
Next
BogoSort(b())</
{{out}}
<pre>Array of 10 integers required 2766901 shuffles To SORT.</pre>
=={{header|Python}}==
<
def bogosort(l):
Line 1,071 ⟶ 2,757:
return False
last = x
return True</
Alternative definition for ''in_order'' (Python 2.5)
<
return all( l[i] <= l[i+1] for i in xrange(0,len(l)-1))</
An alternative implementation for Python 2.5 or later:
<
def bogosort(lst):
random.shuffle(lst) # must shuffle it first or it's a bug if lst was pre-sorted! :)
while lst != sorted(lst):
random.shuffle(lst)
return lst</
Another alternative implementation, using iterators for maximum efficiency:
<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}}==
<
while(is.unsorted(x)) x <- sample(x)
x
}
n <- c(1, 10, 9, 7, 3, 0)
=={{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}}==
<
l.sort_by { rand }
end
Line 1,108 ⟶ 3,143:
def in_order(l)
(0..l.length-2).all? {|i| l[i] <= l[i+1] }
end</
An alternative implementation:
<
l.sort_by { rand }
end
Line 1,119 ⟶ 3,154:
l = shuffle(l) until l == l.sort
l
end</
{{works with|Ruby|1.8.7+}}
<
(0..l.length-2).all? {|i| l[i] <= l[i+1] }
end
Line 1,130 ⟶ 3,165:
l.shuffle! until in_order(l)
l
end</
=={{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}}
<
def bogosort(l: List[Int]): List[Int] = if (isSorted(l)) l else bogosort(scala.util.Random.shuffle(l))</
=={{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}}==
Line 1,141 ⟶ 3,269:
This implementation uses closures rather than extending collections to provide a bogosort method.
<
|isit|
isit := false.
Line 1,164 ⟶ 3,292:
tobesorted := { 2 . 7 . 5 . 3 . 4 . 8 . 6 . 1 }.
bogosort value: tobesorted.
tobesorted displayNl.</
=={{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}}==
<
proc shuffleInPlace {listName} {
Line 1,196 ⟶ 3,400:
}
return $list
}</
=={{header|TI-83 BASIC}}==
Line 1,247 ⟶ 3,451:
=={{header|Ursala}}==
<
#import nat
Line 1,256 ⟶ 3,460:
#cast %nL
example = bogosort <8,50,0,12,47,51></
{{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
Line 1,292 ⟶ 3,539:
next
inOrder = res
end function</syntaxhighlight>
=====Invocation=====
<syntaxhighlight lang="vb">dim a
a = array(11, 1, 2, 3, 4, 4, 6, 7, 8)
Line 1,306 ⟶ 3,551:
wend
wscript.echo timer-t, "seconds"
wscript.echo join( a, ", " )</syntaxhighlight>
=====A few outputs (timed)=====
Line 1,320 ⟶ 3,564:
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}}
|