
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:

O(n logn) sorts
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


Task

Bogosort a list of numbers.



Bogosort simply shuffles a collection randomly until it is sorted.

"Bogosort" is a perversely inefficient algorithm only used as an in-joke.

Its average run-time is   O(n!)   because the chance that any given shuffle of a set will end up in sorted order is about one in   n   factorial,   and the worst case is infinite since there's no guarantee that a random shuffling will ever produce a sorted sequence.

Its best case is   O(n)   since a single pass through the elements may suffice to order them.



Pseudocode:

while not InOrder(list) do
   Shuffle(list)
done



The Knuth shuffle may be used to implement the shuffle part of this algorithm.




* Library for random()
-include 'Random.sno'
 
*       # String -> array
        define('s2a(str,n)i') :(s2a_end)
s2a     s2a = array(n); str = str ' '
sa1     str break(' ') . s2a<i = i + 1> span(' ') = :s(sa1)f(return)
s2a_end
 
*       # Array -> string
        define('a2s(a)i') :(a2s_end)
a2s     a2s = a2s a<i = i + 1> ' ' :s(a2s)f(return)
a2s_end
 
*       # Knuth shuffle in-place
        define('shuffle(a)alen,n,k,tmp') :(shuffle_end)
shuffle n = alen = prototype(a);
sh1     k = convert(random() * alen,'integer') + 1
        eq(a<n>,a<k>) :s(sh2)
        tmp = a<n>; a<n> = a<k>; a<k> = tmp
sh2     n = gt(n,1) n - 1 :s(sh1)
        shuffle = a :(return)
shuffle_end
 
*       # sorted( ) predicate -> Succeed/Fail
        define('sorted(a)alen,i') :(sorted_end)
sorted  alen = prototype(a); i = 1
std1    i = lt(i,alen) i + 1 :f(return)
        gt(a<i - 1>,a<i>) :s(freturn)f(std1)
sorted_end
 
*       # Bogosort
        define('bogo(a)') :(bogo_end)
bogo    output = (i = i + 1) ': ' a2s(a)
        bogo = sorted(a) a :s(return)
        shuffle(a) :(bogo)
bogo_end
 
*       # Test and display
        bogo(s2a('5 4 3 2 1',5))
end