Bogosort - Bogosort

Bogosort
Classe	Ordenação
Estrutura de dados	Variedade
Desempenho de pior caso	Ilimitado (versão aleatória), O (( n +1)!) (Versão determinística)
Melhor caso de desempenho	O ( n )
Desempenho médio	O (( n +1)!)
Pior caso de complexidade de espaço	O ( 1 )

Na ciência da computação , bogosort (também conhecido como classificação de permutação , classificação estúpida ou classificação lenta ) é um algoritmo de classificação altamente ineficiente baseado no paradigma de geração e teste . A função gera sucessivamente permutações de sua entrada até encontrar uma que seja classificada. Não é útil para classificação, mas pode ser usado para fins educacionais, para contrastá-lo com algoritmos mais eficientes.

Duas versões deste exist algoritmo: Uma versão determinista que enumera todas as permutações até que ela atinge um ordenado um, e um randomizado versão que permuta aleatoriamente sua entrada. Uma analogia para o funcionamento da última versão é classificar um baralho jogando o baralho no ar, pegando as cartas aleatoriamente e repetindo o processo até que o baralho seja classificado. Seu nome é uma mala de viagem das palavras bogus e sort .

Descrição do algoritmo

A seguir está uma descrição do algoritmo aleatório em pseudocódigo :

while not isInOrder(deck):
    shuffle(deck)

Aqui está o pseudocódigo acima reescrito em Python 3 :

from random import shuffle

def is_sorted(data) -> bool:
    """Determine whether the data is sorted."""
    return all(a <= b for a, b in zip(data, data[1:]))

def bogosort(data) -> list:
    """Shuffle data until sorted."""
    while not is_sorted(data):
        shuffle(data)
    return data

Este código assume que os dados são um tipo de dados simples e mutável - como o integrado do Python - listcujos elementos podem ser comparados sem problemas.

Tempo de execução e rescisão

Tempo de execução experimental do bogosort

Se todos os elementos a serem classificados são distintos, o número esperado de comparações realizadas no caso médio por bogosort aleatório é assintoticamente equivalente a $(e - 1) n!$ , e o número esperado de trocas no caso médio é igual a $(n - 1) n!$ . O número esperado de trocas cresce mais rápido do que o número esperado de comparações, porque se os elementos não estiverem em ordem, isso geralmente será descoberto após apenas algumas comparações, não importa quantos elementos existam; mas o trabalho de embaralhar a coleção é proporcional ao seu tamanho. No pior caso, o número de comparações e trocas é ilimitado, pela mesma razão que uma moeda lançada pode dar cara qualquer número de vezes consecutivas.

O melhor caso ocorre se a lista fornecida já estiver classificada; neste caso, o número esperado de comparações é $n - 1$ , e nenhuma troca é realizada.

Para qualquer coleção de tamanho fixo, o tempo de execução esperado do algoritmo é finito pela mesma razão que o teorema do macaco infinito mantém: há alguma probabilidade de obter a permutação correta, portanto, dado um número ilimitado de tentativas, quase certamente acabará ser escolhido.

Algoritmos relacionados

