TP2 : Les Méthodes de tri
Instruction
On utilisera la fonction suivante randlist(n, a, b) renvoyant une liste peusdo-
aléatoire de n entiers de l’intervalle [a, b[. Par défaut a = 100 et b = 1000 (et
alors la fonction randlist renvoie des listes de nombres à trois chiffres) :
1 def randlist(n, a=100, b=1000):
2 from random import randrange
3 return [randrange(a, b) for _ in range(n)]
4
5 result = randlist(10)
6 print(result)
7 >>>[521, 753, 740, 141, 710, 598, 181, 607, 157, 931]
1 Exercice (Tri « bulle »)
Le principe de la méthode du « tri bulle » est le suivant :
— on parcourt la liste à trier (de longueur n), et dès qu’on rencontre deux
éléments consécutifs qui ne sont pas dans le bon ordre, on les échange ; à
l’issue de ce parcours, l’élément maximum se retrouve à la fin de la liste.
— on recommence un parcours sur les n − 1 premiers éléments, etc.
— le dernier parcours se limite à comparer les deux premiers éléments.
1. Écrire la fonction tri_bulle(L) qui trie sur place une liste L d’éléments
comparables entre eux.
2. Calculer la complexité de cette fonction.
2 Exercice (Tri « sélection »)
Le principe de la méthode du « tri sélection » est le suivant :
— rechercher l’élément minimum, puis l’échanger avec le premier élément ;
— recommencer avec la liste des n − 1 éléments suivants ;
— ainsi de suite jusqu’à obtenir la liste trié(e).
Écrire la fonction tri_selection(L) qui trie sur place une liste L d’éléments
comparables entre eux et calculer sa complexité.
1
3 Exercice (Tri « insertion »)
Le principe de la méthode du « tri insertion » est le suivant :
— rechercher l’élément minimum, puis l’échanger avec le premier élément ;
— recommencer avec la liste des n − 1 éléments suivants ;
— ainsi de suite jusqu’à obtenir la liste trié(e).
Écrire la fonction tri_selection(L) qui trie sur place une liste d’éléments
comparables entre eux, puis calculer sa complexité.
Question : La quel des fonctions programmé est la plus efficace ?
