Bogosort

Origem: Wikipédia, a enciclopédia livre.

De acordo com o Jargon File, bogo-sort é "the archetypal perversely awful algorithm" (o arquétipo do algoritmo perversamente inútil), 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.

Aqui está um pseudo-código do 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 tem 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.

[editar] Implementações

[editar] Python

from random import shuffle

def bogosort(seq):
    while seq != sorted(seq):
        shuffle(seq)

[editar] 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.

[editar] 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;
}

[editar] Perl

sub bogosort {
    my @a = @_;
    while( ! is_sorted(@a) ) {
      shuffle(\@a);
    }
    @a;
}

sub is_sorted {
    for( my $ctr = 1; $ctr <= $#_; $ctr++ ) {
      return if $_[$ctr-1] > $_[$ctr];
    }

    1;
}

sub shuffle {
    my $ref = shift;
    # Note: Not a fair shuffling algorithm
    for( my $ctr = 0; $ctr < @{$ref}; $ctr++ ) {
          my $index = int(rand(@{$ref}));
          my $temp = $ref->[$ctr];
          $ref->[$ctr] = $ref->[$index];
          $ref->[$index] = $temp;
    }
}