
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.




*process source xref;
 bogosort: Proc Options(main);
 Dcl SYSPRINT Print;
 Dcl (HBOUND,RANDOM,TIME) Builtin;
 Dcl tim Pic'(9)9';
 Dcl timms Pic'(3)9' def tim pos(7);
 tim=time();
 x=random(timms);
 Dcl a(5)       Dec Fixed(5,1) Init(-21,333,0,444.4,1);
 Dcl (x,y,temp) Dec Fixed(5,1);
 Dcl (n,bogo,j,u,v) Bin Fixed(31);
 n=hbound(a);
 Call tell('un-bogoed');
 loop:
 Do bogo=1 By 1;
   Do j=1 To n-1;
     jp=j+1;
     x=a(j);
     y=a(jp);
     if y>=x Then
       Iterate;
     u=rand(1,n);
     Do Until v^=u
       v=rand(1,n);
       End;
     Temp=a(u);
     a(u)=a(v);
     a(v)=temp;
     Iterate loop;
     End;
   Leave;
   End;
 
 Put Edit('number of bogo sorts performed =',bogo)(Skip,a,f(4));
 call tell('   bogoed');
 Return;
 
 tell: Proc(txt);
 Dcl txt Char(*);
 Dcl t Bin Fixed(31);
 Put Edit(txt)(skip,a);
 Do t=1 to n;
   Put Edit(a(t))(Skip,f(6,1));
   End;
 End;
 
 rand: Proc(lo,hi) Returns(Bin Fixed(31));
 Dcl (lo,hi,res) Bin Fixed(31);
 Dcl r Bin Float(31);
 r=random();
 res=r*(hi-lo+1)+lo;
 Return(res);
 End;
 End;