Technologie · 3ème · Algorithmique et Programmation Avancée · 1er Trimestre

Introduction aux Algorithmes de Tri

Les élèves découvrent et comparent des algorithmes de tri simples comme le tri par sélection ou le tri à bulles.

• Programmes Officiels
• MEN: Cycle 4 - Notions d'algorithmique et de programmation

À propos de ce thème

Les algorithmes de tri sont un sujet classique et fondamental de l'algorithmique en 3ème. Les élèves découvrent que trier une liste n'est pas une opération triviale : il existe de nombreuses stratégies, chacune avec ses forces et ses faiblesses. Le tri par sélection (chercher le minimum et le placer au début, puis recommencer) et le tri à bulles (comparer les éléments voisins et les échanger si nécessaire, en plusieurs passages) sont les deux algorithmes étudiés à ce niveau.

Ce sujet correspond directement aux notions d'algorithmique du cycle 4. L'intérêt pédagogique est double : comprendre la logique pas à pas de chaque algorithme, et comparer leur efficacité sur des jeux de données de tailles différentes. Les élèves découvrent qu'un algorithme simple à comprendre (comme le tri à bulles) n'est pas forcément le plus rapide. Les simulations avec des cartes physiques ou des files d'élèves à trier par taille sont particulièrement efficaces car elles rendent chaque comparaison et chaque échange visibles et comptables.

Questions clés

1. Comparez l'efficacité de deux algorithmes de tri différents pour un petit ensemble de données.
2. Expliquez les étapes clés d'un algorithme de tri par sélection.
3. Prédisez le comportement d'un algorithme de tri à bulles sur une liste déjà triée.

Objectifs d'apprentissage

• Comparer l'efficacité temporelle du tri par sélection et du tri à bulles sur des ensembles de données de tailles variées.
• Expliquer les étapes séquentielles de l'algorithme de tri par sélection pour ordonner une liste.
• Démontrer le fonctionnement de l'algorithme de tri à bulles en identifiant les comparaisons et échanges nécessaires.
• Analyser la complexité d'un algorithme de tri en comptant le nombre d'opérations (comparaisons, échanges) pour une liste donnée.

Avant de commencer

Introduction aux structures de données : listes et tableaux

Pourquoi : Les élèves doivent comprendre ce qu'est une liste et comment accéder à ses éléments pour pouvoir les trier.

Concepts de base de l'algorithmique : séquences et boucles

Pourquoi : Les algorithmes de tri utilisent des séquences d'instructions et des répétitions (boucles) pour parcourir et manipuler les listes.

Vocabulaire clé

Tri par sélection	Algorithme qui consiste à trouver répétitivement le plus petit élément non trié et à le placer au début de la partie triée de la liste.
Tri à bulles	Algorithme qui parcourt la liste plusieurs fois, comparant les éléments adjacents et les échangeant s'ils sont dans le mauvais ordre, jusqu'à ce que la liste soit triée.
Comparaison	Opération qui évalue la relation entre deux éléments (par exemple, lequel est le plus grand ou le plus petit).
Échange	Opération qui consiste à permuter la position de deux éléments dans une liste.
Ensemble de données	Une collection d'éléments, souvent une liste de nombres ou d'objets, qui doit être triée.

Attention à ces idées reçues

Idée reçue courante

Le tri à bulles est un bon algorithme car il est facile à comprendre.

Ce qu'il faut enseigner à la place

Facilité de compréhension et efficacité sont deux choses différentes. Le tri à bulles est excellent pour apprendre, mais très lent sur de grandes listes. Les exercices de comptage d'opérations montrent que pour 20 éléments, le tri à bulles peut nécessiter bien plus de comparaisons qu'un tri par sélection.

Idée reçue courante

Un seul passage suffit pour trier une liste avec le tri à bulles.

Ce qu'il faut enseigner à la place

Un passage ne fait 'remonter' que le plus grand élément à sa place. Il faut autant de passages qu'il y a d'éléments (dans le pire cas) pour que toute la liste soit triée. La simulation physique avec des élèves en ligne rend ce mécanisme de passages répétés très visible.

Idée reçue courante

Le tri par sélection et le tri par insertion, c'est la même chose.

Ce qu'il faut enseigner à la place

Le tri par sélection cherche le minimum dans la partie non triée et le place au bon endroit. Le tri par insertion prend chaque élément et le glisse à sa place dans la partie déjà triée. Les animations pas à pas montrent clairement la différence de stratégie entre ces deux approches.

