Sorting algorithms/Bogosort: Difference between revisions

Content added Content deleted

Inline

Revision as of 14:46, 8 August 2011

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

Translation of: python

Works with: ALGOL 68 version Standard - no extensions to language used

Works with: ALGOL 68G version Any - tested with release mk15-0.8b.fc9.i386

Works with: ELLA ALGOL 68 version Any (with appropriate job cards) - tested with release 1.8.8d.fc9.i386

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

Brat

<lang brat>bogosort = { list | sorted = list.sort #Kinda cheating here while { list != sorted } { list.shuffle! } list }

p bogosort [15 6 2 9 1 3 41 19]</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:

Works with: GCC

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

Works with: C# version 3.0+

<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 clojure>(ns bogosort

 (:use [clojure.contrib.seq-utils :only (shuffle)]))

(defn in-order? [less xs]

 (or (empty? xs)
     (empty? (next xs))
     (and (less (first xs) (second xs))
          (recur less (next xs)))))

(defn bogosort

 ([xs]     
    (bogosort < xs))
 ([less xs]
    (if (in-order? less xs) xs

(recur less (shuffle xs)))))

(println (bogosort [7,5,12,1,4,2,23,18]))</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 (x₁ x₂ … x_n) pred) is true when each of (pred x₁ x₂), …, (pred x_n-1 x_n) 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>import std.stdio, std.algorithm, std.random;

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

   while (!isSorted(data))
       randomShuffle(data);

}

void main() {

   auto array = [2, 7, 41, 11, 3, 1, 6, 5, 8];
   bogoSort(array);
   writeln(array);

}</lang> Output:

[1, 2, 3, 5, 6, 7, 8, 11, 41]

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>

Euphoria

<lang euphoria>function shuffle(sequence s)

   object temp
   integer j
   for i = length(s) to 1 by -1 do
       j = rand(i)
       if i != j then
           temp = s[i]
           s[i] = s[j]
           s[j] = temp
       end if
   end for
   return s

end function

function inOrder(sequence s)

   for i = 1 to length(s)-1 do
       if compare(s[i],s[i+1]) > 0 then
           return 0
       end if
   end for
   return 1

end function

function bogosort(sequence s)

   while not inOrder(s) do
       ? s
       s = shuffle(s)
   end while
   return s

end function

? bogosort(shuffle({1,2,3,4,5,6}))</lang>

Output:

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

Factor

<lang factor>USING: grouping kernel math random sequences ;

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

bogosort ( seq -- newseq ) [ dup sorted? ] [ randomize ] until ;</lang>

Fortran

Works with: Fortran version 90 and later

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

Go

<lang go>package main

import (

   "fmt"
   "rand"
   "time"
   "sort"

)

func main() {

   list := []int{31, 41, 59, 26, 53, 58, 97, 93, 23, 84}
   fmt.Println("unsorted:", list)
   temp := make([]int, len(list))
   rand.Seed(time.Nanoseconds())
   for !sort.IntsAreSorted(list) {
       for i, v := range rand.Perm(len(list)) {
           temp[i] = list[v]
       }
       copy(list, temp)
   }
   fmt.Println("sorted!  ", list)

}</lang> Output: (sometimes takes a few seconds)

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

Groovy

