Sorting algorithms/Bogosort

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:

O(n logn) sorts

Heap sort | Merge sort | Patience sort | Quick sort

O(n log²n) sorts
Shell Sort

O(n²) 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)

Pseudocode:

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

C++

The following algorithm actually works for all sequences of comparable types; restricting to lists of integers would not make the code simpler. <cpp>#include <iterator>

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

}</cpp> Using the is_sorted function, part of the SGI STL implementation:

Works with: GCC

<cpp>#include <algorithm>

1. include <ext/algorithm>

template<typename ForwardIterator>

void bogosort(ForwardIterator begin, ForwardIterator end)

{

 while (!__gnu_cxx::is_sorted(begin, end))
   std::random_shuffle(begin, end);

}</cpp>

D

<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
 

}</d>

J

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

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

Java

Works with: Java version 1.5+

This implementation works for all comparable types (types with compareTo defined). <java>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);
   }

}</java>

OCaml

<ocaml>

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

1. Random.self_init();;

- : unit = ()

1. let shuffle = List.sort (fun _ _ -> Random.int 3 - 1) ;;

val shuffle : '_a list -> '_a list = <fun>

1. let rec bogosort li =

   if is_sorted ( < ) li then li
   else bogosort(shuffle li) ;;

val bogosort : '_a list -> '_a list = <fun>

1. bogosort [7;5;12;1;4;2;23;18] ;;

- : int list = [1; 2; 4; 5; 7; 12; 18; 23] </ocaml>

Perl

<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

1. This uses the algorithm described at:
2. 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;}}</perl>

Python

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

Alternative definition for in_order (Python 2.5) <python>def in_order(l):

   return not l or all( l[i] < l[i+1] for i in range(0,len(l)-1))</python>