sorting activity

Imaginez huit cartes mélangées, rouges ou jaunes, rondes ou carrées. On peut mettre d'un côté celles qui sont rouges et de l'autre celles qui ne le sont pas. On peut aussi les ranger par numéro. Ces deux gestes portent couramment le nom de tri, mais ils ne produisent pas le même résultat.

Dans une activité scolaire, le résultat compte autant que la manière de s'y prendre. Un élève qui rassemble d'abord les couleurs ne mobilise pas exactement la même idée qu'un élève qui compare d'abord les formes. Observer ces choix renseigne sur sa façon de classifier.

L'expression activité de tri recouvre trois cadres. Dans le cadre mathématique de la source, un attribut est traduit par un prédicat, c'est-à-dire une propriété vraie ou fausse pour chaque élément. Les éléments qui vérifient le prédicat forment un sous-ensemble ; les autres forment son complémentaire. Ces deux sous-ensembles sont disjoints et leur réunion redonne l'ensemble initial : ils constituent une partition dès lors que les parts vides sont omises.

Avec plusieurs prédicats binaires, chaque élément est décrit par une suite de réponses « oui » ou « non ». Pour un nombre n de prédicats, il existe au plus $2^{n}2^n$ combinaisons de réponses. Ce maximum n'est atteint que si toutes les combinaisons sont effectivement représentées ; dans ce sens opérationnel, les prédicats sont dits indépendants lorsque les $2^{n}2^n$ combinaisons complètes de réponses sont effectivement réalisées.

En informatique, trier signifie plutôt ordonner des éléments selon une relation de comparaison. Le tri par insertion place progressivement chaque élément dans une partie déjà ordonnée ; le tri rapide sépare les éléments autour d'un pivot avant de traiter les groupes obtenus. En didactique, enfin, l'activité de tri est la tâche proposée à l'élève, tandis que la classification est la solution experte attendue. L'observateur étudie les critères et les connaissances que les passages d'un objet au suivant rendent plausibles.

Prenons huit cartes numérotées, présentées dans l'ordre 7, 2, 5, 4, 1, 8, 3, 6. Les cartes 1 et 5 sont des ronds rouges ; 2 et 6, des ronds jaunes ; 3 et 7, des carrés rouges ; 4 et 8, des carrés jaunes.

Données : huit cartes ; deux couleurs, rouge et jaune ; deux formes, ronde et carrée ; deux cartes pour chaque couple couleur-forme. La figure associée montre les quatre groupes obtenus en croisant les deux attributs.

1. Avec le prédicat « la carte est rouge », on obtient {1, 3, 5, 7} et son complémentaire {2, 4, 6, 8}.
2. En ajoutant le prédicat « la carte est carrée », on croise deux réponses binaires et l'on obtient quatre groupes : {1, 5}, {2, 6}, {3, 7} et {4, 8}.
3. En tri informatique croissant, les mêmes cartes deviennent 1, 2, 3, 4, 5, 6, 7, 8.
4. Dans une classe, demander à l'élève d'expliquer chaque déplacement aide à repérer s'il suit la couleur, la forme ou le numéro.

Le contrôle est refaisable : chaque carte apparaît une seule fois dans les quatre groupes, et leur réunion contient bien les huit cartes. Le nombre de groupes vaut ici $2^2=42^2=4$, car les quatre combinaisons de couleur et de forme sont présentes.

Pour répartir des objets selon une propriété oui/non, on formule d'abord un prédicat testable. Sur les huit cartes, « est rouge » convient ; « est joli » ne convient pas sans critère partagé. Si plusieurs valeurs sont possibles sans se réduire à oui/non, une classification multicatégorie est plus directe.

Pour obtenir une suite ordonnée, on choisit une clé et un sens de comparaison. Les numéros des cartes donnent 1 à 8 en ordre croissant. Une partition par couleur serait préférable si l'objectif était seulement de constituer des lots, et non de déterminer un premier et un dernier élément.

Pour analyser une démarche d'élève, on conserve la trace des déplacements et on lui demande d'expliciter son critère. Le classement final seul ne suffit pas : deux stratégies peuvent produire les mêmes quatre groupes.

Partition et ordre. Une partition constitue des groupes disjoints dont la réunion redonne l'ensemble ; un ordre indique quels éléments viennent avant les autres. Séparer les cartes rouges des jaunes ne dit pas si la carte 3 précède la carte 7.

Tri et classification. Dans l'usage didactique retenu ici, le tri est l'activité de l'élève et la classification est la structure experte visée. Un élève peut déplacer les cartes une à une selon une stratégie hésitante tout en aboutissant finalement aux quatre classes attendues.

Tri et dichotomie. Un tri conserve les groupes ou ordonne toute la collection. Une dichotomie divise en deux parties complémentaires puis, dans une recherche, retient la partie où poursuivre. Séparer les cartes rouges des jaunes garde les deux lots ; une étape dichotomique n'en conserve qu'un pour réduire la recherche.

Une combinaison peut manquer. Deux prédicats donnent au plus quatre intersections, pas toujours quatre parts non vides. Si aucune carte n'était un carré jaune, cette intersection serait vide et ne compterait généralement pas comme une part de la partition.

Les attributs ne sont pas toujours indépendants. Si toutes les cartes carrées étaient rouges, connaître la forme imposerait déjà la couleur. Le symptôme est l'impossibilité de réaliser certaines suites de réponses ; pour un nombre n de prédicats, il faut alors annoncer moins de $2^{n}2^n$ groupes possibles.

Des égalités peuvent subsister dans un ordre. Deux éléments peuvent avoir la même clé de comparaison. Il faut préciser un second critère ou choisir un tri stable, qui conserve entre éléments ex æquo l'ordre qu'ils avaient avant le tri.

Une stratégie ne se lit pas directement dans le résultat. Les quatre groupes corrects n'établissent pas à eux seuls les connaissances employées par l'élève. Il faut confronter le résultat à l'ordre des gestes et aux explications données, sans attribuer une règle sur un seul déplacement.

Le glossaire algorithme de tri approfondit les méthodes qui transforment une collection en suite ordonnée.

La relation d'ordre précise la comparaison nécessaire pour décider quel élément doit précéder un autre.

La Dichotomie approfondit la division répétée en deux parties complémentaires, notamment pour localiser le zéro d'une fonction.