
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.




MODULE Bogo EXPORTS Main;
 
IMPORT IO, Fmt, Random;
 
VAR a := ARRAY [1..5] OF INTEGER {1, 2, 3, 4, 5};
    count := 0;
 
PROCEDURE Shuffle(VAR a: ARRAY OF INTEGER) =
  VAR temp: INTEGER;
  BEGIN
    WITH rand = NEW(Random.Default).init() DO
      FOR i := FIRST(a) TO LAST(a) - 1 DO
        WITH j = rand.integer(i, LAST(a)) DO
          temp := a[i];
          a[i] := a[j];
          a[j] := temp;
        END;
      END;
    END;
  END Shuffle;
 
PROCEDURE Sorted(VAR a: ARRAY OF INTEGER): BOOLEAN =
  BEGIN
    IF NUMBER(a) <= 1 THEN
      RETURN TRUE;
    END;
    FOR i := FIRST(a) + 1 TO LAST(a) DO
      IF (a[i] < a[i - 1]) THEN
        RETURN FALSE;
      END;
    END;
    RETURN TRUE;
  END Sorted;
 
BEGIN
  Shuffle(a);
  WHILE NOT Sorted(a) DO
    Shuffle(a);
    INC(count);
  END;
  FOR i := FIRST(a) TO LAST(a) DO
    IO.PutInt(a[i]);
    IO.Put(" ");
  END;
  IO.Put("\nRequired " & Fmt.Int(count) & " shuffles\n");
END Bogo.