NSI en première

Tri

Extrait du programme

Algorithmique

Le concept de méthode algorithmique est introduit […]. Quelques algorithmes classiques sont étudiés. L'étude de leurs coûts respectifs prend tout son sens dans le cas de données nombreuses […].

Il est nécessaire de montrer l'intérêt de prouver la correction d'un algorithme pour lequel on dispose d'une spécification précise, notamment en mobilisant la notion d'invariant sur des exemples simples. […]

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.

Illustration

Lionel Avon