Sorting algorithms/Bogosort
Bogosort a list of numbers, Bogosort means to iterate through every permutation until you find one which is sorted.
Sorting algorithms/Bogosort
You are encouraged to solve this task according to the task description, using any language you may know.
You are encouraged to solve this task according to the task description, using any language you may know.
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 (permutation-sort list)
(let loop ((permutations (permutations list))) (if (sorted? (car permutations)) (car permutations) (loop (cdr permutations)))))
</scheme>