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 horrendo), 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 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.
Índice |
[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;
}
}
[editar] 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;
}
[editar] Fluxograma
