Laboratoire visuel : les tris
Suivez pas à pas les tris à bulles, par sélection et par insertion, puis comparez leur nombre d’opérations sur des listes aléatoires.
Le tri à bulles suit ce code :
def tri_bulles(L):
n = len(L)
for k in range(n - 1):
for j in range(n - 1 - k):
if L[j] > L[j + 1]:
L[j], L[j + 1] = L[j + 1], L[j]
return LLe tri par sélection suit ce code :
def tri_selection(L):
n = len(L)
for i in range(n - 1):
p = i
for j in range(i + 1, n):
if L[j] < L[p]:
p = j
L[i], L[p] = L[p], L[i]
return LLe tri par insertion suit ce code :
def tri_insertion(L):
n = len(L)
for i in range(1, n):
x = L[i]
j = i - 1
while j >= 0 and L[j] > x:
L[j + 1] = L[j]
j = j - 1
L[j + 1] = x
return LSuivez chaque comparaison et chaque échange ou écriture. Les étiquettes au-dessus des cases montrent où pointent les indices du code ; la zone verte est définitive pour les bulles et la sélection, et triée pour l’insertion.
Jusqu'à 10 entiers, séparés par des virgules ou des espaces.
Tableau initial
Comparer sur des listes aléatoires
Choisissez une taille N. Pour chaque essai, les trois méthodes sont évaluées sur la même liste ; le graphique conserve les moyennes obtenues pour chaque taille testée.
Entiers tirés entre 0 et 999 : 1 000 listes si N ≤ 100, 500 si N ≤ 10 000, puis 100. N doit être compris entre 1 et 100 000.
Aucun test effectué.
Une opération = une comparaison de valeurs, un échange (même avec soi-même), ou une écriture dans L pour l’insertion (décalage ou insertion de x). Les tests de boucle ne sont pas comptés. Au-delà de N = 200, les comptes sont calculés exactement : N(N − 1)/2 comparaisons pour les bulles et la sélection, N − 1 échanges pour la sélection, et autant d’échanges que d’inversions pour les bulles. Pour l’insertion : une écriture par inversion, plus N − 1 insertions ; une comparaison par inversion, plus un test d’arrêt pour chaque valeur qui n’est pas un nouveau minimum strict.
| Taille N | Listes | Tri à bulles · moyenne | Tri par sélection · moyenne | Tri par insertion · moyenne |
|---|