Les algorithmes de tris
tri par sélection
Le tri par sélection est celui qui utilise le concept le plus simple. Étant donné qu'il existe un algorithme qui permet de renvoyer la valeur la plus petite d'un tableau, on peut l'appliquer systématiquement pour reconstruire un tableau trié. En d'autres termes, à chaque case du tableau que l'on souhaite trier, on effectue une recherche dans la partie de droite pour retrouver l'élément le plus petit. Une fois trouvé, on échange les valeurs.
PROCÉDURE TRI_SELECT(t: TABLEAU D'ENTIERS, n: ENTIER) VARIABLE i, j, min, swap: ENTIER POUR i DE 0 À N-2: min <- i POUR j DE i À N-1: SI t[j] < t[min], ALORS min = j FIN SI FIN POUR swap <- t[min] t[min] <- t[i] t[i] <- swap FIN POUR FIN PROCÉDURE
tri à bulles
Il consiste à comparer répétitivement les éléments consécutifs d'un tableau, et à les permuter lorsqu'ils sont mal triés. Il doit son nom au fait qu'il déplace rapidement les plus grands éléments en fin de tableau, comme des bulles d'air qui remonteraient rapidement à la surface d'un liquide.
PROCÉDURE TRI_A_BULLES(t: TABLEAU D'ENTIERS, n: ENTIER) VARIABLE i, j, swap: ENTIER POUR i DE 0 À N-1 POUR j DE N-2 À i, PAR PAS DE -1: SI t[j+1] < t[j]: swap <- t[j+1] t[j+1] <- t[j] t[j] <- swap FIN SI FIN POUR FIN POUR FIN PROCÉDURE
PROCÉDURE TRI_A_BULLES_FASTER(t: TABLEAU D'ENTIERS, n: ENTIER) VARIABLE i, j, swap: ENTIER VARIABLE trié: BOOLÉEN trié <- Faux TANT QUE trié != Vrai ET 0 < n -1 trié <- Vrai POUR j DE N-2 À i, PAR PAS DE -1: SI t[j+1] < t[j]: swap <- t[j+1] t[j+1] <- t[j] t[j] <- swap trié <- Faux FIN SI FIN POUR i <- i+1 FIN TANT QUE FIN PROCÉDURE
tri par insertion
Le tri par insertion est considéré comme le tri le plus efficace sur des entrées de petite taille. Il est aussi très rapide lorsque les données sont déjà presque triées. La plupart des personnes l'utilisent naturellement pour trier des cartes à jouer.
PROCÉDURE TRI_INSERT(t: TABLEAU D'ENTIERS, n: ENTIER) VARIABLE i, j, swap: ENTIER POUR i DE 1 À N-1: j <- i TANT QUE j > 0 AND a[j-1] > a[j]: swap <- a[j] a[j] <- a[j-1] a[j-1] <- swap j <- j-1 FIN TANT QUE FIN POUR FIN PROCÉDURE
tri rapide
Il existe des familles de tri, plus rapide, mais aussi plus complexe à implémenter. L'un de ces algorithmes est celui de quicksort où l'idée est de diviser pour mieux régner.
L'idée est de fixer arbitrairement une valeur pivot, et de déplacer les valeurs à droite si elles sont plus grandes que le pivot ou à gauche dans le cas contraire. Une fois fait, il faut rééxécuter ce même algorithme sur ces deux nouvelles parties des tableaux. Il s'agit ici d'un algorithme récursif.
PROCÉDURE TRI_RAPIDE(t: TABLEAU D'ENTIERS, g: ENTIER, d: ENTIER) VARIABLES i, j, p, swap: ENTIER i <- g j <- d p <- t[j] TANT QUE i < j: TANT QUE t[i] < p: i <- i+1 FIN TANT QUE TANT QUE t[j] > p: j <- j-1 FIN TANT QUE SI i <= j, ALORS: swap <- t[i] t[i] <- t[j] t[j] <- swap i <- i+1 j <- j-1 FIN SI FIN TANT QUE SI g < j, ALORS: TRI_RAPIDE(t, g, j) FIN SI SI i < d, ALORS: TRI_RAPIDE(t, i, d) FIN SI FIN PROCÉDURE
La complexité des tris
Bien que QUICKSORT soit le plus rapide, il existe cependant un cas de figure théorique où l'algorithme est au pire cas en complexité quadratique. Toutefois malgré ce désavantage, c'est en pratique un des tris les plus rapides, et donc l'un des plus utilisés. Par contre, il restera plus lent que le tri par insertion dans le cas où le tableau est pratiquement déjà entièrement trié.
Il est d'ailleurs possible de combiner deux algorithmes ensembles pour éviter le pire cas. Par exemple, on peut utiliser le tri rapide lorsque le tableau est très grand, mais une fois que l'intervalle est suffisamment petit on peut utiliser un tri par insertion. C'est exactement le fonctionnement de Introsort.
| tri | pire cas | meilleur cas | moyenne |
|---|---|---|---|
| sélection | O( n² ) | O( n² ) | O( n² ) |
| bulle | O( n² ) | O( n ) | O( n² ) |
| insertion | O( n² ) | O( n ) | O( n² ) |
| rapide | O( n² ) | O( n log n ) | O( n log n ) |
- Last Author
- kossolax
- Last Edited
- Jan 7 2021, 7:51 PM