Sorting algorithms/Bogosort: Difference between revisions

 

 

Pseudocode:

'''done'''

 

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

 

=={{header|ActionScript}}==

{

while (!sorted(arr))

 

return true;

 

=={{header|Ada}}==

with Ada.Numerics.Discrete_Random;

 

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

end loop;

<pre>

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

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

 

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

<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|Common Lisp}}==

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

<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|Euphoria}}==

object temp

integer j

end function

 

 

<pre>{1,2,5,4,6,3}

{5,1,3,6,2,4}

 

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

 

import (

}

fmt.Println("sorted! ", temp)

<pre>

unsorted: [31 41 59 26 53 58 97 93 23 84]

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

 

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

 

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

 

=={{header|Haskell}}==

import Data.Array.IO

import Control.Monad

 

-- from http://www.haskell.org/haskellwiki/Random_shuffle

shuffle :: [a] -> IO [a]

newArray :: Int -> [a] -> IO (IOArray Int a)

newArray n xs = newListArray (1,n) xs

 

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

 

}

 

<pre>Unsorted: 4 5 6 0 7 8 9 1 2 3

This took 23104714 shuffles.

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

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

 

 

return list

 

=={{header|M4}}==

define(`randSeed',141592653)

define(`setRand',

show(`b')

bogosort(`b')

 

 

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

 

 

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

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

 

<pre>1: 5 4 3 2 1

2: 3 5 4 1 2

 

=={{header|Perl}}==

 

sub bogosort

{$_ >= $last or return 0;

$last = $_;}

 

 

=={{header|PHP}}==

while (!in_order($l))

shuffle($l);

return FALSE;

return TRUE;

 

=={{header|PicoLisp}}==

(loop

(map

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

Lst )

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

-> (1 167 183 282 524 556 638 891 902)

: (bogosort (make (do 9 (link (rand 1 999)))))

-> (1 21 72 263 391 476 794 840 878)</pre>

 

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

 

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

 

=={{header|Qi}}==

(define remove-element

0 [_ | R] -> R

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

Suggestion -> (bogosort (shuffle Suggestion)))

 

=={{header|R}}==

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

 

<pre>

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

</pre>

 

 

 

do bogo=1

 

 

 

 

exit /*stick a fork in it, we're done.*/

/*──────────────────────────────────TELL subroutine─────────────────────*/

 

say

 

 

</pre>

More tests showed that:

number of bogo sorts performed = 2583

number of bogo sorts performed = 2376

number of bogo sorts performed = 4071

</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|Scala}}==

{{works with|Scala|2.8}}

 

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

 

<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|Tcl}}==

 

proc shuffleInPlace {listName} {

}

return $list

 

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

=={{header|Ursala}}==

 

#import nat

 

#cast %nL

 

<pre><0,8,12,47,50,51></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}}

</pre>

 

 

{{omit from|GUISS}}