
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.




PROC PrintArray(INT ARRAY a INT size)
  INT i
 
  Put('[)
  FOR i=0 TO size-1
  DO
    IF i>0 THEN Put(' ) FI
    PrintI(a(i))
  OD
  Put(']) PutE()
RETURN
 
PROC KnuthShuffle(INT ARRAY tab BYTE size)
  BYTE i,j
  INT tmp
 
  i=size-1
  WHILE i>0
  DO
    j=Rand(i+1)
    tmp=tab(i)
    tab(i)=tab(j)
    tab(j)=tmp
    i==-1
  OD
RETURN
 
BYTE FUNC IsSorted(INT ARRAY tab BYTE size)
  BYTE i
 
  IF size<2 THEN
    RETURN (1)
  FI
  FOR i=0 TO size-2
  DO
    IF tab(i)>tab(i+1) THEN
      RETURN (0)
    FI
  OD
RETURN (1)
 
PROC BogoSort(INT ARRAY a INT size)
  WHILE IsSorted(a,size)=0
  DO
    KnuthShuffle(a,size)
  OD
RETURN
 
PROC Test(INT ARRAY a INT size)
  PrintE("Array before sort:")
  PrintArray(a,size)
  BogoSort(a,size)
  PrintE("Array after sort:")
  PrintArray(a,size)
  PutE()
RETURN
 
PROC Main()
  INT ARRAY
    a(10)=[1 4 65535 0 7 4 20 65530],
    b(21)=[3 2 1 0 65535 65534 65533],
    c(8)=[101 102 103 104 105 106 107 108],
    d(12)=[1 65535 1 65535 1 65535 1
      65535 1 65535 1 65535]
 
  Test(a,8)
  Test(b,7)
  Test(c,8)
  Test(d,12)
RETURN