Bogosort
Hemos trabajado con listas ordenadas para muchos problemas diferentes. Hemos usado funciones integradas para ordenar algunos arreglos. Sin embargo, no siempre es obvio cómo funcionan esas funciones internamente. En este capítulo, hablaremos de algunos de los algoritmos de ordenamiento más populares que se utilizan en distintos contextos, dependiendo de la aplicación.
El primer algoritmo que veremos es el más descabellado de todos los algoritmos de ordenamiento. Se llama Bogosort. No se utiliza en aplicaciones del mundo real, y pronto verás por qué.
Dado
n números, el algoritmo funciona barajando aleatoriamente esos números y luego verificando si la lista resultante está ordenada:from random import shuffle
a = [3, 1, -2, 5, 6] # Números iniciales
while True: # Bucle hasta que la lista esté ordenada
is_sorted = True
for i in range(1, len(a)): # Un bucle para verificar si la lista está ordenada
if a[i] < a[i-1]: # Si encontramos un elemento menor que el anterior => no está ordenada
is_sorted = False # Ponemos la variable en False y detenemos el bucle
break
if is_sorted: # Si la lista está ordenada => detenemos el bucle infinito
break
else: # De lo contrario, barajamos la lista otra vez
shuffle(a)
print(a) # Finalmente imprimimos la lista resultanteEste algoritmo es completamente aleatorio y puede tardar infinitamente en completarse. Por lo tanto, sería muy peligroso e ineficiente utilizar algo así en entornos de producción.
Se te solicita calcular el número de iteraciones que tomaría un algoritmo Bogosort para finalmente encontrar una solución.
Entrada
La primera línea de la entrada contiene un solo entero
n (1 ≤ n ≤ ).La siguiente línea contiene
n números enteros separados por espacio ( ≤ ≤ ).Salida
El programa debe imprimir el número de iteraciones que tardará el algoritmo Bogosort en completar la búsqueda.
Ejemplos
Entrada | Salida |
5
5 -1 2 3 9 | 10 |
Explicación
El número 10 es un número aleatorio: podría haber sido 2 o 200. Podrías obtener resultados distintos al ejecutar el mismo programa con la misma entrada varias veces.
Otros Algoritmos de Ordenamiento Ridículos
Puedes encontrar otros algoritmos de ordenamiento visualizados en el siguiente video de YouTube creado por Ardens.
Constraints
Time limit: 60 seconds
Memory limit: 512 MB
Output limit: 1 MB