Solution (also implicitly tracks the number of shuffles required): <lang groovy>def bogosort = { list ->

   def n = list.size()
   while (n > 1 && (1..<n).any{ list[it-1] > list[it] }) {
       print '.'*n
       Collections.shuffle(list)
   }
   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 and Unicon

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

Io

<lang io>List do(

   isSorted := method(
       slice(1) foreach(i, x,
           if (x < at(i), return false)
       )
       return true;
   )

   bogoSortInPlace := method(
       while(isSorted not,
           shuffleInPlace()
       )
   )

)

lst := list(2, 1, 4, 3) lst bogoSortInPlace println # ==> list(1, 2, 3, 4), hopefully :)</lang>

J

Generally, this task should be accomplished in J using /:~. Here we take an approach that's more comparable with the other examples on this page.

<lang j>bogo=: monad define

 whilst.  +./ 2 >/\ Ry  do. Ry=. (A.~ ?@!@#) y  end. Ry

)</lang>

Java

Works with: Java version 1.5+

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 = Math.floor(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>

MATLAB

<lang MATLAB>function list = bogoSort(list)

   while( ~issorted(list) ) %Check to see if it is sorted
       list = list( randperm(numel(list)) ); %Randomly sort the list
   end

end</lang>

Sample Output: <lang MATLAB>bogoSort([5 3 8 4 9 7 6 2 1])

ans =

    1     2     3     4     5     6     7     8     9

</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, Fmt, Random;

VAR a := ARRAY [1..5] OF INTEGER {1, 2, 3, 4, 5};

   count := 0;

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 NUMBER(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);
   INC(count);
 END;
 FOR i := FIRST(a) TO LAST(a) DO
   IO.PutInt(a[i]);
   IO.Put(" ");
 END;
 IO.Put("\nRequired " & Fmt.Int(count) & " shuffles\n");

END Bogo.</lang>

Nemerle

<lang Nemerle>using System; using System.Console; using Nemerle.Imperative;

module Bogosort {

   public static Bogosort[T] (this x : array[T]) : void
     where T : IComparable
   {
       def rnd = Random();
       def shuffle(a)
       {
           foreach (i in [0 .. (a.Length - 2)])
           a[i] <-> a[(rnd.Next(i, a.Length))];
       }
       
       def isSorted(b)
       {
           when (b.Length <= 1) return true;
           foreach (i in [1 .. (b.Length - 1)])
               when (b[i].CompareTo(b[i - 1]) < 0) return false;
           true;
       }
       
       def loop()
       {
           unless (isSorted(x)) {shuffle(x); loop();};
       }

       loop()
   }
   
   Main() : void
   {
       def sortme = array[1, 5, 3, 6, 7, 3, 8, -2];
       sortme.Bogosort();
       foreach (i in sortme) Write($"$i  ");
   }

}</lang>

Oberon-2

Works with: Oxford Oberon-2 Compiler

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

PARI/GP

This implementation sorts 9 distinct elements in only 600 milliseconds. <lang parigp>bogosort(v)={

 while(1,
   my(u=vecextract(v,numtoperm(#v,random((#v)!))));
   for(i=2,#v,if(u[i]<u[i-1], next(2)));
   return(u)
 );

};</lang>

Pascal

<lang Pascal>program bogosort;

const

 max = 5;

type

 list = array [1..max] of integer;

{ Print a list } procedure printa(a: list); var

 i: integer;

begin

 for i := 1 to max do
   write(a[i], ' ');
 writeln

end;

{ Knuth shuffle } procedure shuffle(var a: list); var

 i,k,tmp: integer;

begin

 for i := max downto 2 do begin
    k := random(i) + 1;
    if (a[i] <> a[k]) then begin
      tmp := a[i]; a[i] := a[k]; a[k] := tmp
    end
 end

end;

{ Check for sorted list } function sorted(a: list): boolean; var

 i: integer;

begin

 sorted := True;
 for i := 2 to max do
   if (a[i - 1] > a[i]) then begin
     sorted := False; exit
   end

end;

{ Bogosort } procedure bogo(var a: list); var

 i: integer;

begin

 i := 1; randomize;
 write(i,': '); printa(a);
 while not sorted(a) do begin
   shuffle(a);
   i := i + 1; write(i,': '); printa(a)
 end

end;

{ Test and display } var

 a: list;
 i: integer;

begin

 for i := 1 to max do
   a[i] := (max + 1) - i;
 bogo(a);

end.</lang>

Sample Output:

1: 5 4 3 2 1
2: 3 5 4 1 2
. . . . . .
22: 3 2 1 5 4
23: 1 2 3 4 5

Perl

<lang perl>use List::Util qw(shuffle);

sub bogosort

{my @l = @_;
 @l = shuffle(@l) until in_order(@l);
 return @l;}

sub in_order

{my $last = shift;
 foreach (@_)
    {$_ >= $last or return 0;
     $last = $_;}
 return 1;}</lang>

Perl 6

<lang perl6>sub bogosort (@list is copy) {

   @list .= pick(*) until [<=] @list;
   return @list;

}

my @nums = (^5).map: { rand }; say @nums.sort.Str eq @nums.&bogosort.Str ?? 'ok' !! 'not ok'; </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>

PicoLisp

<lang PicoLisp>(de bogosort (Lst)

  (loop
     (map
        '((L) (rot L (rand 1 (length L))))
        Lst )
     (T (apply <= Lst) Lst) ) )</lang>

Output:

: (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)))))
-> (20 51 117 229 671 848 883 948 978)

: (bogosort (make (do 9 (link (rand 1 999)))))
-> (1 21 72 263 391 476 794 840 878)

PowerShell

Shuffle taken from Knuth Shuffle <lang PowerShell>function shuffle ($a) {

   $c = $a.Clone()  # make copy to avoid clobbering $a
   1..($c.Length - 1) | ForEach-Object {
       $i = Get-Random -Minimum $_ -Maximum $c.Length
       $c[$_-1],$c[$i] = $c[$i],$c[$_-1]
       $c[$_-1]  # return newly-shuffled value
   }
   $c[-1]  # last value

}

function isSorted( [Array] $data ) { $sorted = $true for( $i = 1; ( $i -lt $data.length ) -and $sorted; $i++ ) { $sorted = $data[ $i - 1 ] -le $data[ $i ] } $sorted }

function BogoSort ( [Array] $indata ) { $data = $indata.Clone() while( -not ( isSorted $data ) ) { $data = shuffle $indata } $data }

$l = 7; BogoSort ( 1..$l | ForEach-Object { $Rand = New-Object Random }{ $Rand.Next( 0, $l - 1 ) } )</lang>

PureBasic

<lang PureBasic>Procedure KnuthShuffle (Array a(1))

 Protected i, Size = ArraySize(a())
 For i = 0 To Size             
   Swap a(i), a(Random(Size)) 
 Next

EndProcedure

Procedure isSorted(Array a(1))

 Protected i, Size = ArraySize(a())
 For i = 1 To Size
   If a(i) < a(i - 1)
     ProcedureReturn #False
   EndIf
 Next
 ProcedureReturn #True

EndProcedure

Procedure BogoSort(Array a(1))

 Protected Size = ArraySize(a()) + 1, iter
  
 While Not isSorted(a())
   iter + 1
   KnuthShuffle(a())
 Wend
 MessageRequester("Results","Array of " + Str(Size) + " integers required " + Str(iter) + " shuffles To SORT.")

EndProcedure

Dim b(10) For i = 0 To 10

 b(i) = Random(100)

Array of 10 integers required 2766901 shuffles To SORT.

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>

REXX

This is a modified bogo sort.

To verify the array is in order, a sequential search is performed.
When an number is found out of order, two random numbers between the first number's position and the the position of the last number checked are swapped.
A check is made to ensure that one number isn't being swapped with itself.
The search then starts over.
This is repeated as often as it takes to finally get the array in order. <lang rexx> /*REXX program to perform a type of bogo sort on an array. */

a.1=          0            /*this is really the 0th Berstel number... */
a.2=          0
a.3=          1
a.4=          2
a.5=          0
a.6=         -4
a.7=          0
a.8=         16
a.9=         16

a.10= -32 a.11= -64 a.12= 64 a.13= 256 a.14= 0 a.15= -768 a.16= -512 a.17= 2048 a.18= 3072 a.19= -4096 a.20= -12288 a.21= 4096 a.22= 40960 a.23= 16384 a.24= -114688 a.25= -131072 a.26= 262144 a.27= 589824 a.28= -393216 a.29= -2097152 a.30= -262144 a.31= 6291456 a.32= 5242880 a.33= -15728640 a.34= -27262976 a.35= 29360128 a.36= 104857600 a.37= -16777216 a.38= -335544320 a.39= -184549376 a.40= 905969664

size=40 /*we have a list of two score Berstel numbers.*/ call tell 'un-bogoed'

 do bogo=1

   do j=1 for size
   _=a.j

     do k=j+1 to size
     if a.k>=_ then iterate
     n=random(j,k)               /*we have an num out of order.get rand*/
       do forever; m=random(j,k) /*get another random number.*/
       if m\==n then leave       /*ensure we're not swapping the same #*/
       end
     parse value a.n a.m with a.m a.n  /*swap 2 random nums*/
     iterate bogo
     end   /*k*/

   end     /*j*/

 leave
 end     /*bogo*/

say 'number of bogo sorts performed =' bogo-1 call tell ' bogoed' exit

tell: say say center(arg(1),40,'-')

 do j=1 to size
 say arg(1) 'element'right(j,length(size))'='right(a.j,20)
 end

say return </lang> Output:


---------------un-bogoed----------------
un-bogoed element 1=                   0
un-bogoed element 2=                   0
un-bogoed element 3=                   1
un-bogoed element 4=                   2
un-bogoed element 5=                   0
un-bogoed element 6=                  -4
un-bogoed element 7=                   0
un-bogoed element 8=                  16
un-bogoed element 9=                  16
un-bogoed element10=                 -32
un-bogoed element11=                 -64
un-bogoed element12=                  64
un-bogoed element13=                 256
un-bogoed element14=                   0
un-bogoed element15=                -768
un-bogoed element16=                -512
un-bogoed element17=                2048
un-bogoed element18=                3072
un-bogoed element19=               -4096
un-bogoed element20=              -12288
un-bogoed element21=                4096
un-bogoed element22=               40960
un-bogoed element23=               16384
un-bogoed element24=             -114688
un-bogoed element25=             -131072
un-bogoed element26=              262144
un-bogoed element27=              589824
un-bogoed element28=             -393216
un-bogoed element29=            -2097152
un-bogoed element30=             -262144
un-bogoed element31=             6291456
un-bogoed element32=             5242880
un-bogoed element33=           -15728640
un-bogoed element34=           -27262976
un-bogoed element35=            29360128
un-bogoed element36=           104857600
un-bogoed element37=           -16777216
un-bogoed element38=          -335544320
un-bogoed element39=          -184549376
un-bogoed element40=           905969664

number of bogo sorts performed = 3652

----------------  bogoed----------------
  bogoed element 1=          -335544320
  bogoed element 2=          -184549376
  bogoed element 3=           -27262976
  bogoed element 4=           -16777216
  bogoed element 5=           -15728640
  bogoed element 6=            -2097152
  bogoed element 7=             -393216
  bogoed element 8=             -262144
  bogoed element 9=             -131072
  bogoed element10=             -114688
  bogoed element11=              -12288
  bogoed element12=               -4096
  bogoed element13=                -768
  bogoed element14=                -512
  bogoed element15=                 -64
  bogoed element16=                 -32
  bogoed element17=                  -4
  bogoed element18=                   0
  bogoed element19=                   0
  bogoed element20=                   0
  bogoed element21=                   0
  bogoed element22=                   0
  bogoed element23=                   1
  bogoed element24=                   2
  bogoed element25=                  16
  bogoed element26=                  16
  bogoed element27=                  64
  bogoed element28=                 256
  bogoed element29=                2048
  bogoed element30=                3072
  bogoed element31=                4096
  bogoed element32=               16384
  bogoed element33=               40960
  bogoed element34=              262144
  bogoed element35=              589824
  bogoed element36=             5242880
  bogoed element37=             6291456
  bogoed element38=            29360128
  bogoed element39=           104857600
  bogoed element40=           905969664

More tests showed that:

number of bogo sorts performed = 2583
number of bogo sorts performed = 2376
number of bogo sorts performed = 1791
number of bogo sorts performed = 2537
number of bogo sorts performed = 1856
number of bogo sorts performed = 2339
number of bogo sorts performed = 2511
number of bogo sorts performed = 2652
number of bogo sorts performed = 1697
number of bogo sorts performed = 1782
number of bogo sorts performed = 2074
number of bogo sorts performed = 4017
number of bogo sorts performed = 2469
number of bogo sorts performed = 3707
number of bogo sorts performed = 1729
number of bogo sorts performed = 1705
number of bogo sorts performed = 4071

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>

Works with: Ruby version 1.8.7+

<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

Works with: Scala version 2.8

<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

Works with: GNU 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>

SNOBOL4

<lang SNOBOL4>* Library for random() -include 'Random.sno'

# String -> array

       define('s2a(str,n)i') :(s2a_end)

s2a s2a = array(n); str = str ' ' sa1 str break(' ') . s2a span(' ') = :s(sa1)f(return) s2a_end

# Array -> string
define('a2s(a)i') :(a2s_end)
a2s a2s = a2s a ' ' :s(a2s)f(return) a2s_end
# Knuth shuffle in-place
define('shuffle(a)alen,n,k,tmp') :(shuffle_end)
shuffle n = alen = prototype(a); sh1 k = convert(random() * alen,'integer') + 1
eq(a<n>,a<k>) :s(sh2) tmp = a<n>; a<n> = a<k>; a<k> = tmp
sh2 n = gt(n,1) n - 1 :s(sh1)
shuffle = a :(return)
shuffle_end
# sorted( ) predicate -> Succeed/Fail
define('sorted(a)alen,i') :(sorted_end)
sorted alen = prototype(a); i = 1 std1 i = lt(i,alen) i + 1 :f(return)
gt(a,a) :s(freturn)f(std1)
sorted_end
# Bogosort
define('bogo(a)') :(bogo_end)
bogo output = (i = i + 1) ': ' a2s(a)
bogo = sorted(a) a :s(return) shuffle(a) :(bogo)
bogo_end
# Test and display
bogo(s2a('5 4 3 2 1',5))
end</lang>
Sample Output:
1: 5 4 3 2 1 2: 2 1 4 3 5 . . . . . . 117: 3 2 1 5 4 118: 1 2 3 4 5
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" :L₁→L₂ :Lbl A :dim(L₂)→A :For(B,1,dim(L₂)-1) :randInt(1,A)→C :L₂(C)→D :L₂(A)→L₂(C) :D→L₂(A) :A-1→A :End :For(D,1,dim(L₂)-1) :If L₂(D)>L₂(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₁, run prgmSORTBOZO, outputs to L₂
:L₁→L₂ :Lbl T :0→B :For(A,1,dim(L₂)-1) :If L₂(A)>L₂(A+1) :1→B :End :If B=0 :Goto E :randInt(1,dim(L₂))→C :randInt(1,dim(L₂))→D :L₂(C)→E :L₂(C+1)→L₂(C) :E→L₂(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>
VBScript
Implementation
<lang vb>sub swap( byref a, byref b ) dim tmp tmp = a a = b b = tmp end sub
'knuth shuffle (I think) function shuffle( a ) dim i dim r randomize timer for i = lbound( a ) to ubound( a ) r = int( rnd * ( ubound( a ) + 1 ) ) if r <> i then swap a(i), a(r) end if next shuffle = a end function
function inOrder( a ) dim res dim i for i = 0 to ubound( a ) - 1 res = ( a(i) <= a(i+1) ) if res = false then exit for next inOrder = res end function</lang>
Invocation
<lang vb>dim a a = array(11, 1, 2, 3, 4, 4, 6, 7, 8)
dim t t = timer while not inorder( a ) shuffle a wend wscript.echo timer-t, "seconds" wscript.echo join( a, ", " )</lang>
A few outputs (timed)
10.34766 seconds 1, 2, 3, 4, 4, 6, 7, 8, 11 0.5039063 seconds 1, 2, 3, 4, 4, 6, 7, 8, 11 1.980469 seconds 1, 2, 3, 4, 4, 6, 7, 8, 11