Sorting algorithms/Bogosort: Difference between revisions
no edit summary
m (→{{header|C++}}) |
No edit summary |
||
(112 intermediate revisions by 52 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 9 ⟶ 21:
'''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}}==
<
{
while (!sorted(arr))
Line 48 ⟶ 351:
return true;
}</
=={{header|Ada}}==
<
with Ada.Numerics.Discrete_Random;
Line 100 ⟶ 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 114 ⟶ 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 150 ⟶ 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 188 ⟶ 764:
}
Return Found
}</
=={{header|AWK}}==
Sort standard input and output to the standard output
<
{
return int(n * rand())
Line 221 ⟶ 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}}==
<
test() = 4, 65, 2, 31, 0, 99, 2, 83, 782, 1
Line 247 ⟶ 868:
IF d(I%) < d(I%-1) THEN = FALSE
NEXT
= TRUE</
{{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}}==
<
sorted = list.sort #Kinda cheating here
while { list != sorted } { list.shuffle! }
Line 260 ⟶ 887:
}
p bogosort [15 6 2 9 1 3 41 19]</
=={{header|C}}==
<
#include <stdlib.h>
#include <stdbool.h>
Line 299 ⟶ 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 379 ⟶ 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 409 ⟶ 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 420 ⟶ 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}}==
<
void bogoSort(T)(T[] data) {
Line 434 ⟶ 1,159:
bogoSort(array);
writeln(array);
}</
{{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 442 ⟶ 1,169:
Using the shuffle from [[Knuth shuffle#E]].
<
if (list.size() == 0) { return true }
var a := list[0]
Line 457 ⟶ 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}}==
<
object temp
integer j
Line 491 ⟶ 1,443:
end function
? bogosort(shuffle({1,2,3,4,5,6}))</
{{out}}
<pre>{1,2,5,4,6,3}
{5,1,3,6,2,4}
Line 504 ⟶ 1,456:
=={{header|Factor}}==
<
: sorted? ( seq -- ? ) 2 <clumps> [ first2 <= ] all? ;
: bogosort ( seq -- newseq ) [ dup sorted? ] [ randomize ] until ;</
=={{header|Fantom}}==
<
class Main
{
Line 537 ⟶ 1,489:
}
}
</syntaxhighlight>
=={{header|Fortran}}==
{{works with|Fortran|90 and later}}
<
IMPLICIT NONE
CONTAINS
Line 589 ⟶ 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}}==
<
import (
Line 615 ⟶ 1,637:
}
fmt.Println("sorted! ", temp)
}</
<pre>
unsorted: [31 41 59 26 53 58 97 93 23 84]
Line 624 ⟶ 1,646:
=={{header|Groovy}}==
Solution (also implicitly tracks the number of shuffles required):
<
def n = list.size()
while (n > 1 && (1..<n).any{ list[it-1] > list[it] }) {
Line 631 ⟶ 1,653:
}
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 665 ⟶ 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 676 ⟶ 1,702:
=={{header|Icon}} and {{header|Unicon}}==
<
repeat {
!l :=: ?l
Line 692 ⟶ 1,718:
l := [6,3,4,5,1]
|( shuffle(l) & sorted(l)) \1 & every writes(" ",!l)
end</
=={{header|Inform 6}}==
<
for(i = n - 1: i > 0: i--)
{
Line 720 ⟶ 1,746:
shuffle(a, n);
}
];</
=={{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 739 ⟶ 1,782:
lst := list(2, 1, 4, 3)
lst bogoSortInPlace println # ==> list(1, 2, 3, 4), hopefully :)</
=={{header|J}}==
{{eff note|J|/:~}}
<
whilst. +./ 2 >/\ Ry do. Ry=. (A.~ ?@!@#) y end. Ry
)</
=={{header|Java}}==
Without Collections, Lists or Iterators. With a counter.
<
public class BogoSort
Line 804 ⟶ 1,848:
}
</syntaxhighlight>
{{out}}
<pre>Unsorted: 4 5 6 0 7 8 9 1 2 3
This took 23104714 shuffles.
Line 814 ⟶ 1,858:
{{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 837 ⟶ 1,881:
Collections.shuffle(list);
}
}</
=={{header|JavaScript}}==
<
for(var j, x, i = v.length; i; j = Math.floor(Math.random() * i), x = v[--i], v[i] = v[j], v[j] = x);
return v;
Line 859 ⟶ 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 887 ⟶ 1,993:
return list
end</
=={{header|M4}}==
<
define(`randSeed',141592653)
define(`setRand',
Line 929 ⟶ 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 989 ⟶ 2,114:
)
arr
)</
=={{header|Modula-3}}==
<
IMPORT IO, Fmt, Random;
Line 1,038 ⟶ 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}}==
<
using System.Console;
using Nemerle.Imperative;
Line 1,079 ⟶ 2,227:
foreach (i in sortme) Write($"$i ");
}
}</
=={{header|NetRexx}}==
{{trans|Java}}
<
options replace format comments java crossref savelog symbols nobinary
Line 1,129 ⟶ 2,277:
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 1,188 ⟶ 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 1,212 ⟶ 2,382:
li
else
bogosort (shuffle li)</
Example:
<pre>
Line 1,222 ⟶ 2,392:
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 1,253 ⟶ 2,423:
in
{BogoSort X}
{Show {Array.toRecord unit X}}</
=={{header|PARI/GP}}==
This implementation sorts 9 distinct elements in only 600 milliseconds.
<
while(1,
my(u=vecextract(v,numtoperm(#v,random((#v)!))));
Line 1,263 ⟶ 2,433:
return(u)
);
};</
=={{header|Pascal}}==
<
const
Line 1,331 ⟶ 2,501:
a[i] := (max + 1) - i;
bogo(a);
end.</
{{out}}
<pre>1: 5 4 3 2 1
2: 3 5 4 1 2
Line 1,341 ⟶ 2,511:
=={{header|Perl}}==
<
sub bogosort
Line 1,353 ⟶ 2,523:
{$_ >= $last or return 0;
$last = $_;}
return 1;}</
=={{header|
<!--<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 1,377 ⟶ 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,395 ⟶ 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]]
<
$c = $a.Clone() # make copy to avoid clobbering $a
1..($c.Length - 1) | ForEach-Object {
Line 1,426 ⟶ 2,684:
}
$l = 7; BogoSort ( 1..$l | ForEach-Object { $Rand = New-Object Random }{ $Rand.Next( 0, $l - 1 ) } )</
=={{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,461 ⟶ 2,737:
Next
BogoSort(b())</
{{out}}
<pre>Array of 10 integers required 2766901 shuffles To SORT.</pre>
=={{header|Python}}==
<
def bogosort(l):
Line 1,481 ⟶ 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
Line 1,520 ⟶ 2,811:
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}}==
Line 1,538 ⟶ 2,838:
is unit tests and an example.
<
#lang racket
(define (bogo-sort l) (if (apply <= l) l (bogo-sort (shuffle l))))
Line 1,549 ⟶ 2,849:
(displayln unsorted)
(displayln (bogo-sort unsorted)))
</syntaxhighlight>
<pre>
(703 931 12 713 894 232 778 86 700 26)
Line 1,557 ⟶ 2,857:
</pre>
=={{header|
(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
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
exit /*stick a fork in it, we're done.*/
/*──────────────────────────────────TELL subroutine─────────────────────*/
tell: say;
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</
{{out}}
<pre style="height:30ex
─────────────────before bogo sort─────────────────
number of bogo sorts performed =
───────────────── after bogo sort─────────────────
after bogo
after bogo
after bogo
after bogo
after bogo
after bogo
after bogo
after bogo
after bogo
after bogo
after bogo
after bogo
after bogo
after bogo
after bogo
after bogo
after bogo
after bogo
after bogo
after bogo
after bogo
after bogo
after bogo
after bogo
after bogo
after bogo
after bogo
after bogo
after bogo
after bogo
after bogo
after bogo
after bogo
after bogo
after bogo
after bogo
after bogo
after bogo
after bogo
after bogo
</pre>
More tests showed that:
<
number of bogo sorts performed = 2583
number of bogo sorts performed = 2376
Line 1,721 ⟶ 3,073:
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,734 ⟶ 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,745 ⟶ 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,756 ⟶ 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,767 ⟶ 3,269:
This implementation uses closures rather than extending collections to provide a bogosort method.
<
|isit|
isit := false.
Line 1,790 ⟶ 3,292:
tobesorted := { 2 . 7 . 5 . 3 . 4 . 8 . 6 . 1 }.
bogosort value: tobesorted.
tobesorted displayNl.</
=={{header|SNOBOL4}}==
<
-include 'Random.sno'
Line 1,834 ⟶ 3,336:
* # Test and display
bogo(s2a('5 4 3 2 1',5))
end</
{{out}}
<pre>1: 5 4 3 2 1
2: 2 1 4 3 5
Line 1,844 ⟶ 3,346:
=={{header|Swift}}==
<syntaxhighlight lang="swift">import Darwin
func shuffle<T>(inout array: [T]) {
for
let j = Int(arc4random_uniform(UInt32(i)))
(array[i], array[j]) = (array[j], array[i])
}
}
func issorted<T:Comparable>(ary:
}
}
return true
}
func bogosort<T:Comparable>(inout ary:
}</
=={{header|Tcl}}==
<
proc shuffleInPlace {listName} {
Line 1,896 ⟶ 3,400:
}
return $list
}</
=={{header|TI-83 BASIC}}==
Line 1,947 ⟶ 3,451:
=={{header|Ursala}}==
<
#import nat
Line 1,956 ⟶ 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=====
<
dim tmp
tmp = a
Line 1,991 ⟶ 3,539:
next
inOrder = res
end function</
=====Invocation=====
<
a = array(11, 1, 2, 3, 4, 4, 6, 7, 8)
Line 2,003 ⟶ 3,551:
wend
wscript.echo timer-t, "seconds"
wscript.echo join( a, ", " )</
=====A few outputs (timed)=====
Line 2,015 ⟶ 3,563:
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}}==
<
proc BogoSort(A, L); \Sort array A of length L
Line 2,037 ⟶ 3,649:
BogoSort(A, 10);
for I:= 0 to 10-1 do [IntOut(0, A(I)); ChOut(0, ^ )];
]</
{{out}}
Line 2,044 ⟶ 3,656:
</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}}
|