Les tris

Issu de : https://sherpas.com/blog/algorithmes-de-tri/, et de Wikipédia pour les animations.

Qu’est-ce qu’un algorithme de tri ?

👉 Un algorithme de tri est une suite finie d’opérations permettant d’organiser des éléments dans un ordre déterminé préalablement. Le plus souvent, les informaticiens trient des tableaux d’entiers du plus petit au plus grand.

Les algorithmes de tri ont de nombreuses utilités et leur étude est un sujet majeur de recherche en informatique. 

👉 En cours de NSI, les algorithmes de tri permettent de vérifier ta compréhension des concepts de terminaison d’algorithme et d’invariants de boucle.

En effet, lorsque l’on utilise une boucle (while et for), il faut faire attention à la terminaison de celle-ci. Sinon, la boucle est infinie et le programme ne s’arrêtera pas. L’oubli le plus fréquent est lié au compteur qu’il faut incrémenter en fin de boucle.

Le terme “invariants de boucle” désigne une propriété qui est vraie pour tous les passages de la boucle, y compris avant d’y entrer et d’en sortir.

La complexité d’un algorithme 😣

Plusieurs stratégies existent pour trier des tableaux. On peut déterminer leur efficacité grâce au calcul de la complexité. Cela correspond à la quantité de ressources nécessaires à l’exécution du programme. 🔧

👉 La complexité d’un algorithme se note généralement par une fonction dépendant du nombre de valeurs présentes dans celui-ci. On parle ainsi de complexité :

• constante, O(1), si le temps de calcul est toujours le même, quel que soit le nombre d’éléments

• logarithmique, O(log n), si le temps de calcul est proportionnel au logarithme du nombre d’éléments

• linéaire, O(n), si le temps de calcul est proportionnel au nombre d’éléments

• linéarithmique, O(n log n), si le temps de calcul est proportionnel au nombre d’éléments multiplié par le logarithme du nombre d’éléments.

• quadratique, O(n²), si le temps de calcul et proportionnel au carré du nombre d’éléments

• exponentielle, O(2^n), si le temps de calcul est proportionnel à 2 exposant le nombre d’éléments

Sur un tableau de petite taille, la différence de temps mis par l’algorithme est quasiment invisible selon sa complexité. Cependant, si le tableau a plusieurs millions d’éléments, la durée de son tri peut varier de plusieurs jours selon l’algorithme utilisé. Il est donc primordial de comprendre les avantages et inconvénients des algorithmes de tri. ⏰

En l’état actuel des connaissances, les meilleurs algorithmes de tri ont une complexité linéarithmique (O(n log n)). 

Le tri par sélection

👉 Cet algorithme est intuitif. D’abord, il cherche l’élément le plus petit du tableau. Puis, il échange cet élément avec l’élément en première place du tableau. Enfin, il réitère ces actions jusqu’à ce que le tableau soit entièrement trié.

Le tri par sélection consiste donc à découper la liste en deux parties :

• Une partie triée située en début de liste

• Une partie non triée située en fin de liste

Initialement, la première partie est vide. Afin de la faire grossir, on va chercher dans la partie non triée la valeur la plus petite.Une fois trouvée, elle est échangée avec la première valeur de la partie non triée, et la zone de la parte triée est étendue jusqu'à cette nouvelle valeur.

Voici le pseudo-code correspondant : 

tri_selection(Tableau T)

      n ← longueur(T) 

      pour i de 0 à n - 2

          min ← i       

          pour j de i + 1 à n - 1

              si T[j] < T[min], alors min ← j

          fin pour

          si min ≠ i, alors échanger T[i] et T[min]

      fin pour

fin tri_selection

La complexité du tri par sélection est en O(n²). Il n’est donc pas très efficace. Mais, il fait très peu d’échanges (au maximum, n-1). Donc, il peut être utilisé si les éléments sont coûteux à déplacer (ce qui n’est pas le cas d’un tableau d’entier) et peu coûteux à comparer. 

Le tri par insertion

👉 Cette stratégie consiste à placer trier élément par élément le tableau. D’abord, l’algorithme trie les 2 premières valeurs. Puis, il place la troisième à sa place vis-à-vis des 2 premières. Au global, il s’agit de placer la valeur i dans la partie du tableau déjà triée allant de la première valeur à la i-1ème.

