Trions pour l’avenir …

… ou pour une meilleure algorithmique !

Tout le monde doit avoir programmé les tris :

  • par sélection,
  • par insertion,
  • à bulles,

en se basant sur le canevas de la semaine dernière.

On commence par corriger ensemble le tri par sélection que beaucoup avaient fini la semaine dernière et dont on avait proposé un pseudo-code :

from random import randint
 
liste=[]
for i in range(8):
    liste.append(randint(1,101))
 
print(liste)

# tri par sélection du minimum

for i_depart in range(0,7):
    # initialisation
    i_min = i_depart

    # recherche du minimum
    for i in range(i_depart + 1, 8):
        if liste[i] < liste[i_min]:
            i_min = i

    # interversion
    liste[i_depart], liste[i_min] = liste[i_min], liste[i_depart]
    print(liste)

qui donne par exemple :

[62, 84, 15, 52, 58, 35, 56, 7]
[7, 84, 15, 52, 58, 35, 56, 62]
[7, 15, 84, 52, 58, 35, 56, 62]
[7, 15, 35, 52, 58, 84, 56, 62]
[7, 15, 35, 52, 58, 84, 56, 62]
[7, 15, 35, 52, 56, 84, 58, 62]
[7, 15, 35, 52, 56, 58, 84, 62]
[7, 15, 35, 52, 56, 58, 62, 84]
>>> 

Romain (bravo !) propose cette comparaison graphique du temps d’exécution des tris :

TR - 2020_01_15 - Temps de traitement, Algorithmique .jpg

L’image ci-dessus a été obtenue (par Romain) avec des listes de tailles n allant de 1 à 450 et on a trié ces listes avec chacun des algorithmes et chronométré le temps en secondes. Repère :

  • de 1 à 450 pour la taille de la liste triée en abscisses,
  • de zéro à 0,5 secondes en ordonnées.

J’ai utilisé ses codes pour générer l’animation ci-dessous.

TR - 2020_01_15 - Temps de traitement Algorithmique

Repère :

  • de 1 à 150 pour la taille de la liste triée en abscisses,
  • de zéro à 0,3 secondes en ordonnées.

Fini ? Déjà fait ? Alors on continue le …

Travail sur les mini-projets et le site web qui les présente.

3 réflexions au sujet de « Trions pour l’avenir … »

  1. Bonjour ! Pour notre mini-projet de Puissance 4 dans le shell, je suis toujours bloqué par rapport à la montée des pièces et à la vérification de s’il y a une pièce déjà placée en dessous dans le jeu… si vous pouviez m’apporte un peu d’aide, ça ne serait pas de refus, merci !

N'hésitez-pas à poser une question, ou faire avancer le schmilblick

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l’aide de votre compte WordPress.com. Déconnexion /  Changer )

Photo Google

Vous commentez à l’aide de votre compte Google. Déconnexion /  Changer )

Image Twitter

Vous commentez à l’aide de votre compte Twitter. Déconnexion /  Changer )

Photo Facebook

Vous commentez à l’aide de votre compte Facebook. Déconnexion /  Changer )

Connexion à %s

Ce site utilise Akismet pour réduire les indésirables. En savoir plus sur la façon dont les données de vos commentaires sont traitées.