Introduction
Les algorithmes de tri permettent de trier des séquences d'éléments. Pour rappel, une séquence est un ensemble ordonné d'éléments (une liste est une séquence).
Comme vu précédemment, dans les algorithmes gloutons, mais aussi la dichotomie, avoir une liste triée permet de simplifier beaucoup d'algorithmes !
On verra au fur et à mesure des deux ans de NSI d'autres algorithmes qui utilisent cette propriété.
Contenus | Capacités attendues | Commentaires |
|---|---|---|
Tris par insertion, par sélection | Écrire un algorithme de tri. Décrire un invariant de boucle qui prouve la correction des tris par insertion, par sélection. | La terminaison de ces algorithmes est à justifier. On montre que leur coût est quadratique dans le pire cas. |