Pantera Cor de Rosa

Este é o blog de Juliana Carpes Imperial, mais conhecida pelos desconhecidos como a Pantera Cor de Rosa por volta e meia ir correr toda de rosa.

quarta-feira, agosto 31, 2011

Bozosort


Já que Bozo tem sido um assunto frequente aqui no blog, que tal falar de um método de ordenação que leva seu nome?

Quando ouvi falar deste método pela primeira vez durante o mestrado, achei que era palhaçada de um amigo meu. Afinal, ele sempre se referia a palavra bozo para falar de algo bobo. Na época, não sabia que em inglês a palavra significava isso. Só que isso não foi invenção dele. De fato, este "método" existe.

Bozosort é 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. Outros nomes são Bogosort (de bogus), Blortsort e Vainasort ou Estoucomsort.

Algoriticamente falando, tem-se que:
função bozosort(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.

Bozosort não é um algoritmo de ordenação estável. Em C, sua implementação fica assim:

void Bozosort(int size, int* array)
{
   int i, j;
   while (true)
   {
      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];     
      }
   }
}
Já um fluxograma do algoritmo pode ser visto abaixo.


Fonte: Wikipédia.

É ou não algo típico do Bozo?

Marcadores:

0 Comments:

Postar um comentário

Links to this post:

Criar um link

<< Home

Free counter and stats for your website on www.motigo.com