Bogo Sort

Aviso

O Bogo sort é um exemplo didático, não um algoritmo prático de ordenação.

O Bogo sort embaralha uniformemente uma sequência até que ela esteja ordenada. Para n elementos distintos e permutações uniformes e independentes, um embaralhamento produz a ordem correta com probabilidade 1/n!; o número esperado de tentativas é n!. Cada embaralhamento e verificação custa Θ(n); assim, uma implementação direta tem tempo esperado Θ(n · n!).

Não existe um limite determinístico finito para o tempo de execução no pior caso, pois as tentativas aleatórias podem continuar indefinidamente. Valores repetidos aumentam o número de permutações ordenadas e alteram a probabilidade. O algoritmo é útil para discutir terminação aleatorizada e a diferença entre análises de caso esperado e de pior caso.