Gorosort: é um algoritmo de classificação introduzido no 2011 Google Code Jam . Enquanto a lista não estiver em ordem, um subconjunto de todos os elementos é permutado aleatoriamente. Se esse subconjunto for escolhido de maneira ideal cada vez que isso for executado, o valor esperado do número total de vezes que essa operação precisa ser feita é igual ao número de elementos colocados incorretamente.
Bogobogosort: é um algoritmo projetado para não ter sucesso antes da morte térmica do universo em qualquer lista considerável. Ele funciona chamando a si mesmo recursivamente com cópias cada vez menores do início da lista para ver se elas estão classificadas. O caso base é um único elemento, que é sempre classificado. Para outros casos, ele compara o último elemento com o elemento máximo dos elementos anteriores na lista. Se o último elemento for maior ou igual, ele verifica se a ordem da cópia corresponde à versão anterior e, em caso afirmativo, retorna. Caso contrário, ele reorganiza a cópia atual da lista e reinicia sua verificação recursiva.
Bozosort: é outro algoritmo de classificação baseado em números aleatórios. Se a lista não estiver em ordem, ele seleciona dois itens aleatoriamente e os troca e, em seguida, verifica se a lista está classificada. A análise do tempo de execução de um bozosort é mais difícil, mas algumas estimativas são encontradas na análise de H. Gruber de algoritmos de classificação aleatória "perversamente horríveis". $O (n!)$ É considerado o caso médio esperado.
Worstsort: é um algoritmo de classificação pessimal cuja conclusão é garantida em um tempo finito; entretanto, sua eficiência pode ser arbitrariamente ruim, dependendo de sua configuração. O $pior$ algoritmo de classificação é baseado em um algoritmo de classificação ruim, $badsort$ . O algoritmo badsort aceita dois parâmetros: $L$ , que é a lista a ser classificada e $k$ , que é uma profundidade de recursão. No nível de recursão $k = 0$ , $badsort$ apenas usa um algoritmo de classificação comum, como o bubblesort , para classificar suas entradas e retornar a lista classificada. Ou seja, $badsort (L, 0) = bubblesort (L)$ . Portanto, a complexidade de tempo de badsort é $O (n 2)$ se $k = 0$ . No entanto, para qualquer $k > 0$ , $badsort (G, k)$ gera primeiro $P$ , a lista de todas as permutações de $L$ . Em seguida, $badsort$ calcula $badsort (P, k - 1)$ e retorna o primeiro elemento do $P$ classificado . Para tornar a $pior classificação$ verdadeiramente pessimal, $k$ pode ser atribuído ao valor de uma função crescente computável, como (por exemplo, $f$ $($ $n$ $) =$ $A$ $($ $n$ $,$ $n$ $)$ , onde $A$ é a função de Ackermann ). Ergo, para classificar uma lista arbitrariamente mal, você deve executar $worstsort ($ $L$ $,$ $f$ $) = badsort ($ $L$ $,$ $f$ $(comprimento ($ $L$ $)))$ , onde $comprimento ($ $L$ $)$ é o número de elementos em $L$ . O algoritmo resultante tem complexidade , onde = fatorial de $n$ iterado $m$ vezes. Este algoritmo pode ser tão ineficiente quanto desejarmos, escolhendo uma função $f de$ crescimento rápido o suficiente . ${\ displaystyle f \ colon \ mathbb {N} \ to \ mathbb {N}}$ ${\ textstyle \ Omega \ left (\ left (n! ^ {(f (n))} \ right) ^ {2} \ right)}$ ${\ displaystyle n! ^ {(m)} = (\ dotso ((n!)!)! \ dotso)!}$
Slowsort: Um algoritmo de classificação diferente e bem-humorado que emprega uma estratégia equivocada de dividir e conquistar para alcançar uma complexidade massiva.

Quantum bogosort

Quantum bogosort é um algoritmo de classificação hipotético baseado em bogosort, criado como uma piada interna entre os cientistas da computação. O algoritmo gera uma permutação aleatória de sua entrada usando uma fonte quântica de entropia, verifica se a lista está classificada e, se não estiver, destrói o universo. Supondo que a interpretação de muitos mundos seja verdadeira, o uso desse algoritmo resultará em um universo sobrevivente onde a entrada foi classificada com sucesso em tempo $O (n)$ .

Veja também

Notas

Referências

links externos

BogoSort no WikiWikiWeb
Algoritmos de classificação ineficientes
Bogosort : uma implementação que roda em sistemas do tipo Unix, semelhante ao programa de classificação padrão .
Bogosort e jmmcg :: bogosort : Implementações C ++ simples, porém perversas, do algoritmo bogosort.
Pacote Bogosort NPM : implementação de bogosort para o ecossistema Node.js.
Max Sherman Bogo-sort é meio lento , junho de 2013

Languages

In other projects