Sorting algorithms/Bogosort: Difference between revisions
No edit summary |
(Undo revision 15435 by 137.195.250.2 (Talk) The description of shuffling is correct...see http://en.wikipedia.org/wiki/Bogosort) |
||
Line 1: | Line 1: | ||
{{task}}{{Sorting Algorithm}}Bogosort a list of numbers. Bogosort simply shuffles a collection until it is sorted. |
{{task}}{{Sorting Algorithm}}Bogosort a list of numbers. Bogosort simply shuffles a collection until it is sorted. |
||
⚫ | |||
Pseudocode: |
Pseudocode: |
||
Line 6: | Line 5: | ||
=={{header|Haskell}}== |
=={{header|Haskell}}== |
||
⚫ | |||
<pre> |
<pre> |
||
import Control.Monad |
import Control.Monad |
||
Line 29: | Line 29: | ||
=={{header|Java}}== |
=={{header|Java}}== |
||
⚫ | |||
{{works with|Java|1.5+}} |
{{works with|Java|1.5+}} |
||
<java>import java.util.Collections; |
<java>import java.util.Collections; |
||
Line 55: | Line 54: | ||
=={{header|Prolog}}== |
=={{header|Prolog}}== |
||
⚫ | |||
<pre> |
<pre> |
||
bogosort(L,S) :- permutation(L,S), sorted(S). |
bogosort(L,S) :- permutation(L,S), sorted(S). |
||
Line 67: | Line 67: | ||
=={{header|Scheme}}== |
=={{header|Scheme}}== |
||
{{incorrect|Scheme}} |
|||
<scheme> |
<scheme> |
||
(define (insertions e list) |
(define (insertions e list) |
Revision as of 00:24, 8 May 2008
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.
Pseudocode:
while not InOrder(list) do Shuffle(list);
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') }
J
bogo=: 3 : 0 whilst. -. *./ 2 </\ Ry do. Ry=. (A.~ ?@!@#) y end. Ry )
Java
<java>import java.util.Collections; import java.util.LinkedList;
public class Bogosort<T extends Comparable<T>> { public LinkedList<T> bogoSort(LinkedList<T> list){ boolean sorted= false; while(!sorted){ sorted= true; for(int i= 0;i < list.size() - 1;i++){ if(list.get(i).compareTo(list.get(i + 1)) > 0){ sorted= false; } }
if(!sorted){ Collections.shuffle(list); } } return list; } }</java>
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>