Tri par sélection — Fiche NSI

Comment utiliser cette page

Cette page suit toujours le même plan : le principe en une phrase, les étapes dans l'ordre exact, une démonstration interactive, le code Python, puis le nombre de comparaisons et la complexité.

Utilisation de la démonstration

La démonstration avance uniquement quand vous cliquez sur « Suivant » ou « Précédent » : rien ne bouge tout seul. Un bouton « Lecture automatique » est disponible si vous préférez laisser les étapes défiler seules, à une vitesse que vous choisissez.

1. Vocabulaire à connaître avant de commencer

Chaque mot ci-dessous est utilisé exactement dans ce sens dans toute la page.

Mot	Définition précise
Tableau	Une liste de valeurs numérotées à partir de l'indice 0.
Indice	Le numéro qui repère une case du tableau. Le premier indice est 0, pas 1.
Comparer deux valeurs	Regarder laquelle des deux est la plus petite (pour un tri croissant).
Échanger / permuter	Deux valeurs changent de case l'une avec l'autre, en une seule fois.
Sous-tableau trié	La partie du tableau, à gauche, qui est déjà dans le bon ordre à cette étape.
Itération	Un passage dans la boucle principale. On note i le numéro de l'itération.
Complexité	Une estimation du nombre d'opérations faites par l'algorithme, en fonction du nombre n de valeurs du tableau.

2. Le tableau d'exemple utilisé dans cette page

On utilise le tableau T, de 6 valeurs, pour la démonstration du tri par sélection :

Indice	0	1	2	3	4	5
Valeur T[i]	5	3	8	1	9	2

But de l'algorithme : transformer ce tableau, sur place, pour obtenir T = [1, 2, 3, 5, 8, 9], trié par ordre croissant.

3. Tri par sélection

3.1 — Principe, en une phrase

Principe

À chaque étape i, on cherche la plus petite valeur parmi les valeurs non encore triées, et on l'échange avec la valeur qui est à la position i.

3.2 — Les étapes, dans l'ordre exact

On part de l'indice i = 0.
On cherche, parmi les valeurs d'indice i à n-1, celle qui est la plus petite. On note i_min l'indice de cette valeur minimale.
On échange la valeur à l'indice i avec la valeur à l'indice i_min (même si i_min = i, l'échange ne change rien dans ce cas).
On passe à l'indice suivant : i = i + 1.
On répète les étapes 2 à 4 tant que i est inférieur à n - 1.

3.3 — Démonstration interactive

partie déjà triée position i (contour bleu) indice j en cours de comparaison i_min actuellement retenu

Étape 1 / 1

Lecture automatique Vitesse :

La ligne de code correspondant à l'étape en cours est surlignée ci-dessous.

3.4 — Code Python

def tri_selection(T):    """Trie le tableau T par ordre croissant (tri par sélection)."""    n = len(T)    for i in range(n - 1):        i_min = i        for j in range(i + 1, n):            if T[j] < T[i_min]:                i_min = j        T[i], T[i_min] = T[i_min], T[i]    return T# Jeu de données : le même exemple que la démonstration ci-dessusT = [5, 3, 8, 1, 9, 2]print(tri_selection(T))# Résultat affiché : [1, 2, 3, 5, 8, 9]

3.5 — Nombre de comparaisons et complexité

Le nombre de comparaisons ne dépend jamais de l'ordre initial des valeurs : c'est toujours n(n-1)/2 comparaisons pour un tableau de taille n.
Pour notre exemple (n = 6) : 6 × 5 / 2 = 15 comparaisons, dans tous les cas.
Le nombre d'échanges est faible : au maximum n - 1 échanges (un par étape).
Complexité : dans le meilleur cas comme dans le pire cas, le tri par sélection est en O(n²).

4. Comparaison avec le tri par insertion

Pour la démonstration interactive du tri par insertion et son détail complet, voir la fiche sur le tri par insertion.

Critère	Tri par sélection	Tri par insertion
Idée principale	Chercher le minimum, puis l'échanger	Décaler les valeurs pour insérer à la bonne place
Nombre de comparaisons	Toujours n(n-1)/2, quel que soit le tableau de départ	Variable : entre n-1 et n(n-1)/2 selon le tableau de départ
Meilleur cas (tableau déjà trié)	O(n²) — pas plus rapide	O(n) — beaucoup plus rapide
Pire cas	O(n²)	O(n²)
Nombre d'échanges / décalages	Au maximum n - 1 échanges	Peut aller jusqu'à n(n-1)/2 décalages
Quand le préférer	Quand échanger deux valeurs coûte cher, peu importe l'ordre initial	Quand le tableau est déjà presque trié

Prêt(e) pour la suite ? → Fiche sur le tri par insertion