
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.




/*REXX program performs a type of  bogo sort  on  numbers in an array.  */
parse arg list                         /*obtain optional list from C.L. */
if list=''  then list=-21 333 0 444.4  /*Not defined?  Then use default.*/
#=words(list)                          /*the number of numbers in list. */
   do i=1  for words(list);  @.i=word(list,i);  end   /*create an array.*/
call tell 'before bogo sort'
 
  do bogo=1
 
    do j=1  for #-1;   jp=j+1          /* [↓]  compare a # with the next*/
    if @.jp>=@.j  then iterate         /*so far, so good;  keep looking.*/
                                       /*get 2 unique random #s for swap*/
       do  until a\==b;  a=random(1, #);     b=random(1, #);    end
 
    parse value @.a @.b  with  @.b @.a /*swap 2 random numbers in array.*/
    iterate bogo                       /*go and try another bogo sort.  */
    end     /*j*/
 
  leave                                /*we're finished with bogo sort. */
  end       /*bogo*/                   /* [↓]  show the # of bogo sorts.*/
 
say 'number of bogo sorts performed =' bogo
call tell ' after bogo sort'
exit                                   /*stick a fork in it, we're done.*/
/*──────────────────────────────────TELL subroutine─────────────────────*/
tell:  say;  say center(arg(1), 50, '─')
                 do t=1  for #
                 say arg(1)  'element'right(t, length(#))'='right(@.t, 18)
                 end   /*t*/
say
return