-0
0
c
:J
0
li)
..--t
0
N
@
.......
J::
O'l
·;::::
>0.
0
u
Chapitre l 0 • Travaux pratiques
242
l 0.7 MÉTHODES DE TRI
Énoncé
a) Le problème
Le but de ce TP est de comparer le temps d'exécution de plusieurs méthodes de tri
d'une liste de nombres par ordre croissant. Parmi ces méthodes, on peut distinguer:
• Le tri par sélection : on recherche le plus petit élément de la liste, que l'on place
en première position, puis le plus petit de la liste formée par les autres éléments,
que l'on place en seconde position, etc.
• Le tri à bulles : pour une liste L, on compare tous les éléments successifs L[k],
L[k+ 1]. Lorsque deux éléments successifs ne sont pas rangés par ordre croissant,
on les intervertit. Après un parcours complet de la liste, on recommence, et ainsi
de suite jusqu'à ce qu'au cours d'un parcours, aucune interversion n'ai lieu.
• Le tri rapide : pour une liste Layant au moins deux éléments, on retire le premier
élément x de cette liste puis on crée deux listes, celle des éléments inférieurs ou
égaux à x (liste 1) et celle des éléments supérieurs à x (liste 2). On fait de même
avec ces nouvelles listes et ainsi de suite (il s'agit d'un algorithme récursif). On
obtient la liste triée en prenant les éléments triés de la liste 1 puis x puis les
éléments de la liste 2.
b) Les questions
1) Écrire une fonction tri_select(L) retournant la liste triée par la méthode de tri par
sélection.
2) Écrire une fonction tri_bulles(L) retournant la liste triée par la méthode de tri à
bulles.
3) Écrire une fonction récursive tri_rapide(L) retournant la liste triée par la
méthode de tri rapide. On se servira de la fonction Python pivot=L.pop() qui affecte
à la variable pivot la valeur du dernier élément de la liste L et qui le supprime de
cette liste.
4) Écrire un algorithme permettant de comparer la rapidité d'exécution de chacune
des fonctions précédentes. Pour cela :
• importer le module Python time, en insérant en début de partie principale,
l'instruction import time, puis utiliser la fonction time.time() renvoyant le temps
en seconde écoulé depuis le 1er janvier 1970 à 0 h OO.
• importer le module Python random, en insérant en début de partie principale,
l'intruction import random, puis générer une liste Lh de 100 nombres réels, en
utilisant l'instruction Lh.append(random.random()) qui insère dans la liste Lh un
nombre réel choisi au hasard entre 0 et 1.
5) Classer ces méthodes de tri, de la plus rapide à la moins rapide.
0
c
:J
0
li)
..--t
0
N
@
.......
J::
O'l
·;::::
>0.
0
u
Chapitre l 0 • Travaux pratiques
242
l 0.7 MÉTHODES DE TRI
Énoncé
a) Le problème
Le but de ce TP est de comparer le temps d'exécution de plusieurs méthodes de tri
d'une liste de nombres par ordre croissant. Parmi ces méthodes, on peut distinguer:
• Le tri par sélection : on recherche le plus petit élément de la liste, que l'on place
en première position, puis le plus petit de la liste formée par les autres éléments,
que l'on place en seconde position, etc.
• Le tri à bulles : pour une liste L, on compare tous les éléments successifs L[k],
L[k+ 1]. Lorsque deux éléments successifs ne sont pas rangés par ordre croissant,
on les intervertit. Après un parcours complet de la liste, on recommence, et ainsi
de suite jusqu'à ce qu'au cours d'un parcours, aucune interversion n'ai lieu.
• Le tri rapide : pour une liste Layant au moins deux éléments, on retire le premier
élément x de cette liste puis on crée deux listes, celle des éléments inférieurs ou
égaux à x (liste 1) et celle des éléments supérieurs à x (liste 2). On fait de même
avec ces nouvelles listes et ainsi de suite (il s'agit d'un algorithme récursif). On
obtient la liste triée en prenant les éléments triés de la liste 1 puis x puis les
éléments de la liste 2.
b) Les questions
1) Écrire une fonction tri_select(L) retournant la liste triée par la méthode de tri par
sélection.
2) Écrire une fonction tri_bulles(L) retournant la liste triée par la méthode de tri à
bulles.
3) Écrire une fonction récursive tri_rapide(L) retournant la liste triée par la
méthode de tri rapide. On se servira de la fonction Python pivot=L.pop() qui affecte
à la variable pivot la valeur du dernier élément de la liste L et qui le supprime de
cette liste.
4) Écrire un algorithme permettant de comparer la rapidité d'exécution de chacune
des fonctions précédentes. Pour cela :
• importer le module Python time, en insérant en début de partie principale,
l'instruction import time, puis utiliser la fonction time.time() renvoyant le temps
en seconde écoulé depuis le 1er janvier 1970 à 0 h OO.
• importer le module Python random, en insérant en début de partie principale,
l'intruction import random, puis générer une liste Lh de 100 nombres réels, en
utilisant l'instruction Lh.append(random.random()) qui insère dans la liste Lh un
nombre réel choisi au hasard entre 0 et 1.
5) Classer ces méthodes de tri, de la plus rapide à la moins rapide.