Le tri par sélection

Choisir le minimum restant

Au passage d’indice i, les cases avant i sont déjà à leur place définitive. On cherche l’indice du minimum parmi les cases allant de i à la fin. Un échange place ce minimum en i. On poursuit avec i + 1. Pour [5, 2, 4, 1], le premier minimum est 1 à l’indice 3 : l’échange produit [1, 2, 4, 5].

Le tableau peut sembler déjà trié après un échange, mais cette version de l’algorithme poursuit ses recherches. Il ne suffit pas d’observer l’apparence des données pour modifier une procédure sans analyser ce qui garantit son résultat.

Pour visualiser le mécanisme, placez une frontière avant la case i. À gauche, on ne touche plus aux valeurs. À droite, on effectue une recherche complète, même si le premier candidat semble petit. Sur [2,3,6,8,5] au passage 1, le minimum restant est déjà 3 : la frontière avance sans échange effectif. Une absence d’échange ne signifie donc pas une absence de travail.

Mémoriser un indice, pas déplacer à chaque comparaison

La recherche conserve l’indice du plus petit élément rencontré dans la zone non triée. Quand une valeur plus petite apparaît, on modifie cet indice. L’échange n’a lieu qu’après la fin de la recherche. Cette séparation rend l’algorithme lisible : comparer sélectionne le candidat ; échanger le place.

On initialise m à i puisque le candidat initial appartient à la zone étudiée. Commencer toujours à zéro risquerait de reprendre un élément déjà placé. Une égalité peut conserver le premier candidat en utilisant strictement < ; le tri restera correct en présence de doublons.

def tri_selection(t):
    for i in range(len(t) - 1):
        m = i
        for j in range(i + 1, len(t)):
            if t[j] < t[m]:
                m = j
        t[i], t[m] = t[m], t[i]

Pourquoi le résultat est trié

Un invariant décrit le début de chaque passage : le préfixe avant i est trié et contient les i plus petites valeurs du tableau initial, avec leurs répétitions. Initialement, ce préfixe est vide, donc la propriété est vraie. Placer le minimum restant ajoute exactement la prochaine valeur attendue et conserve l’ordre.

Après n - 1 passages, une seule valeur reste ; elle est nécessairement la dernière. Les échanges préservent les données : aucune valeur n’est créée ou supprimée. Il faut ces deux idées pour prouver un tri : l’ordre du résultat et la conservation du contenu initial.

La conservation porte sur les occurrences, pas uniquement sur l’ensemble des valeurs distinctes. Les tableaux [1,1,3] et [1,3,3] ont le même ensemble de valeurs, mais pas le même contenu à trier. Un échange conserve chaque occurrence. Cette propriété reste vraie à tous les passages, y compris lorsque deux valeurs égales se trouvent à des positions différentes.

Un coût indépendant de l’ordre initial

La première recherche compare n - 1 candidats au minimum courant, la suivante n - 2, jusqu’à 1. Le total est n(n - 1) / 2 comparaisons de valeurs. Il est quadratique et reste identique sur un tableau déjà trié dans cette version. Les boucles sont bornées, donc elles se terminent.

Le nombre d’échanges effectifs peut être inférieur au nombre de passages lorsqu’un minimum est déjà bien placé. Il ne faut pas confondre ce nombre avec celui des comparaisons. Dans l’atelier, un passage dont m = i ne compte pas comme échange effectif, même si le code peut exécuter une affectation équivalente.

Exemple complet avec doublons

Trions [4,2,4,1]. Au passage 0, les trois comparaisons sélectionnent l’indice 3 ; l’échange produit [1,2,4,4]. Au passage 1, deux comparaisons laissent le minimum à l’indice 1. Au passage 2, une comparaison entre les deux 4 conserve l’indice 2 avec le test strict. Le résultat est trié après six comparaisons et un seul échange effectif.

Les répétitions ne nécessitent aucune suppression. La deuxième occurrence de 4 reste présente. Un candidat sélectionné au premier passage peut provenir de la toute dernière case : ne cherchez donc pas seulement un voisin plus petit. Le tri par sélection cherche le minimum de tout le suffixe, puis réalise un unique placement. Le tableau de trace doit indiquer la zone cherchée, l’indice retenu et l’état obtenu après l’échange.

Comparer la quantité de travail et l’ordre des égaux

Sur quatre valeurs, les tailles des recherches sont toujours 3, 2 et 1 comparaisons. Le total vaut 6 pour un tableau croissant, décroissant ou rempli de répétitions. En revanche, le nombre d’échanges effectifs dépend du placement initial. Ainsi, le tableau croissant conserve zéro échange mais paie tout de même les recherches.

Approfondissement : si les valeurs portent aussi des étiquettes, le tri par sélection classique ne garantit pas l’ordre initial des ex æquo. Avec [(2,A),(2,B),(1,C)], l’échange du premier et du dernier donne [(1,C),(2,B),(2,A)]. Les deux clés 2 ont inversé leur ordre. Le tri reste correct sur les clés, mais il n’est pas stable. Cette propriété supplémentaire doit être distinguée de l’ordre numérique et de la conservation des éléments.

De la compréhension à l’autonomie

À vous de résoudre

Cherchez d’abord par vous-même. Vérifiez les résultats demandés, utilisez les indices si nécessaire, puis comparez votre méthode à la correction.

Les erreurs qui méritent un détour

Échanger dès qu’une valeur plus petite apparaît.

Cela correspond à une autre procédure. Dans la sélection étudiée, on finit d’abord la recherche du minimum.

Dire « la première partie est triée » sans préciser son contenu.

Pour garantir l’extension du tri, elle doit contenir les plus petites valeurs de tout le tableau.

Cette notion au bac

Retrouvez ces idées dans un sujet complet, avec des indices, une correction expliquée et des ateliers.

• Bac 2026 · Centres étrangers groupe 1 · Jour 1 : Classement d’athlètes : tri par sélection et ABR
• Bac 2025 · Métropole · Remplacement jour1 - 9 septembre 2025 : Papillons : SQL, tri par taille et recherche d’une séquence ADN

Le prochain pas

• Le tri par insertion
• Prouver la correction et la terminaison d’un algorithme
• Comprendre le coût d’un algorithme

Retrouver le catalogue de Première

Ce chapitre s’appuie sur le programme officiel de Première (PDF, nouvel onglet). Les explications et exercices sont proposés pour l’apprentissage.