Sorting algorithms/Bogosort: Difference between revisions
(+D) |
(→{{header|Java}}: minor changes) |
||
Line 65: | Line 65: | ||
This implementation works for all comparable types (types with <tt>compareTo</tt> defined). |
This implementation works for all comparable types (types with <tt>compareTo</tt> defined). |
||
<java>import java.util.Collections; |
<java>import java.util.Collections; |
||
import java.util. |
import java.util.List; |
||
import java.util.Iterator; |
|||
public class Bogosort |
public class Bogosort { |
||
private static <T extends Comparable<? super T>> boolean isSorted(List<T> list) { |
|||
public LinkedList<T> bogoSort(LinkedList<T> list){ |
|||
if (list.isEmpty()) |
|||
boolean sorted= false; |
|||
return true; |
|||
while(!sorted){ |
|||
Iterator<T> it = list.iterator(); |
|||
sorted= true; |
|||
T last = it.next(); |
|||
for(int i= 0;i < list.size() - 1;i++){ |
|||
while (it.hasNext()) { |
|||
if(list.get(i).compareTo(list.get(i + 1)) > 0){ |
|||
T current = it.next(); |
|||
sorted= false; |
|||
if (last.compareTo(current) > 0) |
|||
} |
|||
return false; |
|||
} |
|||
last = current; |
|||
} |
|||
return true; |
|||
} |
|||
public static <T extends Comparable<? super T>> void bogoSort(List<T> list) { |
|||
if(!sorted){ |
|||
while (!isSorted(list)) |
|||
Collections.shuffle(list); |
|||
} |
|||
} |
|||
} |
|||
return list; |
|||
} |
|||
}</java> |
}</java> |
Revision as of 04:44, 9 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> Using the is_sorted function, part of the SGI STL implementation:
<cpp>#include <algorithm>
- include <ext/algorithm>
template<typename ForwardIterator>
void bogosort(ForwardIterator begin, ForwardIterator end)
{
while (!__gnu_cxx::is_sorted(begin, end)) std::random_shuffle(begin, end);
}</cpp>
D
<d>module bogosort ; import std.stdio, std.random ;
bool isSorted(T)(inout T[] a) { // test if a is already sorted
if(a.length <= 1) return true ; // 1-elemented/empty array is defined as sorted for(int i = 1 ; i < a.length ; i++) if(a[i] < a[i-1]) return false ; return true ;
}
T[] bogosort(T)(T[] s) {
while(!isSorted(s)) { for(int n = s.length ; n > 1 ; n--) { int i = rand() % n ; // random shuffling T tmp = s[i] ; s[i] = s[n - 1] ; s[n - 1] = tmp ; } } return s ;
}
void main() {
auto b = [2,7,4,3] ; writefln("%s", bogosort(b)) ; writefln("%s", b) ; // sort is in place
}</d>
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.List; import java.util.Iterator;
public class Bogosort {
private static <T extends Comparable<? super T>> boolean isSorted(List<T> list) { if (list.isEmpty()) return true; Iterator<T> it = list.iterator(); T last = it.next(); while (it.hasNext()) { T current = it.next(); if (last.compareTo(current) > 0) return false; last = current; } return true; }
public static <T extends Comparable<? super T>> void bogoSort(List<T> list) { while (!isSorted(list)) Collections.shuffle(list); }
}</java>