Bogosort
Nous avons déjà travaillé avec des listes triées pour de nombreux problèmes. Nous avons utilisé des fonctions intégrées pour trier certains tableaux, mais il n’est pas toujours évident de comprendre la logique derrière ces fonctions. Dans ce chapitre, nous allons examiner quelques-uns des algorithmes de tri les plus populaires. Ils sont utilisés dans différents contextes, selon l’application.
Le premier algorithme que nous allons aborder est le plus absurde de tous. Il s’appelle Bogosort. Il n’est utilisé dans aucune application concrète, et vous comprendrez vite pourquoi.
Étant donné
n nombres, l’algorithme consiste à mélanger aléatoirement ces nombres puis à vérifier si la liste obtenue est triée :from random import shuffle
a = [3, 1, -2, 5, 6] # Nombres initiaux
while True: # Boucle jusqu'à ce que le tableau soit trié
is_sorted = True
for i in range(1, len(a)): # Boucle pour vérifier si le tableau est trié
if a[i] < a[i-1]: # Si on trouve un élément plus petit que le précédent => ce n'est pas trié
is_sorted = False # On passe la variable à False et on interrompt la boucle
break
if is_sorted: # Si le tableau est trié => on arrête la boucle infinie
break
else: # Sinon, on mélange à nouveau la liste
shuffle(a)
print(a) # Enfin, on affiche la liste résultanteCet algorithme est aléatoire et peut théoriquement passer un temps infini avant de se terminer. À cause de cela, il serait très risqué et inefficace de l’utiliser dans des applications de production.
On vous demande de calculer le nombre d’itérations nécessaires pour que l’algorithme Bogosort finisse par trouver une solution.
Entrée
La première ligne de l’entrée contient un entier
n (1 ≤ n ≤ ).La ligne suivante contient
n entiers séparés par un espace ( ≤ ≤ ).Sortie
Votre programme doit afficher le nombre d’itérations nécessaires au Bogosort pour aboutir à un tri correct.
Exemples
Entrée | Sortie |
5
5 -1 2 3 9 | 10 |
Explication
Le nombre 10 est complètement aléatoire : il aurait pu être égal à 2, ou à 200. Vous pourriez obtenir des nombres différents à chaque exécution pour les mêmes données d’entrée.
Autres algorithmes de tri absurdes
Vous pouvez découvrir d’autres algorithmes de tri fantaisistes dans la vidéo YouTube ci-dessous créée par Ardens.
Constraints
Time limit: 60 seconds
Memory limit: 512 MB
Output limit: 1 MB