Sorting algorithms/Bogosort: Difference between revisions
Content added Content deleted
(New page: {{task}}Bogosort a list of numbers, Bogosort means to iterate through every permutation until you find one which is sorted. =={{header|Haskell}}== <pre> import Control.Monad bogosort l ...) |
|||
Line 53: | Line 53: | ||
(else #f))) |
(else #f))) |
||
(define ( |
(define (bogosort list) |
||
(let loop ((permutations (permutations list))) |
(let loop ((permutations (permutations list))) |
||
(if (sorted? (car permutations)) |
(if (sorted? (car permutations)) |
Revision as of 01:30, 7 May 2008
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.
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>