Idées d'apprentissage actif

Jeu de simulation: Le Tri Humain

Dix élèves se mettent en ligne avec un numéro. La classe applique collectivement l'algorithme du tri par sélection : trouver le plus petit, l'envoyer au début, recommencer avec le reste. Puis on recommence avec le tri à bulles. La classe compte les déplacements dans chaque cas.

30 min·Classe entière

Cercle de recherche: Le Grand Comparatif

Chaque groupe reçoit le même jeu de 15 cartes dans le même ordre. Un groupe applique le tri par sélection, l'autre le tri à bulles. Ils comptent le nombre de comparaisons et d'échanges, puis remplissent un tableau comparatif. Les résultats sont mis en commun pour dégager des conclusions.

40 min·Petits groupes

Penser-Partager-Présenter: Le Tri à Bulles sur Liste Triée

L'enseignant pose la question : que se passe-t-il si on applique le tri à bulles à une liste déjà triée ? Les élèves tracent les étapes individuellement, comparent avec un voisin, et constatent que l'algorithme parcourt quand même toute la liste inutilement (ou détecte l'absence d'échanges en un seul passage selon la version optimisée).

15 min·Binômes

Rotation par ateliers: Visualiser les Algorithmes

Station 1 : Exécuter le tri par sélection pas à pas sur papier avec des barres à colorier à chaque étape. Station 2 : Programmer le tri à bulles en Scratch et observer l'animation. Station 3 : Comparer les compteurs d'opérations sur des listes de tailles 5, 10 et 20 pour observer comment le temps augmente.

45 min·Petits groupes

Liens avec le monde réel

• Les bibliothécaires utilisent des algorithmes de tri pour organiser les livres par titre, auteur ou genre dans les catalogues informatisés, permettant aux usagers de retrouver rapidement les ouvrages.
• Les plateformes de commerce électronique comme Amazon trient les résultats de recherche par pertinence, prix ou popularité pour aider les clients à trouver les produits qu'ils recherchent plus efficacement.
• Les logiciels de gestion de bases de données trient d'énormes quantités d'informations, par exemple pour classer les transactions financières par date ou par montant, afin de faciliter les analyses et les rapports.

Idées d'évaluation

Billet de sortie

Donnez aux élèves une liste de 5 nombres non triés. Demandez-leur d'écrire les étapes du tri par sélection pour cette liste et de compter le nombre de comparaisons effectuées. Ensuite, demandez-leur de prédire si le tri à bulles nécessiterait plus ou moins de comparaisons pour cette même liste.

Question de discussion

Présentez aux élèves deux listes de données : une petite (5 éléments) et une plus grande (20 éléments). Posez la question : 'Si vous deviez trier ces deux listes, lequel des deux algorithmes (tri par sélection ou tri à bulles) choisiriez-vous pour chacune, et pourquoi ? Justifiez votre choix en pensant au nombre d'opérations.'

Vérification rapide

Montrez une liste partiellement triée par l'algorithme à bulles. Demandez aux élèves d'identifier la prochaine paire d'éléments à comparer et d'expliquer s'ils seront échangés ou non, en se basant sur la règle du tri à bulles.

Questions fréquentes

Comment fonctionne le tri par sélection ?

On parcourt toute la liste pour trouver le plus petit élément, puis on le place en première position. On recommence avec le reste de la liste pour trouver le deuxième plus petit, et ainsi de suite. À chaque tour, un élément de plus est à sa place définitive.

Pourquoi le tri à bulles s'appelle-t-il ainsi ?

Parce que les plus grands éléments 'remontent' progressivement vers la fin de la liste, comme des bulles d'air qui montent dans l'eau. À chaque passage, l'élément le plus grand de la partie non triée atteint sa position finale en étant échangé avec ses voisins successifs.

Comment les simulations physiques facilitent-elles la compréhension des algorithmes de tri ?

En déplaçant physiquement des cartes ou des camarades, les élèves voient et comptent chaque comparaison et chaque échange. L'aspect répétitif des passages devient tangible, et la différence d'efficacité entre algorithmes se ressent dans le temps et l'effort nécessaires.

Existe-t-il des algorithmes de tri plus rapides que ceux étudiés en 3ème ?

Oui, des algorithmes comme le tri fusion ou le tri rapide sont bien plus efficaces sur de grandes listes. Ils seront étudiés au lycée en NSI. Les algorithmes de 3ème posent les bases de la réflexion sur l'efficacité et préparent à ces notions plus avancées.