Algorithmes de tri
Dans cette section, on s’intéresse à un problème très courant en informatique, à savoir celui de trier
une liste.
On peut générer une liste aléatoirement en important le module random.
from random import randrange
#on génère une liste de 20 nombres au hasard en 0 et 99
n = 20
liste_une = [randrange(100) for i in range(n)]
print(liste_une)
Tri par sélection
La méthode de tri par sélection consiste à rechercher le plus grand élément du tableau que l’on va
échanger avec le dernier élément. Puis on recommence avec le deuxième élément le plus grand que
l’on échange avec l’avant dernier. Et ainsi de suite ...
Le code suivant contient deux fonctions :
- la fonction maxi(l, n) qui prend en argument une liste l et un nombre n et qui retourne le
maximum et son indice parmi les n premiers éléments de la liste.
- la fonction tri_selec qui trie une liste selon la méthode de tri par sélection, en utilisant la
fonction maxi.
def maxi(l, n):
indice = 0
for i in range(n):
if(l[i] > l[indice]):
indice = i
return [l[indice], indice]
def tri_selec(l):
i = len(l) - 1
while(i > 0):
j = maxi(l, i + 1)[1]
if(j != i):
l[j], l[i] = l[i], l[j]
i -= 1
return l
Tri par insertion
Le tri par insertion est généralement le tri que l'on utilise pour classer des documents : on commence
par prendre le premier élément à trier que l'on place en position 1. Puis on insère les éléments dans
l'ordre en plaçant chaque nouvel élément à sa bonne place.
Pour procéder à un tri par insertion, il suffit de parcourir une liste : on prend les éléments dans l'ordre.
Ensuite, on les compare avec les éléments précédents jusqu'à trouver la place de l'élément qu'on
considère. Il ne reste plus qu'à décaler les éléments du tableau pour insérer l'élément considéré à sa
place dans la partie déjà triée.
Par exemple, si on veut trier la liste [12, 3, 17, 9, 4, 2, 16], on obtient successivement :
Le code suivant contient deux fonctions :
- la fonction insertion(1, n) qui prend en argument une liste l dont on suppose que les n
premiers éléments sont triés et qui insère l'élément l[n] à sa place parmi les n premiers
éléments de l.
- la une fonction tri_insert(l) qui effectue un tri par insertion de la liste l.
def insertion(l, n):
while(l[n] < l[n-l] and n > 0):
l[n-l], l[n] = l[n], l[n-l]
n -= 1
return l
def tri_insert(1):
n = len(l)
for i in range(1, n):
l = insertion(l, i)
return l