Sorting algorithms/Bogosort: Difference between revisions

Content added Content deleted

Inline

Revision as of 23:04, 18 December 2008

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" among computer enthusiasts (geeks and nerds). 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);

Ada

<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; </ada> 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

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>

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>

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>

C#

Works with: C# version 3.0+

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

} </csharp>

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>

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

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

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

Example:

*Main> bogosort [7,5,12,1,4,2,23,18]
[1,2,4,5,7,12,18,23]

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

J

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

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>

Modula-3

MODULE 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 Main.

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.

OCaml

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

</ocaml> Example:

# bogosort [7;5;12;1;4;2;23;18] ;;
- : int list = [1; 2; 4; 5; 7; 12; 18; 23]

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

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;}}</perl>

PHP

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

}</php>

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>

An alternative implementation for Python 2.5 or later:

<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

</python>