Chapitre 4 - Les tris
Durant ce chapitre, nous allons voir comment fonctionne différents tris, voir leurs utilités et leurs rapidités.
Les 4 types de tris étudiés :
-
Le tri à bulles : On compare 2 éléments qui sont côte à côte dans la liste et on les intervertis si c'est nécessaire. Il faut pour cela une case mémoire supplémentaire. On répète l'opération tant que la liste n'est pas triée.
-
Le tri par sélection : On sélectionne dans le liste le minimum et on le place au début de la liste. Puis, parmi la liste restante, on sélectionne le nouveau minimum et on le place au début de la liste restante. Cet algorithme utilise un algorithme de recherche du minimum, il faut une liste de n éléments non trié, c'est alors n - 1 comparaisons qui sont nécessaire. On répète l'opération tant que la liste n'est pas triée.
-
Le tri par insertion : On considère que le début de la liste est déjà trié, c'est qui fait un seul élément au début, et on insert l'élément qui suit à sa place dans la liste. On répète l'opération tant que la liste n'est pas triée.
-
Le tri par fusion : On choisit de trier des sous-listes de 2 éléments, puis on les fusionne avec les listes voisines jusqu'à ce que l'ensemble de la liste soit triés.
Tri à bulles Tri par sélection Tri par insertion Tri par fusion
La complexité d'un tri :
La complexité d'un tri permet de savoir si le tri est efficace ou inefficace par rapport à un autre tri, on calcule son coût. 3 types de coûts sont étudiés cette année : le coût linéaire, quadratique et exponentielle.
Le coût linéaire indique une proportionnalité entre le temps d'exécution et le nombre d'éléments N de la liste, on le note O(n). Le coût quadratique dépend du carré de nombre d'éléments de la liste, on le note O(n²). Le coût exponentielle dépend de la fonction exponentielle, on le note O(log(n)).
Le coût exponentielle est très inefficace car il est conçu de la fonction exponentielle. Les coûts linéaire et quadratique, suivants leur usage, sont plutôt efficace.