7

O que faz exatamente o algoritmo de ordenação bogosort?

Por que muitos dizem que ele é ineficiente?

3
  • 4
    Um video legal de como ele funciona: youtube.com/watch?v=DaPJkYo2quc Commented 26/06/2016 às 14:08
  • Muito bom Guilherme, vou editar a resposta acrescentando sua contribuição.
    – Mateus
    Commented 26/06/2016 às 14:09
  • 2
    Algorítimo também conhecido como "Estou com sorte" rs Commented 26/06/2016 às 20:45

2 Respostas 2

9

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 (1 / n!) (o que dá uma complexidade de tempo do caso médio de O(n!), onde n é o número de elementos do array.

Quanto que é (1 / n!), 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.

6

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

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .