Sorting algorithms/Bogosort: Difference between revisions

{{task|Sorting Algorithms}}

{{Sorting Algorithm}}

 

The [[Knuth shuffle]] may be used to implement the shuffle part of this algorithm.

<br><br>

 

=={{header|ActionScript}}==

{

while (!sorted(arr))

 

return true;

 

=={{header|Ada}}==

with Ada.Numerics.Discrete_Random;

 

Put (Integer'Image (Sequence (I)));

end loop;

The solution is generic.

The procedure Bogosort can be instantiated

3 6 7 9

</pre>

=={{header|ALGOL 68}}==

{{trans|python}}

{{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: (

[6]TYPE sample := (61, 52, 63, 94, 46, 18);

{{out}}

+18 +46 +52 +61 +63 +94

=={{header|ARM Assembly}}==

{{works with|as|Raspberry Pi}}

 

/* ARM assembly Raspberry PI */

bx lr

 

 

 

 

=={{header|AutoHotkey}}==

MsgBox % Bogosort("319208")

MsgBox % Bogosort("fedcba")

}

Return Found

 

=={{header|AWK}}==

Sort standard input and output to the standard output

{

return int(n * rand())

print line[i]

}

 

=={{header|BBC BASIC}}==

test() = 4, 65, 2, 31, 0, 99, 2, 83, 782, 1

IF d(I%) < d(I%-1) THEN = FALSE

NEXT

{{out}}

<pre>

383150 shuffles required to sort 10 items.

</pre>

 

=={{header|Brat}}==

sorted = list.sort #Kinda cheating here

while { list != sorted } { list.shuffle! }

}

 

 

=={{header|C}}==

#include <stdlib.h>

#include <stdbool.h>

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;

 

 

}

 

=={{header|Clojure}}==

 

(or (empty? xs)

(apply order xs)))

(recur order (shuffle xs))))

 

=={{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.

add 1 to array-index giving adjusted-index.

if item(array-index) is greater than item(adjusted-index)

{{out}}

<pre>BEFORE SORT: 141 503 930 105 78 518 180 907 791 361

<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))

