Comment fonctionne le tri par sélection ?

Réponse courte

À chaque étape, le tri par sélection cherche le plus petit élément dans la partie encore non triée, puis l’échange avec la première case de cette partie. Le préfixe trié s’allonge jusqu’à ce que tout le tableau soit rangé.

Comprendre

Choisir le minimum restant

Le tableau est séparé en un préfixe déjà rangé et une partie restante. À l’indice i, on examine toutes les cases de i à la fin pour repérer le minimum, puis on échange ce minimum avec la valeur en position i. L’échange se fait après la recherche complète.

Suivre les étapes

Pour [6, 4, 7, 2, 5], le premier minimum est 2 ; l’échange avec 6 donne [2, 4, 7, 6, 5]. À l’étape suivante, le minimum des cases restantes est 4, déjà à sa place. Puis 5 est choisi parmi [7, 6, 5] : le tableau devient [2, 4, 5, 6, 7]. Chaque étape fixe une nouvelle case du préfixe.

Justifier l’arrêt et le coût

Au début d’une étape, le préfixe contient les plus petites valeurs dans le bon ordre. L’ajout du minimum suivant conserve cette propriété. Quand il ne reste qu’une case, le tableau est trié. Pour n valeurs, les comparaisons sont (n − 1) + (n − 2) + … + 1. Avec cinq valeurs, cela en fait 4 + 3 + 2 + 1 = 10, que le tableau initial soit déjà rangé ou non.

Deux pièges de trace

Échanger la première valeur plus petite rencontrée ne garantit pas de placer le minimum : il faut terminer le balayage de la partie restante avant l’échange. Ne confonds pas non plus le nombre d’échanges avec le nombre de comparaisons ; une étape peut ne rien déplacer tout en ayant comparé plusieurs valeurs.

Étapes

  1. Considère la partie qui commence à l’indice i comme non triée.
  2. Parcours-la pour mémoriser l’indice de sa plus petite valeur.
  3. Échange cette valeur avec celle située à l’indice i, puis passe à l’indice suivant.

Exemples

  • Avec [6, 4, 7, 2, 5], la première étape échange 6 et 2 et produit [2, 4, 7, 6, 5].
  • À l’étape suivante de [2, 4, 7, 6, 5], le minimum du suffixe [4, 7, 6, 5] est 4 ; aucun changement n’est nécessaire.
  • Pour 5 éléments, la sélection effectue 4 + 3 + 2 + 1 = 10 comparaisons entre valeurs.

Pièges fréquents

  • Échanger pendant la recherche dès qu’une valeur plus petite apparaît peut déplacer un candidat qui n’est pas le minimum final de toute la partie restante.
  • Un tableau déjà trié ne supprime pas les comparaisons : la sélection examine encore chaque partie restante pour confirmer son minimum.

Pourquoi ça marche

Le minimum choisi est inférieur ou égal à toutes les valeurs qui restent ; le placer ensuite à la fin du préfixe trié conserve l’ordre global.

Et maintenant ?

Questions proches

← Toutes les questions-réponses