[NSI] Les algorithmes de tri đŸ’»

Sofiane MaziĂšres - Mis Ă  jour le 17/08/2021
190078

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
algorithmes de tri

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

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

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 !

5/5 - (3 votes)

Laisse-nous un commentaire !

Des questions ? Des bons plans Ă  partager ? Nous validons ton commentaire et te rĂ©pondons en quelques heures ! 🎉

Ebook

Notre ebook pour t’aider au lycĂ©e

TĂ©lĂ©charge notre guide pour progresser et rĂ©ussir toutes les Ă©preuves au lycĂ©e ! 🎓