Sorting algorithms/Bogosort
You are encouraged to solve this task according to the task description, using any language you may know.
Sorting Algorithm
This is a sorting algorithm. It may be applied to a set of data in order to sort it.
For comparing various sorts, see compare sorts.
For other sorting algorithms, see sorting algorithms, or:
Heap sort | Merge sort | Patience sort | Quick sort
O(n log2n) sorts
Shell Sort
O(n2) sorts
Bubble sort |
Cocktail sort |
Cocktail sort with shifting bounds |
Comb sort |
Cycle sort |
Gnome sort |
Insertion sort |
Selection sort |
Strand sort
other sorts
Bead sort |
Bogo sort |
Common sorted list |
Composite structures sort |
Custom comparator sort |
Counting sort |
Disjoint sublist sort |
External sort |
Jort sort |
Lexicographical sort |
Natural sorting |
Order by pair comparisons |
Order disjoint list items |
Order two numerical lists |
Object identifier (OID) sort |
Pancake sort |
Quickselect |
Permutation sort |
Radix sort |
Ranking methods |
Remove duplicate elements |
Sleep sort |
Stooge sort |
[Sort letters of a string] |
Three variable sort |
Topological sort |
Tree sort
Bogosort a list of numbers. Bogosort simply shuffles a collection until it is sorted. (read the article on Wikipedia)
It is worth noting that "Bogosort" is a perversely inefficient algorithm and only used as an "in joke". Its typical run-time efficiency would be O(n!) ... the chances that any given shuffle of a set will end up in sorted order is about one in n factorial! Worst case is infinite! (We can never guarantee that a random shuffling will ever produce a sorted sequence).
Pseudocode:
while not InOrder(list) do Shuffle(list) done
See also
- Knuth shuffle (which may be used to implement the shuffle part of this algorithm)
ActionScript
<lang actionscript>public function bogoSort(arr:Array):Array {
while (!sorted(arr))
{
shuffle(arr);
}
return arr;
}
public function shuffle(arr:Array):void {
for (var i:int = 0; i < arr.length; i++)
{
var rand:int = Math.floor(Math.random() * arr.length);
var tmp:* = arr[i];
arr[i] = arr[rand];
arr[rand] = tmp;
}
}
public function sorted(arr:Array):Boolean {
var last:int = arr[0];
for (var i:int = 1; i < arr.length; i++)
{
if (arr[i] < last)
{
return false;
}
last = arr[i]; }
return true;
}</lang>
Ada
<lang ada>with Ada.Text_IO; use Ada.Text_IO; with Ada.Numerics.Discrete_Random;
procedure Test_Bogosort is
generic
type Ordered is private;
type List is array (Positive range <>) of Ordered;
with function "<" (L, R : Ordered) return Boolean is <>;
procedure Bogosort (Data : in out List);
procedure Bogosort (Data : in out List) is
function Sorted return Boolean is
begin
for I in Data'First..Data'Last - 1 loop
if not (Data (I) < Data (I + 1)) then
return False;
end if;
end loop;
return True;
end Sorted;
subtype Index is Integer range Data'Range;
package Dices is new Ada.Numerics.Discrete_Random (Index);
use Dices;
Dice : Generator;
procedure Shuffle is
J : Index;
Temp : Ordered;
begin
for I in Data'Range loop
J := Random (Dice);
Temp := Data (I);
Data (I) := Data (J);
Data (J) := Temp;
end loop;
end Shuffle;
begin
while not Sorted loop
Shuffle;
end loop;
end Bogosort;
type List is array (Positive range <>) of Integer; procedure Integer_Bogosort is new Bogosort (Integer, List); Sequence : List := (7,6,3,9);
begin
Integer_Bogosort (Sequence);
for I in Sequence'Range loop
Put (Integer'Image (Sequence (I)));
end loop;
end Test_Bogosort;</lang> 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. Sample output:
3 6 7 9
ALGOL 68
<lang algol68>MODE TYPE = INT;
PROC random shuffle = (REF[]TYPE l)VOID: (
INT range = UPB l - LWB l + 1;
FOR index FROM LWB l TO UPB l DO
TYPE tmp := l[index];
INT other := ENTIER (LWB l + random * range);
l[index] := l[other];
l[other] := tmp
OD
);
PROC in order = (REF[]TYPE l)BOOL: (
IF LWB l >= UPB l THEN
TRUE
ELSE
TYPE last := l[LWB l];
FOR index FROM LWB l + 1 TO UPB l DO
IF l[index] < last THEN
GO TO return false
FI;
last := l[index]
OD;
TRUE EXIT
return false: FALSE
FI
);
PROC bogo sort = (REF[]TYPE l)REF[]TYPE: (
WHILE NOT in order(l) DO
random shuffle(l)
OD;
l
);
[6]TYPE sample := (61, 52, 63, 94, 46, 18); print((bogo sort(sample), new line))</lang> Output:
+18 +46 +52 +61 +63 +94
AutoHotkey
<lang AutoHotkey>MsgBox % Bogosort("987654") MsgBox % Bogosort("319208") MsgBox % Bogosort("fedcba") MsgBox % Bogosort("gikhjl")
Bogosort(sequence) {
While !Sorted(sequence) sequence := Shuffle(sequence) Return sequence
}
Sorted(sequence) {
Loop, Parse, sequence
{
current := A_LoopField
rest := SubStr(sequence, A_Index)
Loop, Parse, rest
{
If (current > A_LoopField)
Return false
}
}
Return true
}
Shuffle(sequence) {
Max := StrLen(sequence) + 1
Loop % StrLen(sequence) {
Random, Num, 1, % Max - A_Index
Found .= SubStr(sequence, Num, 1)
sequence := SubStr(sequence, 1, Num-1) . SubStr(sequence, Num+1)
}
Return Found
}</lang>
AWK
Sort standard input and output to the standard output <lang awk>function randint(n) {
return int(n * rand())
}
function sorted(sa, sn) {
for(si=1; si < sn; si++) {
if ( sa[si] > sa[si+1] ) return 0;
}
return 1
}
{
line[NR] = $0
} END { # sort it with bogo sort
while ( sorted(line, NR) == 0 ) {
for(i=1; i <= NR; i++) {
r = randint(NR) + 1
t = line[i]
line[i] = line[r]
line[r] = t
}
}
#print it
for(i=1; i <= NR; i++) {
print line[i]
}
}</lang>
C
<lang c>#include <stdio.h>
- include <stdlib.h>
- include <stdbool.h>
bool is_sorted(int *a, int n) {
while ( --n >= 1 ) {
if ( a[n] < a[n-1] ) return false;
}
return true;
}
void shuffle(int *a, int n) {
int i, t, r;
for(i=0; i < n; i++) {
t = a[i];
r = rand() % n;
a[i] = a[r];
a[r] = t;
}
}
void bogosort(int *a, int n) {
while ( !is_sorted(a, n) ) shuffle(a, n);
}
int main() {
int numbers[] = { 1, 10, 9, 7, 3, 0 };
int i;
bogosort(numbers, 6);
for (i=0; i < 6; i++) printf("%d ", numbers[i]);
printf("\n");
}</lang>
C++
The following algorithm actually works for all sequences of comparable types; restricting to lists of integers would not make the code simpler. <lang cpp>#include <iterator>
- include <algorithm>
template<typename ForwardIterator>
void bogosort(ForwardIterator begin, ForwardIterator end)
{
typedef std::iterator_traits<ForwardIterator>::value_type value_type;
// if we find two adjacent values where the first is greater than the second, the sequence isn't sorted. while (std::adjacent_find(begin, end, std::greater<value_type>()) != end) std::random_shuffle(begin, end);
}</lang> Using the is_sorted function, part of the SGI STL implementation:
<lang cpp>#include <algorithm>
- include <ext/algorithm>
template<typename ForwardIterator>
void bogosort(ForwardIterator begin, ForwardIterator end)
{
while (!__gnu_cxx::is_sorted(begin, end)) std::random_shuffle(begin, end);
}</lang>
C#
<lang csharp>using System; using System.Collections.Generic;
namespace RosettaCode.BogoSort {
public static class BogoSorter
{
public static void Sort<T>(List<T> list) where T:IComparable
{
while (!list.isSorted())
{
list.Shuffle();
}
}
private static bool isSorted<T>(this IList<T> list) where T:IComparable
{
if(list.Count<=1)
return true;
for (int i = 1 ; i < list.Count; i++)
if(list[i].CompareTo(list[i-1])<0) return false;
return true;
}
private static void Shuffle<T>(this IList<T> list)
{
Random rand = new Random();
for (int i = 0; i < list.Count; i++)
{
int swapIndex = rand.Next(list.Count);
T temp = list[swapIndex];
list[swapIndex] = list[i];
list[i] = temp;
}
}
}
class TestProgram
{
static void Main()
{
List<int> testList = new List<int> { 3, 4, 1, 8, 7, 4, -2 };
BogoSorter.Sort(testList);
foreach (int i in testList) Console.Write(i + " ");
}
}
}</lang>
Clojure
We use seq-utils' shuffle, which initializes a Java ArrayList with the input sequence, shuffle it, and then return a sequence of the result.
<lang lisp>(use 'clojure.contrib.seq-utils)
(defn in-order? [cmp xs]
(or (empty? xs)
(empty? (next xs))
(and (cmp (first xs) (second xs))
(recur cmp (next xs)))))
(defn bogosort [cmp xs]
(if (in-order? cmp xs) xs
(recur cmp (shuffle xs))))</lang>
Common Lisp
Sortedp checks that each element of a list is related by predicate to the next element of the list. I.e., (sortedp (x1 x2 … xn) pred) is true when each of (pred x1 x2), …, (pred xn-1 xn) is true.
nshuffle is the same code as in Knuth shuffle.
<lang lisp>(defun nshuffle (sequence)
(loop for i from (length sequence) downto 2
do (rotatef (elt sequence (random i))
(elt sequence (1- i ))))
sequence)
(defun sortedp (list predicate)
(every predicate list (rest list)))
(defun bogosort (list predicate)
(do ((list list (nshuffle list)))
((sortedp list predicate) list)))</lang>
D
<lang d>module bogosort ; import std.stdio, std.random ;
bool isSorted(T)(inout T[] a) { // test if a is already sorted
if(a.length <= 1) return true ; // 1-elemented/empty array is defined as sorted for(int i = 1 ; i < a.length ; i++) if(a[i] < a[i-1]) return false ; return true ;
}
T[] bogosort(T)(T[] s) {
while(!isSorted(s)) {
for(int n = s.length ; n > 1 ; n--) {
int i = rand() % n ; // random shuffling
T tmp = s[i] ; s[i] = s[n - 1] ; s[n - 1] = tmp ;
}
}
return s ;
}
void main() {
auto b = [2,7,4,3] ;
writefln("%s", bogosort(b)) ;
writefln("%s", b) ; // sort is in place
}</lang>
E
Using the shuffle from Knuth shuffle#E.
<lang e>def isSorted(list) {
if (list.size() == 0) { return true }
var a := list[0]
for i in 1..!(list.size()) {
var b := list[i]
if (a > b) { return false }
a := b
}
return true
}
def bogosort(list, random) {
while (!isSorted(list)) {
shuffle(list, random)
}
}</lang>
Factor
<lang factor>USING: grouping kernel math random sequences ;
- sorted? ( seq -- ? ) 2 <clumps> [ first2 <= ] all? ;
- bogosort ( seq -- newseq ) [ dup sorted? ] [ randomize ] until ;</lang>
Fortran
<lang fortran>MODULE BOGO IMPLICIT NONE CONTAINS
FUNCTION Sorted(a) LOGICAL :: Sorted INTEGER, INTENT(IN) :: a(:) INTEGER :: i
Sorted = .TRUE.
DO i = 1, SIZE(a)-1
IF(a(i) > a(i+1)) THEN
Sorted = .FALSE.
EXIT
END IF
END DO
END FUNCTION Sorted
SUBROUTINE SHUFFLE(a) INTEGER, INTENT(IN OUT) :: a(:) INTEGER :: i, rand, temp REAL :: x
DO i = SIZE(a), 1, -1
CALL RANDOM_NUMBER(x)
rand = INT(x * i) + 1
temp = a(rand)
a(rand) = a(i)
a(i) = temp
END DO
END SUBROUTINE
END MODULE
PROGRAM BOGOSORT
USE BOGO IMPLICIT NONE INTEGER :: iter = 0 INTEGER :: array(8) = (/2, 7, 5, 3, 4, 8, 6, 1/) LOGICAL :: s DO s = Sorted(array) IF (s) EXIT CALL SHUFFLE(array) iter = iter + 1 END DO WRITE (*,*) "Array required", iter, " shuffles to sort"
END PROGRAM BOGOSORT</lang>
Groovy
Solution (also implicitly tracks the number of shuffles required): <lang groovy>def bogosort = { list ->
def n = list.size()
if (n > 1) {
while ((1..<n).any{ list[it-1] > list[it] }) {
Collections.shuffle(list)
print '.'
}
}
list
}</lang>
Test Program: <lang groovy>println bogosort([3,1,2])</lang>
Output, trial 1:
....[1, 2, 3]
Output, trial 2:
..........................[1, 2, 3]
Haskell
<lang haskell>import System.Random import Data.Array.IO import Control.Monad
isSorted :: (Ord a) => [a] -> Bool isSorted (e1:e2:r) = e1 <= e2 && isSorted (e2:r) isSorted _ = True
-- from http://www.haskell.org/haskellwiki/Random_shuffle shuffle :: [a] -> IO [a] shuffle xs = do
ar <- newArray n xs
forM [1..n] $ \i -> do
j <- randomRIO (i,n)
vi <- readArray ar i
vj <- readArray ar j
writeArray ar j vi
return vj
where
n = length xs
newArray :: Int -> [a] -> IO (IOArray Int a)
newArray n xs = newListArray (1,n) xs
bogosort :: (Ord a) => [a] -> IO [a] bogosort li | isSorted li = return li
| otherwise = shuffle li >>= bogosort</lang>
Example:
*Main> bogosort [7,5,12,1,4,2,23,18] [1,2,4,5,7,12,18,23]
Icon
<lang icon>procedure shuffle(l)
repeat {
!l :=: ?l
suspend l
}
end
procedure sorted(l)
local i if (i := 2 to *l & l[i] >= l[i-1]) then return &fail else return 1
end
procedure main()
local l
l := [6,3,4,5,1]
|( shuffle(l) & sorted(l)) \1 & every writes(" ",!l)
end</lang>
J
<lang j>bogo=: monad define
whilst. -. *./ 2 </\ Ry do. Ry=. (A.~ ?@!@#) y end. Ry
)</lang>
Java
This implementation works for all comparable types (types with compareTo defined). <lang java5>import java.util.Collections; import java.util.List; import java.util.Iterator;
public class Bogosort {
private static <T extends Comparable<? super T>> boolean isSorted(List<T> list) {
if (list.isEmpty())
return true;
Iterator<T> it = list.iterator();
T last = it.next();
while (it.hasNext()) {
T current = it.next();
if (last.compareTo(current) > 0)
return false;
last = current;
}
return true;
}
public static <T extends Comparable<? super T>> void bogoSort(List<T> list) {
while (!isSorted(list))
Collections.shuffle(list);
}
}</lang>
JavaScript
<lang javascript>shuffle = function(v) {
for(var j, x, i = v.length; i; j = parseInt(Math.random() * i), x = v[--i], v[i] = v[j], v[j] = x); return v;
};
isSorted = function(v){
for(var i=1; i<v.length; i++) {
if (v[i-1] > v[i]) { return false; }
}
return true;
}
bogosort = function(v){
var sorted = false;
while(sorted == false){
v = shuffle(v);
sorted = isSorted(v);
}
return v;
}</lang>
Lua
<lang lua>function bogosort (list)
if type (list) ~= 'table' then return list end
-- Fisher-Yates Knuth shuffle
local function shuffle ()
local rand = math.random(1,#list)
for i=1,#list do
list[i],list[rand] = list[rand],list[i]
rand = math.random(1,#list)
end
end
-- Returns true only if list is now sorted
local function in_order ()
local last = list[1]
for i,v in next,list do
if v < last then return false end
last = v
end
return true
end
while not in_order() do shuffle() end
return list
end</lang>
M4
<lang M4>divert(-1) define(`randSeed',141592653) define(`setRand',
`define(`randSeed',ifelse(eval($1<10000),1,`eval(20000-$1)',`$1'))')
define(`rand_t',`eval(randSeed^(randSeed>>13))') define(`random',
`define(`randSeed',eval((rand_t^(rand_t<<18))&0x7fffffff))randSeed')
define(`for',
`ifelse($#,0,``$0, `ifelse(eval($2<=$3),1, `pushdef(`$1',$2)$4`'popdef(`$1')$0(`$1',incr($2),$3,`$4')')')')
define(`set',`define(`$1[$2]',`$3')') define(`new',`set($1,size,0)') define(`get',`defn($1[$2])') define(`append',
`set($1,size,incr(get($1,size)))`'set($1,get($1,size),$2)')
define(`deck',
`new($1)for(`x',1,$2,
`append(`$1',random)')')
define(`show',
`for(`x',1,get($1,size),`get($1,x)`'ifelse(x,get($1,size),`',`, ')')')
define(`swap',`set($1,$2,get($1,$4))`'set($1,$4,$3)') define(`shuffle',
`for(`x',1,get($1,size),
`swap($1,x,get($1,x),eval(1+random%get($1,size)))')')
define(`inordern',
`ifelse(eval($2>=get($1,size)),1,
1,
`ifelse(eval(get($1,$2)>get($1,incr($2))),1,
0,
`inordern(`$1',incr($2))')')')
define(`inorder',`inordern($1,1)') define(`bogosort',
`ifelse(inorder(`$1'),0,`nope shuffle(`$1')`'bogosort(`$1')')')
divert
deck(`b',6) show(`b') bogosort(`b') show(`b')</lang>
MAXScript
<lang maxscript>fn notSorted arr = (
if arr.count > 0 then
(
local current = arr[1]
for i in 2 to arr.count do
(
if current > arr[i] then
(
return true
)
current = arr[i]
)
)
false
)
fn randSort x y = (
random -1 1
)
fn shuffle arr = (
qsort arr randSort arr
)
fn bogosort arr = (
while notSorted arr do
(
arr = shuffle arr
)
arr
)</lang>
Modula-3
<lang modula3>MODULE Bogo EXPORTS Main;
IMPORT IO, Random;
VAR a := ARRAY [1..10] OF INTEGER {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
PROCEDURE Shuffle(VAR a: ARRAY OF INTEGER) =
VAR temp: INTEGER;
BEGIN
WITH rand = NEW(Random.Default).init() DO
FOR i := FIRST(a) TO LAST(a) - 1 DO
WITH j = rand.integer(i, LAST(a)) DO
temp := a[i];
a[i] := a[j];
a[j] := temp;
END;
END;
END;
END Shuffle;
PROCEDURE Sorted(VAR a: ARRAY OF INTEGER): BOOLEAN =
BEGIN
IF LAST(a) <= 1 THEN
RETURN TRUE;
END;
FOR i := FIRST(a) + 1 TO LAST(a) DO
IF (a[i] < a[i - 1]) THEN
RETURN FALSE;
END;
END;
RETURN TRUE;
END Sorted;
BEGIN
Shuffle(a);
WHILE NOT Sorted(a) DO
Shuffle(a);
END;
FOR i := FIRST(a) TO LAST(a) DO
IO.PutInt(a[i]);
IO.Put(" ");
END;
IO.PutChar('\n');
END Bogo.</lang>
Oberon-2
<lang oberon2>MODULE Bogo;
IMPORT Out, Random;
VAR a: ARRAY 10 OF INTEGER;
PROCEDURE Init;
VAR i: INTEGER;
BEGIN
FOR i := 0 TO LEN(a) - 1 DO
a[i] := i + 1;
END;
END Init;
PROCEDURE Sorted(VAR a: ARRAY OF INTEGER): BOOLEAN;
VAR i: INTEGER;
BEGIN
IF LEN(a) <= 1 THEN
RETURN TRUE;
END;
FOR i := 1 TO LEN(a) - 1 DO
IF (a[i] < a[i - 1]) THEN
RETURN FALSE;
END;
END;
RETURN TRUE;
END Sorted;
PROCEDURE Shuffle*(VAR a: ARRAY OF INTEGER);
VAR n, t, r: INTEGER;
BEGIN
FOR n := 0 TO LEN(a) - 1 DO
r := Random.Roll(n);
t := a[n];
a[n] := a[r];
a[r] := t;
END;
END Shuffle;
BEGIN
Init;
Shuffle(a);
WHILE ~Sorted(a) DO
Shuffle(a);
END;
FOR i := 0 TO LEN(a) - 1 DO
Out.Int(a[i], 0);
Out.String(" ");
END;
Out.Ln;
END Bogo.</lang>
Init initializes the array as 1 thru 10, then it is shuffled, and then the while loop continually shuffles until Sorted returns true.
OCaml
<lang ocaml>let rec is_sorted comp = function
| e1 :: e2 :: r -> comp e1 e2 <= 0 && is_sorted comp (e2 :: r) | _ -> true
(* Fisher-Yates shuffle on lists; uses temp array *) let shuffle l =
let ar = Array.of_list l in
for n = Array.length ar - 1 downto 1 do
let k = Random.int (n+1) in
let temp = ar.(k) in (* swap ar.(k) and ar.(n) *)
ar.(k) <- ar.(n);
ar.(n) <- temp
done;
Array.to_list ar
let rec bogosort li =
if is_sorted compare li then li else bogosort (shuffle li)</lang>
Example:
# bogosort [7;5;12;1;4;2;23;18] ;; - : int list = [1; 2; 4; 5; 7; 12; 18; 23]
Octave
<lang octave>function y = is_sorted(v)
y = true;
for i = 2:length(v)
if ( v(i-1) > v(i) )
y = false;
return
endif
endfor
endfunction
function r = shuffle(v)
l = length(v); for i = 1:l t = v(i); r = unidrnd(l); v(i) = v(r); v(r) = t; endfor r = v;
endfunction
function s = bogosort(v)
while( !is_sorted(v) ) v = shuffle(v); endwhile s = v;
endfunction</lang>
<lang octave>n = [ 1, 10, 9, 7, 3, 0 ]; disp(bogosort(n));</lang>
Perl
<lang perl>sub bogosort
{my @l = @_;
shuffle(\@l) until in_order(@l);
return @l;}
sub in_order
{my $last = shift(@_);
foreach (@_)
{$_ >= $last or return 0;
$last = $_;}
return 1;}
sub shuffle
- This uses the algorithm described at:
- http://en.wikipedia.org/wiki/Fisher-Yates_shuffle#The_modern_algorithm
{our @l; local *l = shift;
# @l is now an alias of the original argument.
for (my $n = $#l ; $n ; --$n)
{my $k = int rand($n + 1);
@l[$k, $n] = @l[$n, $k] if $k != $n;}}</lang>
PHP
<lang php>function bogosort($l) {
while (!in_order($l))
shuffle($l);
return $l;
}
function in_order($l) {
for ($i = 1; $i < count($l); $i++)
if ($l[$i] < $l[$i-1])
return FALSE;
return TRUE;
}</lang>
Python
<lang python>import random
def bogosort(l):
while not in_order(l):
random.shuffle(l)
return l
def in_order(l):
if not l:
return True
last = l[0]
for x in l[1:]:
if x < last:
return False
last = x
return True</lang>
Alternative definition for in_order (Python 2.5) <lang python>def in_order(l):
return all( l[i] <= l[i+1] for i in xrange(0,len(l)-1))</lang>
An alternative implementation for Python 2.5 or later: <lang python>import random 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</lang>
R
<lang R>bogosort <- function(x) {
is.sorted <- function(x) all(diff(x) >= 0) while(!is.sorted(x)) x <- sample(x) x
}
n <- c(1, 10, 9, 7, 3, 0) print(bogosort(n))</lang>
Ruby
<lang ruby>def shuffle(l)
l.sort_by { rand }
end
def bogosort(l)
l = shuffle(l) until in_order(l) l
end
def in_order(l)
(0..l.length-2).all? {|i| l[i] <= l[i+1] }
end</lang>
An alternative implementation:
<lang ruby>def shuffle(l)
l.sort_by { rand }
end
def bogosort(l)
l = shuffle(l) until l == l.sort l
end</lang>
Smalltalk
This implementation uses closures rather than extending collections to provide a bogosort method. <lang smalltalk>Smalltalk at: #isItSorted put: [ :c |
|isit| isit := false. (2 to: (c size)) detect: [ :i | ( (c at: ( i - 1 )) > (c at: i) ) ] ifNone: [ isit := true ]. isit
]. Smalltalk at: #bogosort put: [ :c |
[ isItSorted value: c ] whileFalse: [
1 to: (c size) do: [ :i |
|r t|
r := (Random between: 1 and: (c size)).
t := (c at: i).
c at: i put: (c at: r).
c at: r put: t
]
]
].
|tobesorted| tobesorted := { 2 . 7 . 5 . 3 . 4 . 8 . 6 . 1 }. bogosort value: tobesorted. tobesorted displayNl.</lang>
Tcl
<lang tcl>package require Tcl 8.5
proc shuffleInPlace {listName} {
upvar 1 $listName list
set len [set len2 [llength $list]]
for {set i 0} {$i < $len-1} {incr i; incr len2 -1} {
# Pick cell to swap with
set n [expr {int($i + $len2 * rand())}]
# Perform swap
set temp [lindex $list $i]
lset list $i [lindex $list $n]
lset list $n $temp
}
} proc inOrder {list} {
set prev [lindex $list 0]
foreach item [lrange $list 1 end] {
if {$prev > $item} {
return false
}
set prev $item
}
return true
} proc bogosort {list} {
while { ! [inOrder $list]} {
shuffleInPlace list
}
return $list
}</lang>
Ursala
<lang Ursala>#import std
- import nat
shuffle = @iNX ~&l->r ^jrX/~&l ~&lK8PrC
bogosort = (not ordered nleq)-> shuffle
- cast %nL
example = bogosort <8,50,0,12,47,51></lang> output:
<0,8,12,47,50,51>