Bogosort

De acordo com o Jargon File, bogo-sort é o algoritmo perversamente horrendo arquetípico, um exemplo disto é a tentativa de ordenar um baralho repetidamente jogando as cartas ao ar, juntá-las aleatoriamente, e então verificar se as cartas estão ordenadas. Seu nome veio do engraçado termo quantum bogodynamics e, ultimamente, a palavra bogus. Outros nomes são bozo sort , blort sort e vai-na sort ou Estou com sort.

Aqui está o algoritmo:

função bogosort(array)
  enquanto não está_ordenado(array)
    array := permutação_aleatória(array)

Esse algoritmo é probabilístico por natureza. Se todos os elementos a serem ordenados são distintos, a complexidade esperada é O(n × n!). O tempo exato de execução esperado depende do quantos diferentes valores de elementos ocorrem, e quantas vezes cada um deles ocorre, mas para casos não-triviais o tempo esperado de execução é exponencial ou super-exponencial a n. Ele termina pela mesma razão do teorema do macaco infinito; existe alguma probabilidade de que aconteça a permutação correta, dado que em um infinito número de tentativas fatalmente a encontrará.

Deve-se notar que com os algoritmos geradores de números pseudo-aleatórios, que têm um número finito de estados e não são realmente aleatórios, o algoritmo pode nunca terminar para certos conjuntos de valores a serem ordenados.

Bogosort não é um algoritmo de ordenação estável.

Implementações

C

void EstoucomSort(int size, int *array)
{
    int i, j;

    for (i = 1; i <= size; i++)
        if (i == size)
            return;
        else if (array[i-1] > array[i])
            break;

    for (i = 0; i < size; i++) {
        j = rand() % size;
        if (array[i] != array[j])
            array[i] ^= array[j] ^= array[i] ^= array[j]; /* Método de swap favorito de 10 entre 10 [[l33t]] POGers. */
    }

    EstoucomSort(size, array); /* Estouro de pilha garantido para n >= 4. */
}

C++

 #include <algorithm>
 #include <vector>
 
 template<class T>
 void bogosort(std::vector<T>& array)
 {
     while (! is_sorted(array))
         std::random_shuffle(array.begin(), array.end());
 }
 
 template<class T>
 bool is_sorted(const std::vector<T>& array)
 {
     for (typename std::vector<T>::size_type i = 1; i < array.size(); ++i)
         if (array[i] < array[i-1]) return false;
     return true;
 }

Java

public static void bogoSort(int length, int range) {
        int []array = randomIntArray(length,range);
                
        while (! isSorted(array))
                array = randomArray(array);
                
        for (int i = 0; i < array.length; i++) {
                System.out.print(array[i] + " ");
        }
                
}
        
private static boolean isSorted(int [] array)
{
    for (int i = 0; i < (array.length - 1); ++i) {
        if (array[i] > array[i+1])
                return false;
    }
        
    return true;
}
        
private static int [] randomArray(int [] array) {
                 
    int size = array.length;
    int[] indices = new int[size]; 
    for (int i=0; i<size; i++) {
        indices[i] = i;
    }
              
    Random random = new Random();
    for (int i = 0; i < size; i++) {
      boolean unique = false;
      int nRandom = 0;
      while (!unique) {
        unique = true;
        nRandom = random.nextInt(size);
        for (int j = 0; j < i; j++) {
          if (indices[j] == nRandom) {
             unique = false;
             break;
          }
        }
      } 
         
      indices[i] = nRandom; 
    }
         
    int [] result = new int[size];
        for (int k = 0; k < size; k++) {
    result[indices[k]] = array[k];
    }

    return result;
}
        
private static int[] randomIntArray(int length, int n)
{
  int[] a = new int[length];
  Random generator = new Random();
  for (int i = 0; i < a.length; i++)
  {
      a[i] = generator.nextInt(n);
  }
  return a;
}

Pascal

 program bogosort (input, output);
 const max=10;   {*Tamanho do vetor *}
 type vetor=array[1..max] of integer;
 var lista, lista1: vetor;
     i: integer;
     j: boolean;
     pos: integer;
 
         function teste(var proto: vetor): boolean;     {*Verifica se o vetor NÃO está ordenado.*}
         var i: integer;
         begin
                 teste:=true;
                 for i:=2 to max do
                         if (proto[i]<proto[i-1]) then
                                 break;
                 if (i=max) and (proto[max]>=proto[max-1]) then
                         teste:=false;
         end;
 
 begin
         randomize;    {*Inicializa o gerador de numeros aleatórios *}
         writeln('Escreva abaixo os ', max,' elementos do vetor:');
         for i:=1 to max do
         begin
                 read(lista[i]);  
                 lista1[i]:=lista[i];
         end;
         for i:=1 to max do           {*Escreve o vetor recebido *}
                 write(lista1[i],' ');
         writeln;
         while teste(lista1) do    {*Enquanto o vetor nao esta ordenado...*}
         begin
                 j:=true;
                 for i:=1 to max do     {*Inicializa o vetor auxiliar *}
                         lista1[i]:=0;
                 for i:=1 to max do   {* Este loop preenche aleatoriamente o vetor auxiliar *}
                 begin
                         j:=true;
                         while j do {* Este while garante que nenhum dado será sobrescrito *}
                         begin
                                 pos:= random(max)+1;    {* Gera posição aleatória *}
                                 if lista1[pos]=0 then     {*Garante que a posição não está ocupada *}
                                 begin
                                         lista1[pos]:=lista[i];
                                         j:=false;
                                 end;
                         end;
                 end;
                 for i:=1 to max do     {* Imprime na tela a tentativa *}       
                         write(lista1[i],' ');
                 writeln;               
         end;
         write('A LISTA FOI ORDENADA!');
 end.

Perl

 use List::Util qw(shuffle);
 
 sub bogosort {
    my @a = @_;
    my @sorted = sort @a;
    while("@a" ne "@sorted") {
       @a = shuffle(@a);
    }
    return @a;
 }

Python

from random import shuffle
 
def bogosort(seq):
    while not all(x <= y for x, y in zip(seq, seq[1:])):
        shuffle(seq)
    return seq

Ruby

def bogosort(seq)
 seq.shuffle! while not seq[0..-2].zip(seq[1..-1]).all? {|a,b| a <= b}
end

Fluxograma

Ligações externas

• entrada para bogo-sort no Jargon File