Tri par sélection et tri par insertion

Les algorithmes de tri ordonnent les éléments d'une liste selon un critère (croissant, décroissant). Le tri par sélection parcourt la liste pour trouver le minimum, le place en première position, puis recommence sur le reste de la liste. Le tri par insertion traite les éléments un par un : chaque nouvel élément est inséré à sa place dans la partie déjà triée, comme quand on trie des cartes dans sa main. Ces deux algorithmes ont une complexité quadratique O(n²) dans le pire cas, ce qui les rend inefficaces pour de grandes listes. Le tri par insertion est cependant plus rapide en pratique quand la liste est presque triée. Prouver qu'un algorithme de tri est correct nécessite de montrer un invariant de boucle : une propriété vraie à chaque itération.