Sorting algorithms/Bogosort: Difference between revisions
(→{{header|TI-83 BASIC}}: Added ti83b) |
(→{{header|TI-83 BASIC}}: added ti83b bogosort) |
||
Line 1,107:
=={{header|TI-83 BASIC}}==
Same IO as BozoSort (below).
:"BOGO"
:L<sub>1</sub>→L<sub>2</sub>
:Lbl A
:dim(L<sub>2</sub>)→A
:For(B,1,dim(L<sub>2</sub>)-1)
:randInt(1,A)→C
:L<sub>2</sub>(C)→D
:L<sub>2</sub>(A)→L<sub>2</sub>(C)
:D→L<sub>2</sub>(A)
:A-1→A
:End
:For(D,1,dim(L<sub>2</sub>)-1)
:If L<sub>2</sub>(D)>L<sub>2</sub>(D+1)
:Goto A
:End
:DelVar A
:DelVar B
:DelVar C
:DelVar D
:Return
This isn't a bogosort, but a bozosort. Store input into L<sub>1</sub>, run prgmSORTBOZO, outputs to L<sub>2</sub>
:L<sub>1</sub>→L<sub>2</sub>
|
Revision as of 00:35, 1 February 2010
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>
Mathematica
<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}</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>
Oz
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.
<lang oz>declare
proc {BogoSort Arr} for while:{Not {InOrder Arr}} do {Shuffle Arr} end end
fun {InOrder Arr} for I in {Array.low Arr}+1..{Array.high Arr}
return:Return default:true
do if Arr.(I-1) > Arr.I then {Return false} end end end
proc {Shuffle Arr} Low = {Array.low Arr} High = {Array.high Arr} in for I in High..Low;~1 do
J = Low + {OS.rand} mod (I - Low + 1)
OldI = Arr.I in
Arr.I := Arr.J
Arr.J := OldI end end
X = {Tuple.toArray unit(3 1 4 1 5 9 2 6 5)}
in
{BogoSort X} {Show {Array.toRecord unit X}}</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>
<lang ruby>def in_order(l)
(0..l.length-2).all? {|i| l[i] <= l[i+1] }
end
def bogosort(l)
l.shuffle! until in_order(l) l
end</lang>
Scala
<lang scala>def isSorted(l: List[Int]) = l.iterator sliding 2 forall (s => s.head < s.last) def bogosort(l: List[Int]): List[Int] = if (isSorted(l)) l else bogosort(scala.util.Random.shuffle(l))</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>
TI-83 BASIC
Same IO as BozoSort (below).
:"BOGO" :L1→L2 :Lbl A :dim(L2)→A :For(B,1,dim(L2)-1) :randInt(1,A)→C :L2(C)→D :L2(A)→L2(C) :D→L2(A) :A-1→A :End :For(D,1,dim(L2)-1) :If L2(D)>L2(D+1) :Goto A :End :DelVar A :DelVar B :DelVar C :DelVar D :Return
This isn't a bogosort, but a bozosort. Store input into L1, run prgmSORTBOZO, outputs to L2
:L1→L2 :Lbl T :0→B :For(A,1,dim(L2)-1) :If L2(A)>L2(A+1) :1→B :End :If B=0 :Goto E :randInt(1,dim(L2))→C :randInt(1,dim(L2))→D :L2(C)→E :L2(C+1)→L2(C) :E→L2(C+1) :Goto T :Lbl E :DelVar A :DelVar B :DelVar C :DelVar D :DelVar E :Stop
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>