4.0 Algorithmes de tri
Les algorithmes de tri sont fondamentaux dans la gestion des données et permettent l’accès à des informations dans des délais très brefs. Aussi l’ingéniosité des informaticiens a été mise en œuvre pour élaborer ceux qui nécessitent le moins d’opérations.
Trier des données, c’est les ranger suivant un ordre défini au préalable. Par exemple avec des données numériques, nous pouvons trier ces données en utilisant l’ordre défini en mathématiques : \(a\) est avant \(b\) si \(b - a\) est positif (\(a < b\) si \(b - a > 0\) ).
Si nous trions l’ensemble de nombres \({3,8,5,2}\), nous obtenons l’ensemble \({2,3,5,8}\) et nous disons que les nombres sont rangés suivant l’ordre croissant. Si nous les rangeons dans l’ordre inverse, nous parlons d’ordre décroissant.
Les lettres de notre alphabet sont rangées suivant l’ordre alphabétique. Nous pouvons alors trier un ensemble de mots, par exemple l’ensemble de quatre mots \({bonjour, bon, table, assiette}\), en suivant l’ordre lexicographique qui utilise lui-même l’ordre alphabétique. Nous obtenons l’ensemble \({assiette, bon, bonjour, table}\).
Des suites d’instructions permettant d’effectuer un tri ont été étudiées dès les années 1940 sur les premiers ordinateurs. Durant cette période, l’américaine Betty Holberton était l’une des six programmatrices de l’ENIAC, le premier ordinateur entièrement électronique.
Elle travaillait sur différents codes et applications et c’est à ce moment qu’elle développa sans doute le premier programme de tri. Elle travaillera plus tard avec Grâce Hopper sur les langages de programmation COBOL et Fortran.
Dans les algorithmes présentés plus loin, nous procédons par des comparaisons successives entre deux éléments et effectuons éventuellement une permutation des deux éléments comparés.
Le nombre de permutations est donc toujours inférieur au nombre de comparaisons. Le coût ou la complexité d’un algorithme est dans ce cas un ordre de grandeur du nombre de comparaisons effectuées par cet algorithme.
Pour un algorithme donné, le coût peut être différent suivant les cas à traiter, il y a des cas favorables, et d’autres non. Ce coût doit absolument être évalué avant d’écrire un programme et l’exécuter car suivant la taille de l’ensemble de données, le temps de calcul avec une machine peut devenir rédhibitoire.
Prenons trois nombres tout distincts \(a\), \(b\) et \(c\).
Il y a six manières de ranger ces trois nombres :
\((a,b,c)\)
\((a,c,b)\)
\((b,a,c)\)
\((b,c,a)\)
\((c,a,b)\)
\((c,b,a)\)
Si en comparant \(a\) et \(b\), nous obtenons \(a < b\), alors le nombre de rangements possibles est divisé par deux, il n’en reste plus que trois :
\((a, b, c)\)
\((a, c, b)\)
\((c, a, b)\)
La comparaison de \(a\) et \(c\) permet de conclure si \(c < a\), sinon il faut une troisième comparaison entre \(b\) et \(c\).
Pour quatre nombres \((a, b, c, d)\), il y a quatre fois plus de rangements possibles.
En effet, pour chacun des six rangements de \(a\), \(b\) et \(c\), il y a quatre places possibles pour \(d\) : * en premier, * soit entre le premier et le deuxième, * soit entre le deuxième et le troisième, * soit en dernier.
Après une première comparaison, il reste douze rangements possibles, et après une seconde comparaison il en reste six. Au total, nous avons donc cinq comparaisons au maximum.
Le nombre total \(r\) de rangements possibles de \(n\) données vaut \(n * (n - 1) * 2 * 1\) noté \(n!\), \(n\) factoriel.
Après chaque comparaison, ce nombre de rangements possibles est divisé par 2. Donc après \(k\) comparaison, il est divisé par \(2k\). Le tri est terminé lorsqu’il ne reste plus qu’un seul rangement possible, c’est-à-dire dès que \(2k > r\).
Remarque : en binaire, 2 s’écrit avec \(k +1\) bits. Donc le nombre de comparaisons est de l’ordre du nombre de chiffres dans l’écriture binaire de \(r\).
Il est intéressant de faire un test avec un jeu de 32 cartes, un ordre étant défini sur l’ensemble des cartes. On utilise un ordre sur les valeurs, 7, 8, 9, 10, valet, dame, roi, as, et pour ordonner deux cartes de même valeur, un ordre sur les couleurs. Comme pour l’ordre lexicographique avec des mots de deux lettres, il s’agit d’un ordre sur les couples \((valeur, couleur)\).
On distribue une dizaine de cartes à une personne et on lui demande d’ordonner les cartes. On recommence avec d’autres personnes. Avec chaque personne, on essaie de dégager une stratégie, un algorithme de tri. On peut alors remarquer que des algorithmes comme le tri sélection, le tri insertion, ainsi que d’autres plus élaborés sont utilisés et souvent à tour de rôle pour un tri donné.
L’idée « diviser pour régner » est présente.
4.1 Tri par sélection
En anglais, cet algorithme est nommé « selection sort ».
Le principe
On dispose de \(n\) données. On cherche la plus petite donnée et on la place en première position, puis on cherche la plus petite donnée parmi les données restantes et on la place en deuxième position, et ainsi de suite.
Si les données sont les éléments d’une liste \(liste\), l’algorithme consiste donc à faire varier un indice \(i\) de \(0\) à \(n - 2\). Pour chaque valeur de \(i\), on cherche dans la tranche liste \([i : n]\) le plus petit élément et on l’échange avec \(liste[i]\).
L’algorithme de tri par sélection est souvent utilisé pour trier à la main des objets, comme des cartes à jouer, des livres, etc.
i_mini ← i (indice du plus petit élèment)
mini ← liste[i]
pour j variant de i+1 à n-1
si liste[j] < mini
i_mini ← j
mini ← liste[j]
Pour obtenir un algorithme du tri sélection, il ne reste qu’à insérer l’algorithme du minimum dans une boucle où \(i\) varie de \(0\) à \(n-2\) et pour chaque valeur de \(i\) à faire échange de liste[i] avec liste[i_mini].
La donnée en entrée est une liste de \(n\) éléments. Il n’y a pas de résultat renvoyé en sortie, la liste est modifiée en place.
POUR i VARIANT de i à n-2
i_mini ← i
mini ← liste[i]
POUR j VARIANT de i+1 à n-1
SI liste[j] < mini
i_mini ← j
mini ← liste[j]
ECHANGER liste[i] et liste[i_mini]
1def tri_selection(liste) :
2 for i in range(len(liste) -1 ):
3 i_mini = i
4 mini = liste[i]
5 for j in range (i+1, len(liste)) :
6 if(liste[j] < mini ) :
7 i_mini = j
8 mini = liste[j]
9 liste[i], liste[i_mini] = liste[i_mini], liste[i]
Exemple avec la liste \([7, 4, 3, 2, 9, 5]\) et les éléments échangés.
\([2, 4, 3, 7, 9, 5]\) après échange de 2 et 7.
Pour i égal à 0
Pour i égal à 1
Pour i égal à 2
Pour i égal à 3
Pour i égal à 4
\([2, 3, 4, 7, 9, 5]\) après échange de 3 et 4. \([2, 3, 4, 7, 9, 5]\) après aucun échange. \([2, 3, 4, 5, 9, 7]\) après échange de 5 et 7. \([2, 3, 4, 5, 7, 9]\) après échange de 7 et 9.
La liste passée en paramètre est modifiée en place. Donc pour utiliser cette fonction, il suffit d’écrire l’instruction tri_selection(liste).
Si nous ne voulons pas modifier la liste passée en paramètre il faut en faire une copie et ensuite renvoyer une nouvelle liste qui est triée. On obtient alors le programme suivant :
1 def tri_selection(liste) :
2 liste = list(liste)
3 for i in range(len(liste) -1 ):
4 i_mini = i
5 mini = liste[i]
6 for j in range (i+1, len(liste)) :
7 if(liste[j] < mini ) :
8 i_mini = j
9 mini = liste[j]
10 liste[i], liste[i_mini] = liste[i_mini], liste[i]
11 return liste
12
13 # testons le programme :
14
15 tri = tri_selection([7, 4, 3, 2, 9, 5])
16 print(tri)
La console retourne :
>>> tri = tri_selection([7, 4, 3, 2, 9, 5])
>>> print(tri)