Le tri par insertion, comme le tri par sélection, consiste donc à découper la liste en deux parties :

• Une partie triée située en début de liste

• Une partie non triée située en fin de liste

Le changement majeur est qu'au lieu de chercher la valeur minimale dans la partie non triée, on va récupérer la première valeur qu'on va insérer dans la première partie (en respectant l'ordre croissant).

Voici le pseudo-code correspondant : 

tri_insertion(Tableau T)

       pour i de 1 à taille(T) - 1

            x ← T[i]                            

            j ← i                               

            tant que j > 0 et T[j - 1] > x

                     T[j] ← T[j - 1]

                     j ← j - 1

            fin_tant_que

            T[j] ← x  

       fin_pour

fin_tri_insertion

En moyenne, le tri par insertion a une complexité quadratique (O(n²)), mais si le tableau est déjà ordonné, sa complexité est linéaire (O(n)). 

Le tri à bulles

👉 Cette méthode de tri consiste à inverser tous les couples de nombres non ordonnés. Par exemple, avec les 3 éléments : 6|5|4 : le tri à bulle va comparer 6 et 5, comme ils ne sont pas ordonnés, ils vont être inversés (on aura 5|6|4), puis va comparer 6 et 4 et les échanger (5|4|6). ☑️

À la fin de la première boucle, le plus grand élément du tableau sera forcément bien placé. Puis, l’algorithme recommence jusqu’à la fin du tri.

Voici le pseudo-code du tri à bulles :

tri_à_bulles(Tableau T)

   pour i allant de (taille de T)-1 à 1

       pour j allant de 0 à i-1

           si T[j+1] < T[j]

               (T[j+1], T[j]) = (T[j], T[j+1])

           fin_si

       fin_pour

   fin_pour

fin_tri_à_bulles

Cet algorithme a aussi une complexité quadratique en O(n²). Cependant, plus le tableau est préalablement trié, plus il est efficace. En moyenne, il est aussi efficace que le tri par sélection, mais dans les cas particuliers où le tableau est en partie ordonné, il est plus efficace. 

Le tri rapide

Le tri rapide est un peu plus complexe à comprendre, mais il a de nombreux avantages que nous détaillerons après son explication. 💪

👉 L’idée est de choisir un élément au hasard dans le tableau et de s’en servir comme pivot. On va placer d’un côté toutes les valeurs inférieures au pivot, et de l’autre les valeurs supérieures à celui-ci. Puis, il faudra réitérer cela pour chaque partie du tableau, jusqu’à que les partitions soient composées d’un seul élément.

Voici comment on le code :

partitionner(tableau T, entier premier, entier dernier, entier pivot)

    échanger T[pivot] et T[dernier] 

    j := premier

    pour i de premier à dernier - 1 // la boucle se termine quand i = (dernier-1).

        si T[i] <= T[dernier] alors

            échanger T[i] et T[j]

            j := j + 1

        fin_si

    fin_pour

    échanger T[dernier] et T[j]

    renvoyer j

fin_partitionner

tri_rapide(tableau T, entier premier, entier dernier)

    si premier < dernier alors

        pivot := choix_pivot(T, premier, dernier)

        pivot := partitionner(T, premier, dernier, pivot)

        tri_rapide(T, premier, pivot-1)

        tri_rapide(T, pivot+1, dernier)

    fin_si

fin_tri_rapide

La complexité de cet algorithme est linéarithmique (O(n log n)). L’espace mémoire utilisé est aussi faible. 

Rem : on voit que la fonction tri_rapide s'appelle elle même, on parle alors de fonction récursive. Cette notion de récursivité sera étudiée en classe de terminale.

Conclusion sur les algorithmes de tri

Nous avons vu que de nombreux algorithmes permettent de trier un tableau. Cependant, certains sont plus efficaces que d’autres, car leur complexité est plus faible.

Sur des petits tableaux, la différence est minime, mais lorsque ceux-ci possèdent plusieurs millions d’éléments, il devient indispensable de choisir un algorithme ayant une complexité minimale. 🧐