Algorithmes de tri⚓︎
On souhaite trier une liste L, c'est-à-dire réarranger ses éléments pour qu'ils soient rangés dans l'ordre croissant. Par exemple, si L = [5, 1, -4, 2, -8, 7] alors un algorithme de tri doit permettre d'obtenir la liste [-8, -4, 1, 2, 5, 7]. Dans ce TP, nous étudions plusieurs algorithmes de tri. Pensez à bien tester toutes vos fonctions.
Tri par sélection⚓︎
Le tri par sélection consiste à chercher le minimum que l'on met en 1ère position de la liste, puis le 2ème plus petit élément en 2ème position...
Exercice⚓︎
Écrire une fonction minimum(L, i) qui renvoie l'indice du minimum de la liste L à partir de la position i. Par exemple, si L = [5, 1, -8, 2, -4, 7], minimum(L, 0) doit renvoyer 2 (correspondant à L[2] = -8) et minimum([5, 1, -8, 2, -4, 7], 3) doit renvoyer 4 (correspondant à L[4] = -4).
Exercice⚓︎
Écrire une fonction tri_selection(L) qui trie une liste L en utilisant le tri par sélection. On pourra compléter le code suivant :
Tri par insertion⚓︎
Le tri par insertion consiste à trier progressivement la liste L, de gauche à droite. Plus précisément, à l'étape i , les i premiers de L sont triés et on fait en sorte d'insérer le i+1ème élément L[i] au bon endroit pour que les i+1
premiers éléments soient triés. Voici les étapes du tri par insertion pour la liste L = [5, 1, -4, 2, -8, 7] :
i = 0 : on insère L[0] = 5 de façon à ce que le 1er élément de L soit trié (il n'y a rien à faire : un élément seul est toujours trié). L vaut [5, 1, -4, 2, -8, 7] (on met en gras la partie de L déjà triée).
i = 1 : on insère L[1] = 1 au bon endroit, ce qui donne [1, 5, -4, 2, -8, 7]
i = 2 : on insère L[2] = -4 au bon endroit, ce qui donne [-4, 1, 5, 2, -8, 7]
i = 3 : on insère L[3] = 2 au bon endroit, ce qui donne [-4, 1, 2, 5, -8, 7]
i = 4 : on insère L[4] = -8 au bon endroit, ce qui donne [-8, -4, 1, 2, 5, 7]
i = 5 : on insère L[5] = 7 au bon endroit, ce qui donne [-8, -4, 1, 2, 5, 7]
On a terminé, et la liste est bien triée.
Exercice⚓︎
Ecrire une fonction position telle que, si L est une liste, i un indice de L et e une valeur, position(L, i, e) renvoie le plus petit indice j < i tel que L[j] > e. S'il n'existe pas de tel indice j, on renverra i. Exemple : position([1, 5, -4, 2, -8, 7], 2, -4) doit renvoyer 0, position([-8, -4, 1, 2, 5, 7], 5, 7) doit renvoyer 5. On pourra compléter le code suivant :
def position(L, i, e):
for j in range(i):
if ...:
return ...
return i
print(position([1, 5, -4, 2, -8, 7], 2, -4)) # test
print(position([-8, -4, 1, 2, 5, 7], 5, 7)) # test
Exercice⚓︎
Écrire une fonction decaler telle que decaler(L, i, j) décale les éléments de la liste L d'une position vers la droite. Ainsi, la valeur de L[i] doit être mise dans L[i + 1], L[i + 1] dans L[i + 2], ..., L[j - 1] doit être mise dans L[j]. Par exemple, après les instructions L = [1, 3, 6, 9, 17] et decaler(L, 1, 3), L doit contenir [1, 3, 3, 6, 17] (L[i] n'est pas modifié). Solution
Exercice⚓︎
En utilisant position et decaler, écrire une fonction tri_insertion qui trie une liste en utilisant le tri par insertion. On pourra compléter le code suivant :
def tri_insertion(L):
for i in range(len(L)):
p = ...
decaler(...)
... # mettre l'anciennce valeur de L[i] dans L[p]
Tri fusion (récursif)⚓︎
Le tri fusion sur une liste L consiste à :
Séparer L en deux listes L1 et L2 de même taille.
Trier récursivement L1 et L2 pour obtenir des listes triées L1' et L2'.
Fusionner L1' et L2' pour avoir un tri de L.
Le tri fusion est donc récursif.
Illustration du tri fusion sur L = [5, 1, -4, 2, -8, 7] :
