Bogosort

From Rosetta Code

Bogosort a list of numbers. Bogosort simply shuffles a collection until it is sorted. (read the article on Wikipedia)

Pseudocode:

while not InOrder(list) do Shuffle(list);

Contents 1 C++ 2 D 3 J 4 Fortran 5 Java 6 Oberon-2 7 OCaml 8 Perl 9 Python

[edit] C++

The following algorithm actually works for all sequences of comparable types; restricting to lists of integers would not make the code simpler.

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

Using the is_sorted function, part of the SGI STL implementation:

Works with: GCC

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

[edit] 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
 
}

[edit] J

bogo=: 3 : 0
whilst. -. *./ 2 </\ Ry  do. Ry=. (A.~ ?@!@#) y  end. Ry
)

[edit] Fortran

Works with: Fortran version 90 and later

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

[edit] Java

Works with: Java version 1.5+

This implementation works for all comparable types (types with compareTo defined).

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

[edit] Oberon-2

Works with Oxford Oberon-2 Compiler.

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 PrintArray(VAR a: ARRAY OF INTEGER);
      VAR i: INTEGER;
   BEGIN
      FOR i := 0 TO LEN(a) - 1 DO
         Out.Int(a[i], 0);
         Out.String(" ");
      END;
   END PrintArray;

   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;
   PrintArray(a);
   Out.Ln;
END Bogo.

Init initializes the array as 1..10, then it is shuffled, and then the while loop continually shuffles until Sorted returns true.

[edit] OCaml

 
# let is_sorted comp (x::xs) =
    let rec aux prev = function
    | [] -> true
    | x::xs ->
        if comp x prev then false
        else aux x xs
    in
    aux x xs
  ;;
val is_sorted : ('a -> 'a -> bool) -> 'a list -> bool = <fun>
 
# Random.self_init();;
- : unit = ()
 
# let shuffle = List.sort (fun _ _ -> Random.int 3 - 1) ;;
val shuffle : '_a list -> '_a list = <fun>
 
# let rec bogosort li =
    if is_sorted ( < ) li then li
    else bogosort(shuffle li) ;;
val bogosort : '_a list -> '_a list = <fun>
 
# bogosort [7;5;12;1;4;2;23;18] ;;
- : int list = [1; 2; 4; 5; 7; 12; 18; 23]
 

[edit] 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;}}

[edit] 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

Alternative definition for in_order (Python 2.5)

def in_order(l):
    return not l or all( l[i] < l[i+1] for i in range(0,len(l)-1))