Bogosort
Temos trabalhado com listas ordenadas para diversos problemas. Já utilizámos funções internas para ordenar alguns arrays. No entanto, não é óbvio como essas funções realmente funcionam por detrás dos bastidores. Neste capítulo, vamos falar sobre alguns dos algoritmos de ordenação mais populares, utilizados em diferentes contextos — dependendo da aplicação.
O primeiro algoritmo a discutir é o mais absurdo de todos os algoritmos de ordenação. É chamado de Bogosort. Não é utilizado em aplicação nenhuma no mundo real, e vais perceber rapidamente porquê.
Dado
n números, o algoritmo funciona baralhando aleatoriamente esses números e verificando depois se a lista resultante está ordenada:from random import shuffle
a = [3, 1, -2, 5, 6] # Números iniciais
while True: # Permaneça em loop até que o array esteja ordenado
is_sorted = True
for i in range(1, len(a)): # Um loop para verificar se o array está ordenado
if a[i] < a[i-1]: # Se encontrarmos um elemento menor que o anterior => não está ordenado
is_sorted = False # Definimos a variável para False e interrompemos o loop
break
if is_sorted: # Se o array estiver ordenado => interrompa o loop infinito
break
else: # Caso contrário, embaralhe a lista novamente
shuffle(a)
print(a) # Por fim, imprima a lista resultanteEste algoritmo é aleatório e pode demorar infinitamente a concluir. Portanto, seria realmente perigoso e ineficiente utilizá-lo em aplicações de produção.
És desafiado a calcular quantas iterações seriam necessárias para o algoritmo Bogosort encontrar finalmente uma solução.
Entrada
A primeira linha da entrada contém um único inteiro
n (1 ≤ n ≤ ).A linha seguinte contém
n inteiros separados por espaço ( ≤ ≤ ).Saída
O programa deve imprimir o número de iterações que o algoritmo Bogosort levaria para concluir a pesquisa.
Exemplos
Exemplo de Entrada | Exemplo de Saída |
5
5 -1 2 3 9 | 10 |
Explicação
O número 10 é completamente aleatório — podia ter sido 2 ou 200. É possível obter valores diferentes ao executar o mesmo programa com a mesma entrada várias vezes.
Outros Algoritmos de Ordenação Ridículos
Podes encontrar outros algoritmos de ordenação visualizados no vídeo do YouTube abaixo, criado por Ardens.
Constraints
Time limit: 60 seconds
Memory limit: 512 MB
Output limit: 1 MB