Numérique et sciences informatiques · Première · Algorithmique · 3.º Período

Algorithmes de tri

Étudier et implémenter les algorithmes de tri par insertion et par sélection. Analyser leur complexité quadratique et prouver leur terminaison.

En bref:L'étude des algorithmes de tri (insertion et sélection) est un moment clé pour comprendre l'efficacité informatique et la rigueur de la preuve. Ces algorithmes, bien que moins performants que les tris modernes, sont parfaits pour enseigner la manipulation d'index et les structures de boucles imbriquées. Les élèves découvrent que pour organiser des données, il existe plusieurs stratégies avec des logiques différentes.

• Programmes Officiels
• BOEN spécialité NSI 1re - Tri par insertion, tri par sélection
• BOEN spécialité NSI 1re - Complexité, terminaison et correction

À propos de ce thème

L'étude des algorithmes de tri (insertion et sélection) est un moment clé pour comprendre l'efficacité informatique et la rigueur de la preuve. Ces algorithmes, bien que moins performants que les tris modernes, sont parfaits pour enseigner la manipulation d'index et les structures de boucles imbriquées. Les élèves découvrent que pour organiser des données, il existe plusieurs stratégies avec des logiques différentes.

Ce chapitre introduit aussi des notions théoriques cruciales : la terminaison (est-on sûr que l'algorithme s'arrête ?) et la correction (est-on sûr que le résultat est trié ?). L'apprentissage par la manipulation physique de cartes à jouer permet de décomposer chaque étape du tri, rendant les boucles 'pour' et 'tant que' beaucoup plus intuitives.

Questions clés

1. Comment fonctionne le tri par sélection ?
2. Quelle est la différence de principe avec le tri par insertion ?
3. Comment démontrer qu'un algorithme de tri se termine toujours ?

Attention à ces idées reçues

Idée reçue courante

Confondre le tri par sélection et le tri par insertion.

Ce qu'il faut enseigner à la place

Le tri par sélection cherche le plus petit élément pour le placer au début, tandis que le tri par insertion prend l'élément suivant pour le 'glisser' à sa place. Utiliser des animations visuelles aide à distinguer ces deux mouvements.

Idée reçue courante

Penser que le tri par sélection est plus rapide car il fait moins d'échanges.

Ce qu'il faut enseigner à la place

Bien qu'il fasse moins d'échanges, il fait autant de comparaisons. Il faut montrer que les deux tris ont une complexité quadratique O(n²) pour que les élèves comprennent qu'ils sont équivalents sur de grands volumes.

Idées d'apprentissage actif

Cercle de recherche

La bataille des tris

La moitié de la classe applique le tri par sélection sur un jeu de cartes, l'autre le tri par insertion. Ils comptent le nombre de comparaisons et de déplacements pour comparer l'efficacité réelle.

45 min·Petits groupes

Enseignement par les pairs

Expliquer son tri

Un élève doit expliquer l'algorithme du tri par insertion à un camarade en utilisant uniquement des gestes et des objets, sans montrer le code.

20 min·Binômes

Rotation par ateliers

Preuves et complexité

Atelier 1 : tracer l'exécution sur papier. Atelier 2 : identifier le variant de boucle pour la terminaison. Atelier 3 : coder l'algorithme en Python.

55 min·Petits groupes

Questions fréquentes

Comment fonctionne le tri par sélection ?

On cherche le plus petit élément de la partie non triée et on l'échange avec l'élément au début de cette partie. On recommence ensuite avec le reste du tableau.

Quelle est la différence avec le tri par insertion ?

Le tri par insertion considère les éléments un par un et les insère à leur place correcte parmi les éléments déjà triés, un peu comme on range des cartes dans sa main.

Pourquoi utiliser des jeux de cartes pour enseigner le tri ?

La manipulation physique permet de ralentir le processus de pensée et de décomposer chaque comparaison et chaque échange. Cela rend les boucles imbriquées concrètes : la boucle externe choisit la carte, la boucle interne cherche sa place ou le minimum.

Qu'est-ce qu'un invariant de boucle ?

C'est une propriété qui reste vraie à chaque étape de l'algorithme. Pour le tri, c'est souvent le fait que la partie gauche du tableau est déjà triée. Cela sert à prouver que l'algorithme fonctionne correctement.