Sorting algorithms/Bogosort: Difference between revisions
m
syntax highlighting fixup automation
Thundergnat (talk | contribs) m (→{{header|Eiffel}}: fix irregular markup) |
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
||
Line 25:
<br><br>
=={{header|11l}}==
<
R all((0 .< data.len - 1).map(i -> @data[i] <= @data[i + 1]))
Line 34:
V arr = [2, 1, 3]
bogosort(&arr)
print(arr)</
{{out}}
Line 43:
=={{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 */
Line 217:
/* for this file see task include a file in language AArch64 assembly */
.include "../includeARM64.inc"
</syntaxhighlight>
=={{header|Action!}}==
<
INT i
Line 289:
Test(c,8)
Test(d,12)
RETURN</
{{out}}
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Bogosort.png Screenshot from Atari 8-bit computer]
Line 315:
=={{header|ActionScript}}==
<
{
while (!sorted(arr))
Line 351:
return true;
}</
=={{header|Ada}}==
<
with Ada.Numerics.Discrete_Random;
Line 403:
Put (Integer'Image (Sequence (I)));
end loop;
end Test_Bogosort;</
The solution is generic.
The procedure Bogosort can be instantiated
Line 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 458:
[6]TYPE sample := (61, 52, 63, 94, 46, 18);
print((bogo sort(sample), new line))</
{{out}}
+18 +46 +52 +61 +63 +94
Line 464:
=={{header|ARM Assembly}}==
{{works with|as|Raspberry Pi}}
<syntaxhighlight lang="arm assembly">
/* ARM assembly Raspberry PI */
Line 714:
bx lr
</syntaxhighlight>
=={{header|Arturo}}==
<
a: new items
while [not? sorted? a]-> shuffle 'a
Line 724:
]
print bogoSort [3 1 2 8 5 7 9 4 6]</
{{out}}
Line 731:
=={{header|AutoHotkey}}==
<
MsgBox % Bogosort("319208")
MsgBox % Bogosort("fedcba")
Line 764:
}
Return Found
}</
=={{header|AWK}}==
Sort standard input and output to the standard output
<
{
return int(n * rand())
Line 797:
print line[i]
}
}</
=={{header|BBC BASIC}}==
<
test() = 4, 65, 2, 31, 0, 99, 2, 83, 782, 1
Line 823:
IF d(I%) < d(I%-1) THEN = FALSE
NEXT
= TRUE</
{{out}}
<pre>
Line 830:
=={{header|Brat}}==
<
sorted = list.sort #Kinda cheating here
while { list != sorted } { list.shuffle! }
Line 836:
}
p bogosort [15 6 2 9 1 3 41 19]</
=={{header|C}}==
<
#include <stdlib.h>
#include <stdbool.h>
Line 875:
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 926:
}
}</
=={{header|C++}}==
Uses C++11. Compile with
g++ -std=c++11 bogo.cpp
<
#include <iostream>
#include <iterator>
Line 959:
copy(std::begin(a), std::end(a), std::ostream_iterator<int>(std::cout, " "));
std::cout << "\n";
}</
{{out}}
<pre>
Line 967:
=={{header|Clojure}}==
<
(or (empty? xs)
(apply order xs)))
Line 975:
(recur order (shuffle xs))))
(println (bogosort < [7 5 12 1 4 2 23 18]))</
=={{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.
<
program-id. bogo-sort-program.
data division.
Line 1,043:
add 1 to array-index giving adjusted-index.
if item(array-index) is greater than item(adjusted-index)
then move zero to sorted.</
{{out}}
<pre>BEFORE SORT: 141 503 930 105 78 518 180 907 791 361
Line 1,055:
<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 1,066:
(defun bogosort (list predicate)
(do ((list list (nshuffle list)))
((sortedp list predicate) list)))</
=={{header|Crystal}}==
<
i = items.size-1
while i > 1
Line 1,094:
knuthShuffle(items)
end
end</
=={{header|D}}==
<
void bogoSort(T)(T[] data) {
Line 1,108:
bogoSort(array);
writeln(array);
}</
{{out}}
<pre>[1, 2, 3, 5, 6, 7, 8, 11, 41]</pre>
Line 1,118:
Using the shuffle from [[Knuth shuffle#E]].
<
if (list.size() == 0) { return true }
var a := list[0]
Line 1,133:
shuffle(list, random)
}
}</
=={{header|Eiffel}}==
<syntaxhighlight lang="eiffel">
class
BOGO_SORT
Line 1,203:
end
</syntaxhighlight>
TEST:
<syntaxhighlight lang="eiffel">
class
APPLICATION
Line 1,238:
end
</syntaxhighlight>
{{out}}
<pre>
Line 1,247:
=={{header|Elena}}==
ELENA 5.0 :
<
import system'routines;
Line 1,271:
console.printLine("before:", list.asEnumerable());
console.printLine("after :", list.bogoSorter().asEnumerable())
}</
{{out}}
<pre>
Line 1,279:
=={{header|Elixir}}==
<
def bogo_sort(list) do
if sorted?(list) do
Line 1,291:
defp sorted?([x, y | _]) when x>y, do: false
defp sorted?([_, y | rest]), do: sorted?([y | rest])
end</
Example:
Line 1,300:
=={{header|Euphoria}}==
<
object temp
integer j
Line 1,331:
end function
? bogosort(shuffle({1,2,3,4,5,6}))</
{{out}}
Line 1,344:
=={{header|Factor}}==
<
: sorted? ( seq -- ? ) 2 <clumps> [ first2 <= ] all? ;
: bogosort ( seq -- newseq ) [ dup sorted? ] [ randomize ] until ;</
=={{header|Fantom}}==
<
class Main
{
Line 1,377:
}
}
</syntaxhighlight>
=={{header|Fortran}}==
{{works with|Fortran|90 and later}}
<
IMPLICIT NONE
CONTAINS
Line 1,429:
WRITE (*,*) "Array required", iter, " shuffles to sort"
END PROGRAM BOGOSORT</
=={{header|FreeBASIC}}==
<
dim as ulong n = ubound(a), i, j, k, m = ubound(a)*2
dim as ulong tmp
Line 1,469:
for i=0 to ubound(a) - 1
print a(i)
next i</
=={{header|Gambas}}==
'''[https://gambas-playground.proko.eu/?gist=b2b766f379d809cbf054c2d32d76c453 Click this link to run this code]'''
<
Dim sSorted As String = "123456789" 'The desired outcome
Dim sTest, sChr As String 'Various strings
Line 1,491:
Print "Solved in " & Str(iCounter) & " loops" 'Print the result
End</
Output: (This example was completed in under 2 seconds)
<pre>
Line 1,504:
=={{header|Go}}==
<
import (
Line 1,525:
}
fmt.Println("sorted! ", temp)
}</
{{out}} (sometimes takes a few seconds)
<pre>
Line 1,534:
=={{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 1,541:
}
list
}</
Test Program:
<
{{out}} trial 1:
Line 1,553:
=={{header|Haskell}}==
<
import Data.Array.IO
import Control.Monad
Line 1,582:
bogosort :: Ord a => [a] -> IO [a]
bogosort = bogosortBy (<)</
Example:
<pre>
Line 1,590:
=={{header|Icon}} and {{header|Unicon}}==
<
repeat {
!l :=: ?l
Line 1,606:
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 1,634:
shuffle(a, n);
}
];</
=={{header|Io}}==
<
isSorted := method(
slice(1) foreach(i, x,
Line 1,653:
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 1,719:
}
</syntaxhighlight>
{{out}}
Line 1,729:
{{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 1,752:
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 1,774:
}
return v;
}</
=={{header|Julia}}==
{{works with|Julia|0.6}}
<
while !issorted(arr)
shuffle!(arr)
Line 1,787:
v = rand(-10:10, 10)
println("# unordered: $v\n -> ordered: ", bogosort!(v))</
{{out}}
Line 1,795:
=={{header|Kotlin}}==
{{trans|C}}
<
const val RAND_MAX = 32768 // big enough for this
Line 1,830:
bogosort(a)
println("After sorting : ${a.contentToString()}")
}</
{{out}}
Line 1,839:
=={{header|Lua}}==
<
if type (list) ~= 'table' then return list end
Line 1,864:
return list
end</
=={{header|M4}}==
<
define(`randSeed',141592653)
define(`setRand',
Line 1,906:
show(`b')
bogosort(`b')
show(`b')</
=={{header|Maple}}==
<
len := numelems(arr):
#Translation of C, random swapping
Line 1,924:
shuffle_arr(arr, len):
end do:
arr;</
{{Out|Output}}
<pre>[1 2 3]</pre>
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<
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 1,985:
)
arr
)</
=={{header|Modula-3}}==
<
IMPORT IO, Fmt, Random;
Line 2,034:
END;
IO.Put("\nRequired " & Fmt.Int(count) & " shuffles\n");
END Bogo.</
=={{header|Nanoquery}}==
<
if len(list) = 0
return true
Line 2,057:
return list
end</
=={{header|Nemerle}}==
<
using System.Console;
using Nemerle.Imperative;
Line 2,098:
foreach (i in sortme) Write($"$i ");
}
}</
=={{header|NetRexx}}==
{{trans|Java}}
<
options replace format comments java crossref savelog symbols nobinary
Line 2,148:
method isFalse public static returns boolean
return \isTrue
</syntaxhighlight>
{{out}}
<pre>
Line 2,156:
=={{header|Nim}}==
<
randomize()
Line 2,173:
var a = @[4, 65, 2, -31, 0, 99, 2, 83, 782]
bogoSort a
echo a</
{{out}}
<pre>@[-31, 0, 2, 2, 4, 65, 83, 99, 782]</pre>
Line 2,179:
=={{header|Oberon-2}}==
{{Works with|Oxford Oberon-2 Compiler}}
<
IMPORT Out, Random;
Line 2,229:
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 2,253:
li
else
bogosort (shuffle li)</
Example:
<pre>
Line 2,263:
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 2,294:
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 2,304:
return(u)
);
};</
=={{header|Pascal}}==
<
const
Line 2,372:
a[i] := (max + 1) - i;
bogo(a);
end.</
{{out}}
Line 2,382:
=={{header|Perl}}==
<
sub bogosort
Line 2,394:
{$_ >= $last or return 0;
$last = $_;}
return 1;}</
=={{header|Phix}}==
<!--<
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
Line 2,413:
<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>
<!--</
{{out}}
<pre>
Line 2,424:
=={{header|PHP}}==
<
while (!in_order($l))
shuffle($l);
Line 2,435:
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)))))
Line 2,456:
=={{header|PL/I}}==
{{trans|REXX}}
<
bogosort: Proc Options(main);
Dcl SYSPRINT Print;
Line 2,509:
Return(res);
End;
End;</
{{out}}
<pre>un-bogoed
Line 2,527:
=={{header|PowerShell}}==
Shuffle taken from [[Knuth Shuffle]]
<
$c = $a.Clone() # make copy to avoid clobbering $a
1..($c.Length - 1) | ForEach-Object {
Line 2,555:
}
$l = 7; BogoSort ( 1..$l | ForEach-Object { $Rand = New-Object Random }{ $Rand.Next( 0, $l - 1 ) } )</
=={{header|Prolog}}==
<
min_list(L,Min),
repeat,
Line 2,568:
is_sorted([N|T],P) :-
N >= P,
is_sorted(T,N).</
{{out}}
<pre>
Line 2,576:
=={{header|PureBasic}}==
<
Protected i, Size = ArraySize(a())
For i = 0 To Size
Line 2,608:
Next
BogoSort(b())</
{{out}}
<pre>Array of 10 integers required 2766901 shuffles To SORT.</pre>
=={{header|Python}}==
<
def bogosort(l):
Line 2,628:
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:
<
import random
from itertools import dropwhile, imap, islice, izip, repeat, starmap
Line 2,655:
bogosort = lambda l: next(dropwhile(
lambda l: not all(starmap(operator.le, izip(l, islice(l, 1, None)))),
imap(shuffled, repeat(l))))</
=={{header|Qi}}==
<syntaxhighlight lang="qi">
(define remove-element
0 [_ | R] -> R
Line 2,682:
Suggestion -> Suggestion where (in-order? Suggestion)
Suggestion -> (bogosort (shuffle Suggestion)))
</syntaxhighlight>
=={{header|Quackery}}==
<
dup [] != if
[ behead swap witheach
Line 2,693:
drop ] is inorder ( [ --> b )
[ dup inorder not while shuffle again ] is bogosort ( [ --> [ )</
=={{header|R}}==
<
while(is.unsorted(x)) x <- sample(x)
x
Line 2,702:
n <- c(1, 10, 9, 7, 3, 0)
bogosort(n)</
=={{header|Racket}}==
Line 2,709:
is unit tests and an example.
<
#lang racket
(define (bogo-sort l) (if (apply <= l) l (bogo-sort (shuffle l))))
Line 2,720:
(displayln unsorted)
(displayln (bogo-sort unsorted)))
</syntaxhighlight>
{{out}} (chances are you won't get quite this!):
Line 2,730:
=={{header|Raku}}==
(formerly Perl 6)
<syntaxhighlight lang="raku"
@list .= pick(*) until [<=] @list;
return @list;
Line 2,737:
my @nums = (^5).map: { rand };
say @nums.sort.Str eq @nums.&bogosort.Str ?? 'ok' !! 'not ok';
</syntaxhighlight>
=={{header|REXX}}==
===true bogo sort===
<
parse arg list /*obtain optional list from C.L. */
if list='' then list=-21 333 0 444.4 /*Not defined? Then use default.*/
Line 2,771:
end /*t*/
say
return</
{{out}} using the default input:
<pre>
Line 2,794:
<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.
<
@.1 = 0 ; @.11= -64 ; @.21= 4096 ; @.31= 6291456
@.2 = 0 ; @.12= 64 ; @.22= 40960 ; @.32= 5242880
Line 2,835:
end /*t*/
say
return</
{{out}}
<pre style="height:30ex">
Line 2,946:
=={{header|Ring}}==
<
# Project : Sorting algorithms/Bogosort
Line 2,987:
see svect
see "]" + nl
</syntaxhighlight>
Output:
<pre>
Line 2,995:
=={{header|Ruby}}==
<
l.sort_by { rand }
end
Line 3,006:
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 3,017:
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 3,028:
l.shuffle! until in_order(l)
l
end</
=={{header|Rust}}==
Works with Rust 1.11+, requires rand module
{{libheader|rand}}
<
use rand::Rng;
Line 3,060:
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}}==
<
return true if (a.len <= 1);
var first = a[0];
Line 3,081:
var arr = 5.of{ 100.rand.int };
say "Before: #{arr}";
say "After: #{bogosort(arr)}";</
{{out}}
<pre>
Line 3,090:
=={{header|Scheme}}==
Uses [[Knuth shuffle]] to shuffle the list.
<
(srfi :27 random-bits))
Line 3,123:
(display "Output: ")
(display (bogosort input))
(newline))</
{{out}}
<pre>Input: (5 4 3 2 1)
Line 3,132:
This implementation uses closures rather than extending collections to provide a bogosort method.
<
|isit|
isit := false.
Line 3,155:
tobesorted := { 2 . 7 . 5 . 3 . 4 . 8 . 6 . 1 }.
bogosort value: tobesorted.
tobesorted displayNl.</
=={{header|SNOBOL4}}==
<
-include 'Random.sno'
Line 3,199:
* # Test and display
bogo(s2a('5 4 3 2 1',5))
end</
{{out}}
Line 3,209:
=={{header|Swift}}==
<
func shuffle<T>(inout array: [T]) {
Line 3,231:
shuffle(&ary)
}
}</
=={{header|Tcl}}==
<
proc shuffleInPlace {listName} {
Line 3,263:
}
return $list
}</
=={{header|TI-83 BASIC}}==
Line 3,314:
=={{header|Ursala}}==
<
#import nat
Line 3,323:
#cast %nL
example = bogosort <8,50,0,12,47,51></
{{out}}
<pre><0,8,12,47,50,51></pre>
=={{header|VBA}}==
{{trans|Phix}}<
Dim t As Variant, i As Integer
If Not IsMissing(a) Then
Line 3,363:
Public Sub main()
Debug.Print Join(bogosort(Knuth([{1,2,3,4,5,6}])), ", ")
End Sub</
<pre>...
1, 3, 2, 5, 6, 4
Line 3,373:
=={{header|VBScript}}==
=====Implementation=====
<
dim tmp
tmp = a
Line 3,402:
next
inOrder = res
end function</
=====Invocation=====
<
a = array(11, 1, 2, 3, 4, 4, 6, 7, 8)
Line 3,414:
wend
wscript.echo timer-t, "seconds"
wscript.echo join( a, ", " )</
=====A few outputs (timed)=====
Line 3,430:
=={{header|Vlang}}==
Updated for Vlang version 0.2.2
<
fn shuffle_array(mut arr []int) {
Line 3,460:
sort_array(mut array)
println('Output: $array')
}</
{{out}}
<pre>Input: [6, 9, 1, 4]
Line 3,473:
=={{header|Wren}}==
{{libheader|Wren-sort}}
<
import "/sort" for Sort
Line 3,484:
System.print("Before: %(a)")
bogoSort.call(a)
System.print("After : %(a)")</
{{out}}
Line 3,493:
=={{header|XPL0}}==
<
proc BogoSort(A, L); \Sort array A of length L
Line 3,512:
BogoSort(A, 10);
for I:= 0 to 10-1 do [IntOut(0, A(I)); ChOut(0, ^ )];
]</
{{out}}
Line 3,522:
=={{header|Yabasic}}==
{{trans|FreeBASIC}}
<
sub shuffle(a())
n = arraysize(a(),1)
Line 3,560:
next i
end
</syntaxhighlight>
=={{header|zkl}}==
<
list.len()<2 or
list.reduce(fcn(a,b){ if(b<a) return(Void.Stop,False); b }).toBool()
Line 3,571:
ns:=L(5,23,1,6,123,7,23);
while(not increasing(ns)){ ns=ns.shuffle() }
ns.println();</
{{out}}
<pre>L(1,5,6,7,23,23,123)</pre>
|