Sorting algorithms/Bogosort: Difference between revisions
added haskell |
|||
Line 113: | Line 113: | ||
END PROGRAM BOGOSORT |
END PROGRAM BOGOSORT |
||
=={{header|Haskell}}== |
|||
<pre> |
|||
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 |
|||
</pre> |
|||
Example: |
|||
<pre> |
|||
*Main> bogosort [7,5,12,1,4,2,23,18] |
|||
[1,2,4,5,7,12,18,23] |
|||
</pre> |
|||
=={{header|Java}}== |
=={{header|Java}}== |
Revision as of 04:54, 23 October 2008
![Task](http://static.miraheze.org/rosettacodewiki/thumb/b/ba/Rcode-button-task-crushed.png/64px-Rcode-button-task-crushed.png)
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)
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>
- 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:
<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>
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
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]
Java
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>
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>
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>