¶ Exercice 1 - Fonction de vérification
Les fonctions de cet exercice sont à écrire dans un fichier nommé verif_tris.py
Question 1 - Écrire une fonction est_triee qui prend en paramètre une liste d'entiers. Cette fonction renvoie True si la liste passée en paramètre est triée dans l'ordre croissant, False sinon.
def est_triee(liste:list) -> bool :
pass
Question 2 - Écrire 2 doctests pour vérifier votre fonction. Ces deux doctests permettront de tester les deux résultats possibles de la fonction.
¶ Exercice 2 - Le tri par sélection
Les fonctions de cet exercice sont à écrire dans un fichier nommé
tris.py
Question 1 - Écrire une fonction selection_minimum. Cette fonction prend en paramètre une liste d'entiers et deux entiers a et b. Elle renvoie l'indice de la plus petite valeur du tableau compris entre les indices a et b.
def selection_minimum(liste:list,a:int, b:int) -> int :
pass
Question 2 - Écrire une fonction echanger. Cette fonction prend en paramètre une liste et deux entiers a et b. Elle effectue une permutation des valeurs situées aux indices passés en paramètre.
def echanger(liste:list, a:int, b:int) -> None :
pass
Question 3 - Écrire une version 1 de la fonction tri_selection. Cette fonction prend en paramètre une liste et trie cette liste dans l'ordre croissant sur place. Elle réutilise les 2 fonctions précédentes.
def tri_par_selection_1(liste:list) -> None :
pass
Question 4 - Écrire une version 2 de la fonction tri_selection. Cette fonction prend en paramètre une liste et trie cette liste dans l'ordre croissant sur place, sans utiliser les fonctions select_minimum et echanger.
def tri_par_selection_2(liste:list) -> None :
pass
Question 5 - Tester vos 2 fonctions en ajoutant 2 doctests et en utilisant la fonction est_triee.
¶ Exercice 3 - Le tri par insertion
Les fonctions de cet exercice sont à écrire dans le même fichier nommé
tris.py
Question 1 - Écrire une fonction tri_insertion. Cette fonction prend en paramètre une liste et trie cette liste dans l'ordre croissant sur place.
def tri_par_insertion(liste:list) -> None :
pass
Question 2 - Tester cette fonction en ajoutant 2 doctests et en utilisant la fonction est_triee.
¶ Exercice 4 - Le tri à bulles
Les fonctions de cet exercice sont à écrire dans le même fichier nommé
tris.py
Le principe du tri à bulles (bubble sort) est de comparer deux à deux les éléments et consécutifs d'une liste et d'effecteur une permutation si > . On continue de trier jusqu'à ce qu'il n'y ait plus de permutation.
Question 1 - Écrire une fonction tri_bulles. Cette fonction prend en paramètre une liste et trie cette liste dans l'ordre croissant sur place.
def tri_bulles(liste:list) -> None :
pass
¶ Exercice 5 - Analyse du temps d'exécution des tris
Dans cette partie, on s'intéresse à l'efficacité des nos fonctions en mesurant le temps d'exécution de chacun des algorithmes. Pour cela, nous allons utiliser le module timeit.
L'objectif est de générer des courbes qui affichent le temps d'exécution en fonction de la taille des listes à trier et de l'état des listes.
¶ Le module timeit
Le module timeit de Python permet de prendre une mesure du temps d'exécution d'une fonction, en secondes.
from timeit import timeit
Ce module fournit une fonction timeit qui accepte en entrée trois paramètres :
-
setuppermet de préciser àtimeitles modules à charger pour permettre l'exécution correcte de la fonction (y compris le module qui contient la fonction à mesurer), -
stmt– pour statement, est l'appel de la fonction qui sera mesurée (donc avec ses paramètres), -
numberest le nombre de fois où l'instructionstmtsera exécutée. Le temps mesuré sera le temps cumulé pour toutes ces exécutions.
Remarquez que le code Python des deux paramètres setup et stmt sont donnés sous forme d'une chaîne de caractères. Par exemple, après avoir importé le module timeit :
imports = "from .... import ...."
program = "ma_fonction(4, 12)"
temps = timeit(setup=imports, stmt=program, number=100)
Le résultat obtenu représente le temps total mis pour exécuter 100 fois ma_fonction.
¶ Questions
Question 1 - Créer un nouveau fichier nommé analyse_tri.py.
Question 2 - Écrire la fonction cree_liste_croissante. Cette fonction prend en paramètre un entier correspondant au nombre d'éléments dans la liste. Elle retourne une liste croissante avec les entiers de 0 à n.
def cree_liste_croissante(n:int):
pass
Question 3 - Écrire la fonction cree_liste_decroissante. Cette fonction prend en paramètre un entier correspondant au nombre d'éléments dans la liste. Elle retourne une liste décroissant avec les entiers de n à 0.
def cree_liste_decroissante(n):
pass
Question 4 - Écrire la fonction cree_liste_melange. Cette fonction prend en paramètre un entier correspondant au nombre d'éléments dans la liste. Elle retourne une liste avec n entiers choisi aléatoirement entre 0 et n.
def cree_liste_melangee(n):
pass
Ces trois fonctions vont permettre de tester nos algorithmes selon différentes situations : le pire des cas, le meilleur des cas et le cas moyen.
¶ Le cas moyen : une liste mélangée
Question 3 - Écrire une fonction analyse_tri_selection. Elle retourne une liste composée des différents temps d'exécution de la fonction selon la taille de la liste.
Elle prend en paramètre un nombre entier correspondant à la taille maximale d'une liste Cela veut dire qu'on testera la fonction avec un tableau de taille 1, 2, 3... jusqu'à la taille maximale passée en paramètre. Chaque temps d'exécution sera stocké dans une liste.
Quelques précisions :
- On définira le nombre de répétitions du module
timeità 10. - Pour l'instant, on utilisera une liste mélangée.
- La ligne de code pour les imports du module
timeitsera :
def analyse_tri_selection(taille_liste) -> list :
imports = "from tri import tri_selection; from __main__ import cree_liste_melangee; liste = cree_liste_melangee("+str(n)+")"
Question 3 - Écrire une fonction analyse_tri_insertion. Cette fonction possède le même comportement que la fonction de la question précédente.
- On utilisera également une liste mélangée.
Question 4 - Les deux fonctions précédentes génèrent une liste de nombres correspondant à la durée d'exécution des algorithmes de tri selon une certaine taille de liste.
On peut donc comparer l'efficacité des deux algorithmes de tri en dessinant un graphique grâce au module pylab.
Pour dessiner une courbe, il faut :
- Définir la taille maximale des listes utilisées.
- Récupérer le résultat de chaque fonction précédente.
- Utiliser la fonction
plotdu modulepylabpour dessiner les courbes.
TAILLE_MAX_LISTE = 1000
y1 = analyse_tri_selection(TAILLE_MAX_LISTE)
y2 = analyse_tri_insertion(TAILLE_MAX_LISTE)
pylab.plot(y1, color='r', label='Tri par selection')
pylab.plot(y2, color='b', label='Tri par insertion')
On peut ajouter les lignes suivantes pour ajouter la légende de chaque courbe.
pylab.title('Analyse du temps d\'exécution des algorithmes de tri')
pylab.suptitle('Cas moyen : liste mélangées)
pylab.xlabel('Taille des listes')
pylab.ylabel('Temps en secondes')
pylab.legend()
Enfin, la ligne suivant permet d'affiche le graphique.
pylab.show()
¶ Tester tous les cas : pire, meilleur, moyen
Question 5 - Modifier les fonctions analyse_tri_selection et analyse_tri_insertion afin d'ajouter un paramètre etat_liste. Ce paramètre permet d'indiquer l'état de la liste qu'il faut générer et donc trier. 3 états sont possibles, qui feront appel aux différentes fonctions de la question 2.
Les 3 états possibles sont :
melangeecroissantedecroissante
def analyse_tri_insertion(taille_liste, etat_liste) -> list :
pass
On pourra ainsi lancer notre programme grâce au code suivante :
TAILLE_MAX_LISTE = 1000
ETAT_LISTE = 'decroissante' # On peut changer l'état des listes ici !
y1 = analyse_tri_selection(TAILLE_MAX_LISTE, ETAT_LISTE)
y2 = analyse_tri_insertion(TAILLE_MAX_LISTE, ETAT_LISTE)
pylab.plot(y1, color='r', label='Tri par selection')
pylab.plot(y2, color='b', label='Tri par insertion')
pylab.title('Analyse du temps d\'exécution des algorithmes de tri')
pylab.suptitle('Liste ' + ETAT_LISTE)
pylab.xlabel('Taille des listes')
pylab.ylabel('Temps en secondes')
pylab.legend()
pylab.show()