
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.




with Ada.Text_IO;  use Ada.Text_IO;
with Ada.Numerics.Discrete_Random;
 
procedure Test_Bogosort is
   generic
      type Ordered is private;
      type List is array (Positive range <>) of Ordered;
      with function "<" (L, R : Ordered) return Boolean is <>;
   procedure Bogosort (Data : in out List);
 
   procedure Bogosort (Data : in out List) is
      function Sorted return Boolean is
      begin
         for I in Data'First..Data'Last - 1 loop
            if not (Data (I) < Data (I + 1)) then
               return False;
            end if;
         end loop;
         return True;
      end Sorted;
      subtype Index is Integer range Data'Range;
      package Dices is new Ada.Numerics.Discrete_Random (Index);
      use Dices;
      Dice : Generator;
      procedure Shuffle is
         J    : Index;
         Temp : Ordered;
      begin
         for I in Data'Range loop
            J := Random (Dice);
            Temp := Data (I);
            Data (I) := Data (J);
            Data (J) := Temp;
         end loop;
      end Shuffle;
   begin
      while not Sorted loop
         Shuffle;
      end loop;
   end Bogosort;
 
   type List is array (Positive range <>) of Integer;
   procedure Integer_Bogosort is new Bogosort (Integer, List);
   Sequence : List := (7,6,3,9);
begin
   Integer_Bogosort (Sequence);
   for I in Sequence'Range loop
      Put (Integer'Image (Sequence (I)));
   end loop;
end Test_Bogosort;