Sorting algorithms/Bogosort
![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.
Bogosort a list of numbers, Bogosort means to iterate through every permutation until you find one which is sorted.
Haskell
import Control.Monad bogosort l = head $ do p <- permute l if sorted p then return p else mzero sorted (e1 : e2 : r) = e1 <= e2 && sorted (e2 : r) sorted _ = True permute [] = return [] permute (h:t) = do { t' <- permute t ; insert h t' } insert e [] = return [e] insert e l@(h : t) = return (e : l) `mplus` do { t' <- insert e t ; return (h : t') }
Prolog
bogosort(L,S) :- permutation(L,S), sorted(S). sorted([]). sorted([_]). sorted([X,Y|ZS]) :- X =< Y, sorted([Y|ZS]). permutation([],[]). permutation([X|XS],YS) :- permutation(XS,ZS), select(X,YS,ZS).
Scheme
<scheme> (define (insertions e list)
(if (null? list) (cons (cons e list) list) (cons (cons e list) (map (lambda (tail) (cons (car list) tail)) (insertions e (cdr list))))))
(define (permutations list)
(if (null? list) (cons list list) (apply append (map (lambda (permutation) (insertions (car list) permutation)) (permutations (cdr list))))))
(define (sorted? list)
(cond ((null? list) #t) ((null? (cdr list)) #t) ((<= (car list) (cadr list)) (sorted? (cdr list))) (else #f)))
(define (bogosort list)
(let loop ((permutations (permutations list))) (if (sorted? (car permutations)) (car permutations) (loop (cdr permutations)))))
</scheme>