(defun bogosort (list predicate)

(do ((list list (nshuffle list)))

 

=={{header|D}}==

 

void bogoSort(T)(T[] data) {

bogoSort(array);

writeln(array);

{{out}}

<pre>[1, 2, 3, 5, 6, 7, 8, 11, 41]</pre>

 

=={{header|E}}==

Using the shuffle from [[Knuth shuffle#E]].

 

if (list.size() == 0) { return true }

var a := list[0]

shuffle(list, random)

}

 

=={{header|Eiffel}}==

class

BOGO_SORT

 

end

TEST:

class

APPLICATION

 

end

{{out}}

<pre>

Sorted: 1 2 3 5 7

</pre>

=={{header|Elena}}==

import system'routines;

public program()

{

console.printLine("before:", list.asEnumerable());

console.printLine("after :", list.bogoSorter().asEnumerable())

{{out}}

<pre>

 

=={{header|Elixir}}==

def bogo_sort(list) do

if sorted?(list) do

defp sorted?([x, y | _]) when x>y, do: false

defp sorted?([_, y | rest]), do: sorted?([y | rest])

 

Example:

 

=={{header|Euphoria}}==

object temp

integer j

end function

 

 

{{out}}

 

=={{header|Factor}}==

 

: sorted? ( seq -- ? ) 2 <clumps> [ first2 <= ] all? ;

 

=={{header|Fantom}}==

 

class Main

{

}

}

 

=={{header|Fortran}}==

{{works with|Fortran|90 and later}}

IMPLICIT NONE

CONTAINS

WRITE (*,*) "Array required", iter, " shuffles to sort"

 

=={{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

Print "Solved in " & Str(iCounter) & " loops" 'Print the result

 

Output: (This example was completed in under 2 seconds)

<pre>

 

=={{header|Go}}==

 

import (

}

fmt.Println("sorted! ", temp)

{{out}} (sometimes takes a few seconds)

<pre>

=={{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] }) {

}

list

 

Test Program:

 

{{out}} trial 1:

 

=={{header|Haskell}}==

import Data.Array.IO

import Control.Monad

 

bogosort :: Ord a => [a] -> IO [a]

Example:

<pre>

 

=={{header|Icon}} and {{header|Unicon}}==

repeat {

!l :=: ?l

l := [6,3,4,5,1]

|( shuffle(l) & sorted(l)) \1 & every writes(" ",!l)

 

=={{header|Inform 6}}==

for(i = n - 1: i > 0: i--)

{

shuffle(a, n);

}

 

=={{header|Io}}==

isSorted := method(

slice(1) foreach(i, x,

 

lst := list(2, 1, 4, 3)

=={{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

 

}

 

{{out}}

{{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;

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;

}

return v;

 

=={{header|Julia}}==

{{works with|Julia|0.6}}

 

while !issorted(arr)

shuffle!(arr)

 

v = rand(-10:10, 10)

 

{{out}}

=={{header|Kotlin}}==

{{trans|C}}

 

const val RAND_MAX = 32768 // big enough for this

bogosort(a)

println("After sorting : ${a.contentToString()}")

 

{{out}}

 

=={{header|Lua}}==

if type (list) ~= 'table' then return list end

 

 

return list

 

=={{header|M4}}==

define(`randSeed',141592653)

define(`setRand',

show(`b')

bogosort(`b')

 

=={{header|Maple}}==

len := numelems(arr):

#Translation of C, random swapping

shuffle_arr(arr, len):

end do:

{{Out|Output}}

<pre>[1 2 3]</pre>

 

Bogosort[{1, 2, 6, 4, 0, -1, Pi, 3, 5}]

 

=={{header|MATLAB}} / {{header|Octave}}==

 

while( ~issorted(list) ) %Check to see if it is sorted

list = list( randperm(numel(list)) ); %Randomly sort the list

end

 

{{out}}

 

ans =

 

1 2 3 4 5 6 7 8 9

 

=={{header|MAXScript}}==

(

if arr.count > 0 then

)

arr

 

=={{header|Modula-3}}==

 

 

IMPORT IO, Fmt, Random;

END;

IO.Put("\nRequired " & Fmt.Int(count) & " shuffles\n");

 

=={{header|Nemerle}}==

using System.Console;

using Nemerle.Imperative;

foreach (i in sortme) Write($"$i ");

}

 

=={{header|NetRexx}}==

{{trans|Java}}

options replace format comments java crossref savelog symbols nobinary

 

method isFalse public static returns boolean

return \isTrue

{{out}}

<pre>

 

=={{header|Nim}}==

 

 

proc isSorted[T](s: openarray[T]): bool =

var a = @[4, 65, 2, -31, 0, 99, 2, 83, 782]

bogoSort a

{{out}}

<pre>@[-31, 0, 2, 2, 4, 65, 83, 99, 782]</pre>

=={{header|Oberon-2}}==

{{Works with|Oxford Oberon-2 Compiler}}

 

IMPORT Out, Random;

END;

Out.Ln;

 

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

li

else

Example:

<pre>

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

in

{BogoSort X}

 

=={{header|PARI/GP}}==

This implementation sorts 9 distinct elements in only 600 milliseconds.

while(1,

my(u=vecextract(v,numtoperm(#v,random((#v)!))));

return(u)

);

 

=={{header|Pascal}}==

 

 

const

a[i] := (max + 1) - i;

bogo(a);

 

{{out}}

 

=={{header|Perl}}==

 

sub bogosort

{$_ >= $last or return 0;

$last = $_;}

 

=={{header|Phix}}==

{{out}}

<pre>

 

=={{header|PHP}}==

while (!in_order($l))

shuffle($l);

return FALSE;

return TRUE;

 

=={{header|PicoLisp}}==

(loop

(map

'((L) (rot L (rand 1 (length L))))

Lst )

{{out}}

<pre>: (bogosort (make (do 9 (link (rand 1 999)))))

=={{header|PL/I}}==

{{trans|REXX}}

bogosort: Proc Options(main);

Dcl SYSPRINT Print;

Return(res);

End;

{{out}}

<pre>un-bogoed

=={{header|PowerShell}}==

Shuffle taken from [[Knuth Shuffle]]

$c = $a.Clone() # make copy to avoid clobbering $a

1..($c.Length - 1) | ForEach-Object {

}

 

 

=={{header|PureBasic}}==

Protected i, Size = ArraySize(a())

For i = 0 To Size

Next

 

{{out}}

<pre>Array of 10 integers required 2766901 shuffles To SORT.</pre>

 

=={{header|Python}}==

 

def bogosort(l):

return False

last = x

 

Alternative definition for ''in_order'' (Python 2.5)

 

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)

 

Another alternative implementation, using iterators for maximum efficiency:

 

import random

from itertools import dropwhile, imap, islice, izip, repeat, starmap

bogosort = lambda l: next(dropwhile(

lambda l: not all(starmap(operator.le, izip(l, islice(l, 1, None)))),

 

=={{header|Qi}}==

(define remove-element

0 [_ | R] -> R

Suggestion -> Suggestion where (in-order? Suggestion)

Suggestion -> (bogosort (shuffle Suggestion)))

 

=={{header|R}}==

while(is.unsorted(x)) x <- sample(x)

x

 

n <- c(1, 10, 9, 7, 3, 0)

 

=={{header|Racket}}==

is unit tests and an example.

 

#lang racket

(define (bogo-sort l) (if (apply <= l) l (bogo-sort (shuffle l))))

(displayln unsorted)

(displayln (bogo-sort unsorted)))

 

{{out}} (chances are you won't get quite this!):

(12 26 86 232 700 703 713 778 894 931)

</pre>

 

=={{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.*/

end /*t*/

say

{{out}} using the default input:

<pre>

<br>has already been sorted and including the number out-of-order. &nbsp; 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

end /*t*/

say

{{out}}

<pre style="height:30ex">

 

=={{header|Ring}}==

# Project : Sorting algorithms/Bogosort

 

see svect

see "]" + nl

Output:

<pre>

[0, 1, 2, 2, 4, 31, 65, 83, 99, 782]

</pre>

 

=={{header|Ruby}}==

l.sort_by { rand }

end

def in_order(l)

(0..l.length-2).all? {|i| l[i] <= l[i+1] }

 

An alternative implementation:

 

l.sort_by { rand }

end

l = shuffle(l) until l == l.sort

l

 

{{works with|Ruby|1.8.7+}}

 

(0..l.length-2).all? {|i| l[i] <= l[i+1] }

end

l.shuffle! until in_order(l)

l

 

=={{header|Rust}}==

Works with Rust 1.11+, requires rand module

{{libheader|rand}}

use rand::Rng;

 

println!("{:?}", testlist);

}

 

=={{header|Scala}}==

{{works with|Scala|2.8}}

 

=={{header|Sidef}}==

}

 

func bogosort(a) {

}

 

{{out}}

<pre>

After: 33 45 57 83 85

</pre>

 

=={{header|Smalltalk}}==

 

This implementation uses closures rather than extending collections to provide a bogosort method.

|isit|

isit := false.

tobesorted := { 2 . 7 . 5 . 3 . 4 . 8 . 6 . 1 }.

bogosort value: tobesorted.

 

=={{header|SNOBOL4}}==

 

-include 'Random.sno'

 

* # Test and display

bogo(s2a('5 4 3 2 1',5))

 

{{out}}

 

=={{header|Swift}}==

 

func shuffle<T>(inout array: [T]) {

shuffle(&ary)

}

 

=={{header|Tcl}}==

 

proc shuffleInPlace {listName} {

}

return $list

 

=={{header|TI-83 BASIC}}==

=={{header|Ursala}}==

 

#import nat

 

#cast %nL

 

{{out}}

<pre><0,8,12,47,50,51></pre>

 

=={{header|VBA}}==

Dim t As Variant, i As Integer

If Not IsMissing(a) Then

Public Sub main()

Debug.Print Join(bogosort(Knuth([{1,2,3,4,5,6}])), ", ")

<pre>...

1, 3, 2, 5, 6, 4

2, 6, 3, 4, 1, 5

1, 2, 3, 4, 5, 6</pre>

=={{header|VBScript}}==

=====Implementation=====

dim tmp

tmp = a

next

inOrder = res

 

=====Invocation=====

a = array(11, 1, 2, 3, 4, 4, 6, 7, 8)

 

wend

wscript.echo timer-t, "seconds"

 

=====A few outputs (timed)=====

1.980469 seconds

1, 2, 3, 4, 4, 6, 7, 8, 11

</pre>

 

=={{header|XPL0}}==

 

proc BogoSort(A, L); \Sort array A of length L

BogoSort(A, 10);

for I:= 0 to 10-1 do [IntOut(0, A(I)); ChOut(0, ^ )];

 

{{out}}

-5 1 1 2 3 4 4 5 6 9

</pre>

 

=={{header|zkl}}==

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() }

{{out}}

<pre>L(1,5,6,7,23,23,123)</pre>