Sorting algorithms/Bogosort: Difference between revisions
m (→{{header|Java}}: Added note about comparable types) |
(remove sections moved to Permutation Sort) |
||
| Line 20: | Line 20: | ||
} |
} |
||
</cpp> |
</cpp> |
||
=={{header|Haskell}}== |
|||
{{incorrect|Haskell}} |
|||
<pre> |
|||
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') } |
|||
</pre> |
|||
=={{header|J}}== |
=={{header|J}}== |
||
| Line 69: | Line 50: | ||
} |
} |
||
}</java> |
}</java> |
||
=={{header|Prolog}}== |
|||
{{incorrect|Prolog}} |
|||
<pre> |
|||
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). |
|||
</pre> |
|||
=={{header|Scheme}}== |
|||
{{incorrect|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> |
|||
Revision as of 21:45, 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);
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>
J
bogo=: 3 : 0 whilst. -. *./ 2 </\ Ry do. Ry=. (A.~ ?@!@#) y end. Ry )
Java
This implementation works for all comparable types (types with compareTo defined). <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>