Bozo Sort

Aviso

O Bozo sort é intencionalmente impraticável e aparece aqui apenas para análise.

O Bozo sort escolhe repetidamente duas posições de modo uniforme e aleatório, troca seus valores e para quando a sequência está ordenada.

Ao contrário do bogo sort, uma etapa não amostra uma permutação uniforme e independente. Ela realiza um passeio aleatório pelas permutações. O tempo esperado para atingir a ordenação depende da regra exata — por exemplo, se é permitido escolher duas vezes a mesma posição — e não deve ser declarado como O(n!) sem que esse modelo seja derivado. Não existe um limite determinístico finito para a terminação no pior caso.

A lição é metodológica: uma afirmação de complexidade aleatorizada exige um processo aleatório definido, um custo por etapa e a identificação do caso relatado.