O que faz exatamente o algoritmo de ordenação bogosort?
Por que muitos dizem que ele é ineficiente?
O que faz exatamente o algoritmo de ordenação bogosort?
Por que muitos dizem que ele é ineficiente?
O bogosort é um algoritmo que consiste no seguinte:
O array está ordenado?
Se sim, então excelente, fim do algoritmo.
Se não, embaralhe ele aleatoriamente e volte para o começo.
Este algoritmo é extremamente simples, mas também extremamente ineficiente. E consiste basicamente em embaralhar o array tantas vezes quanto forem necessárias até que por pura sorte e acaso, a ordenação aleatória dos elementos acabe sendo a correta. Mesmo ordenações parcialmente ordenadas ou quase ordenadas são completamente e cegamente descartadas em sua totalidade e de nada acabam ajudando.
O resultado é que quanto maior o array, maior é a quantidade de sorte que é preciso se ter para que a ordenação correta apareça por capricho do acaso. A rigor, no pior caso, um número infinito de tentativas seria necessário e a ordenação correta nunca surgiria (o que tende a acontecer se o gerador aleatório usado para embaralhar estiver viciado de alguma forma). Considerando que não haja vícios estatísticos no gerador de ordenações aleatórias, a probabilidade de uma dada ordenação qualquer gerada aleatoriamente ser correta é de (o que dá uma complexidade de tempo do caso médio de , onde é o número de elementos do array.
Quanto que é , a probabilidade de acerto? Bem, veja na seguinte tabela:
n n! Probabilidade
-------------------------------------------------------------
1 1 100,00000000%
2 2 50,00000000%
3 6 16,66666666%
4 24 4,16666666%
5 120 0,83333333%
6 720 0,13888888%
7 5040 0,01984126%
8 40320 0,00248015%
9 362880 0,00027557%
10 3628800 0,00002755%
15 1307674368000 0,000000000007647%
20 2432902008176640000 0,000000000000000000411%
25 15511210043330985984000000 0,(25 zeros)6447%
30 2,65 * (10^32) 0,(32 zeros)3699%
Ou seja, a probabilidade de a sorte e o acaso escolher a ordenação correta piora muito rapidamente cada vez que um elemento é adicionado. De fato, a taxa de piora é mais do que exponencial.
Quanto tempo isso demoraria? Bem, vamos supor que a sua máquina é super rápida e é capaz de embaralhar e testar se um dado array está ordenado, 1 bilhão de vezes por segundo (o que não é tão verdade, pois arrays maiores tendem a demorar mais para embaralhar e testar do que os menores, mas para manter um pouquinho de otimismo, vamos supor que os arrays grandes demoram o mesmo para serem embaralhados e testados do que os pequenos). Então, quanto tempo demoraria em média*?
n Tempo
-------------------------------
1 1 nanosegundo
2 1 nanosegundo
3 3 nanosegundos
4 12 nanosegundos
5 60 nanosegundos
6 360 nanosegundos
7 2,5 microsegundos
8 20 microsegundos
9 182 microsegundos
10 1,82 milissegundos
15 10 minutos e 54 segundos
20 38 anos e 7 meses
25 245,7 milhões de anos
30 4,2 quatrilhões de anos
4,2 quatrilhões de anos para ordenar um array de 30 elementos mesmo fazendo 1 bilhão de testes por segundo!? Acho que está claro porque o bogosort é um algoritmo ineficiente!
E para ver a escala da ineficiência, basta ver que para ordenar 15 elementos, ele levaria em média 10 minutos e 54 segundos (algo que qualquer criança faria em poucos segundos), mas basta dobrar o número de elementos e o tempo pula para quatrilhões de anos. Isso ocorre porque o crescimento de tempo é pior do que exponencial no tamanho da entrada. E olha que estamos usando uma super-máquina que consegue embaralhar o array e verificar se ele está ordenado um bilhão de vezes por segundo!
* - Para fazer esse cálculo, eu parti do pressuposto de que uma mesma ordenação nunca é sorteada duas vezes, e portanto, em média, após testar metade das ordenações possíveis, a chance de o algoritmo esbarrar na ordenação correta seria de 50%. Ocorre que o bogosort padrão não conta com essa restrição, logo o tempo médio demorado seria na verdade ainda pior do que isso.
O Bogosort, conhecido como stupid sort, permutation sort, slowsort, shotgun sort, monkey sort, é usado com propósito educacional nas disciplinas de análise e complexidade de algoritmos com o objetivo de ensinar aos alunos um paradigma conhecido como “generate and test” que nada mais é: faça enquanto não chegar ao resultado final. Sua complexidade é de O(n!)
Basicamente o Bogosort funciona com a premissa: “embaralhe novamente o vetor (shuffle) enquanto ele não estiver ordenado”.
Portanto, imagine a ineficiência ao tentar realizar essa técnica em vetores com muitas posições? Sim, ineficiente porque faria a permutação aleatória de elementos enquanto não estivesse 100% ordenado.
Um exemplo de implementação do Bogosort em C:
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
void embaralhar(int *pV, int n);
bool verificarOrdenacao(int *pV, int n);
void aplicarBogosort(int *pV, int n);
int main(){
int numeros[] = { 33, 10, 50, -4, 2, 99, -1};
int i;
aplicarBogosort(numeros, 7);
for (i=0; i < 7; i++)
printf("\n%d ", numeros[i]);
return EXIT_SUCCESS;
}
bool verificarOrdenacao(int *pV, int n){
while (--n >= 1) {
if (pV[n] < pV[n-1])
return false;
}
return true;
}
void embaralhar(int *pV, int n){
int i, t, r;
for(i=0; i < n; i++) {
t = pV[i];
r = rand() % n;
pV[i] = pV[r];
pV[r] = t;
}
}
void aplicarBogosort(int *pV, int n){
while (!verificarOrdenacao(pV, n)) embaralhar(pV, n);
}
Como contribuição do membro do SO PT @Guilherme Lima, segue o vídeo demonstrando como ele funciona em termos visuais, para facilitar a abstração):https://www.youtube.com/watch?v=DaPJkYo2quc