Bogosort
Abbiamo già lavorato con liste ordinate per molti tipi di problemi. Abbiamo utilizzato funzioni integrate per ordinare alcuni array; tuttavia, non è per niente ovvio come queste funzioni funzionino “dietro le quinte”. In questo capitolo, analizzeremo alcuni degli algoritmi di ordinamento più diffusi, utilizzati in vari contesti a seconda delle necessità.
Il primo algoritmo che tratteremo è il più assurdo di tutti gli algoritmi di ordinamento. Si chiama Bogosort. Non viene mai utilizzato in applicazioni reali e presto capirete il perché.
Dato
n numeri, l’algoritmo consiste nel mescolare casualmente quegli stessi numeri e poi verificare se la lista ottenuta è ordinata:from random import shuffle
a = [3, 1, -2, 5, 6] # Numeri iniziali
while True: # Ciclo fino a quando l'array non è ordinato
is_sorted = True
for i in range(1, len(a)): # Un ciclo per verificare se l'array è ordinato
if a[i] < a[i-1]: # Se troviamo un elemento più piccolo del precedente => l'array non è ordinato
is_sorted = False # Impostiamo la variabile a False e interrompiamo il ciclo
break
if is_sorted: # Se l'array è ordinato => interrompi il ciclo infinito
break
else: # Altrimenti rimescola di nuovo la lista
shuffle(a)
print(a) # Alla fine stampa la lista risultanteQuesto algoritmo si basa sulla casualità e può richiedere un tempo potenzialmente infinito per terminare. Di conseguenza, sarebbe davvero rischioso e inefficiente adoperarlo in applicazioni di produzione.
Vi si chiede di calcolare il numero di iterazioni necessarie affinché l’algoritmo Bogosort trovi finalmente una soluzione.
Input
La prima riga dell'input contiene un singolo intero
n (1 ≤ n ≤ ).La riga successiva contiene
n interi separati da uno spazio ( ≤ ≤ ).Output
Il programma deve stampare il numero di iterazioni necessarie perché l’algoritmo Bogosort completi la ricerca.
Esempi
Ingresso | Uscita |
5
5 -1 2 3 9 | 10 |
Spiegazione
Il valore 10 è un numero casuale: avrebbe potuto essere 2, o 200. Potresti ottenere numeri diversi eseguendo lo stesso programma più volte con il medesimo input.
Altri Algoritmi di Ordinamento Ridicoli
Puoi trovare altri algoritmi di ordinamento visualizzati nel video YouTube qui sotto, realizzato da Ardens.
Constraints
Time limit: 60 seconds
Memory limit: 512 MB
Output limit: 1 MB