[NSI] Les algorithmes de tri 💻

L’étude des algorithmes de tri est un passage obligé pour tous les étudiants en informatique. Tu n’as pas bien compris ce cours et tu cherches des comparaisons entre les différents algorithmes de tri ? Tu souhaites mieux comprendre la notion de complexité ? 📂

Pas de souci, les Sherpas t’expliquent tout ce que tu dois connaître sur ce sujet afin de réussir ton prochain contrôle. Let’s go ! ✨

Comprendre les algorithmes de tri en informatique ⌨️

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 à tes professeurs 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.

Tu cherches quelqu’un pouvant t’aider en NSI ? Retrouve nos cours particuliers d’informatique. Le premier cours est offert et te permettra de savoir si un Sherpa peut t’aider à progresser ! 😉

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)).

Fabien

Télécom Paris

20€/h

Nicolas

CentraleSupélec

17€/h

Louise

Mines ParisTech

24€/h

Fanny

Ponts ParisTech

19€/h

Besoin d’un prof particulier d’informatique ? ✨

Nos Sherpas sont là pour t’aider à progresser et prendre confiance en toi !

JE PRENDS UN COURS GRATUIT !

Les différents algorithmes de tri à connaître ⚙️

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é. 🔁

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 à bulle ⏺

👉 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 à bulle :

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 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.

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)).

Margot

Arts et Métiers ParisTech

22€/h/h

Bastien

Polytechnique

26€/h

Hugo

Insa Lyon

16€/h

Thibault

ENS Paris Ulm

20€/h

Ton premier cours particulier d’informatique est offert ! 🎁

Tous nos profs sont passés par les meilleures écoles de France !

J’EN PROFITE !

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.

Le tri fusion

👉 Le tri fusion consiste à fusionner 2 listes en les triant. Puis, recommencer cela de manière itérative de manière à fusionner d’abord les valeurs une à une, puis deux à deux… 🔀

Voici son pseudo-code :

fonction triFusion(Tableau T)
      si n ≤ 1
              renvoyer T
      sinon
              renvoyer fusion(triFusion(T[1, …, n/2]), triFusion(T[n/2 + 1, …, n]))
      fin_si_sinon
fin_triFusion


fonction fusion(Tableau A, Tableau B)
      si A est le tableau vide
              renvoyer B
      si B est le tableau vide
              renvoyer A
      si A[1] ≤ B[1]
              renvoyer A[1] ⊕ fusion(A[2, …, a], B)
      sinon
              renvoyer B[1] ⊕ fusion(A, B[2, …, b])
      fin_si_sinon
fin_fusion

Il possède aussi une complexité linéarithmique (O(n log n)) mais il a le défaut de nécessiter un tableau annexe de taille n. Si la mémoire est restreinte, c’est un inconvénient.

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. 🧐

Si tu as bien compris ce sujet, n’hésite pas à feuilleter nos autres articles sur des sujets d’informatique !