Numérique et Sciences Informatiques > Algorithmique : Tris et Recherche > Algorithmes de Tri Élémentaires > Tri par sélection

Le Tri par Sélection : Une Méthode de Tri Simple et Efficace

Comprendre le tri par sélection, un algorithme de tri simple, étape par étape. Découvrez son fonctionnement, ses avantages, ses inconvénients et sa complexité.

Introduction au Tri par Sélection

Le tri par sélection est un algorithme de tri simple et intuitif. Il fonctionne en sélectionnant à chaque étape le plus petit (ou le plus grand, selon l'ordre souhaité) élément restant dans la partie non triée du tableau, et en l'échangeant avec l'élément situé au début de cette partie non triée. Cela construit progressivement la partie triée du tableau, en partant du début.

Principe de Fonctionnement

L'algorithme du tri par sélection se déroule en plusieurs étapes :

  1. Recherche du Minimum : On recherche le plus petit élément dans la partie non triée du tableau.
  2. Échange : On échange cet élément avec le premier élément de la partie non triée. Cela place le plus petit élément à sa position correcte dans la partie triée.
  3. Itération : On répète les étapes 1 et 2 pour le reste du tableau non trié, en incrémentant l'index du début de la partie non triée.

Ce processus se poursuit jusqu'à ce que tout le tableau soit trié. Après chaque itération, la partie triée du tableau s'agrandit d'un élément.

Exemple Détaillé

Prenons l'exemple du tableau suivant : [64, 25, 12, 22, 11]

Étape 1 :

  • On recherche le minimum dans tout le tableau. Le minimum est 11, situé à l'indice 4.
  • On échange 11 avec 64 (le premier élément). Le tableau devient : [11, 25, 12, 22, 64]

Étape 2 :
  • On recherche le minimum dans la partie non triée (à partir de l'indice 1). Le minimum est 12, situé à l'indice 2.
  • On échange 12 avec 25 (l'élément à l'indice 1). Le tableau devient : [11, 12, 25, 22, 64]

Étape 3 :
  • On recherche le minimum dans la partie non triée (à partir de l'indice 2). Le minimum est 22, situé à l'indice 3.
  • On échange 22 avec 25 (l'élément à l'indice 2). Le tableau devient : [11, 12, 22, 25, 64]

Étape 4 :
  • On recherche le minimum dans la partie non triée (à partir de l'indice 3). Le minimum est 25, situé à l'indice 3.
  • Comme 25 est déjà à sa place, on ne fait pas d'échange. Le tableau reste : [11, 12, 22, 25, 64]

Le tableau est maintenant trié.

Pseudo-Code

Voici le pseudo-code de l'algorithme du tri par sélection :

POUR i DE 0 À longueur(tableau) - 2 FAIRE min_index = i POUR j DE i + 1 À longueur(tableau) - 1 FAIRE SI tableau[j] < tableau[min_index] ALORS min_index = j FIN SI FIN POUR SI min_index != i ALORS ECHANGER tableau[i] et tableau[min_index] FIN SI FIN POUR

Complexité

La complexité du tri par sélection est de O(n^2) dans tous les cas (meilleur, moyen et pire cas). Cela signifie que le temps d'exécution de l'algorithme croît quadratiquement avec la taille du tableau à trier. Il n'est donc pas très efficace pour les grands tableaux. Il réalise peu d'échanges ce qui peut être un avantage si les écritures sont coûteuses.

Avantages et Inconvénients

Avantages :

  • Simple à comprendre et à implémenter.
  • Efficace pour les petits tableaux.
  • Effectue peu d'échanges.

Inconvénients :
  • Inefficace pour les grands tableaux (complexité O(n^2)).
  • Ne s'adapte pas aux données déjà partiellement triées.

Ce qu'il faut retenir

  • Le tri par sélection est un algorithme de tri simple qui fonctionne en sélectionnant le minimum (ou maximum) à chaque itération.
  • Sa complexité est de O(n^2), ce qui le rend inefficace pour les grands ensembles de données.
  • Il est facile à implémenter et effectue peu d'échanges, ce qui peut être avantageux dans certains contextes.
  • Étapes clés : Recherche du minimum, échange avec l'élément courant, itération sur le reste du tableau.

← Le Tri par Insertion : Un Guide Complet Le Tri à Bulles: Comprendre et Implémenter Facilement →

FAQ

  • Quand utiliser le tri par sélection ?

    Le tri par sélection est approprié pour les petits ensembles de données ou lorsque la simplicité de l'algorithme est plus importante que l'efficacité.
  • Le tri par sélection est-il un algorithme de tri stable ?

    Non, le tri par sélection n'est pas un algorithme de tri stable. Cela signifie que l'ordre relatif des éléments égaux peut être modifié lors du tri.
  • Comment améliorer le tri par sélection ?

    Il n'y a pas d'améliorations significatives à apporter au tri par sélection en termes de complexité. D'autres algorithmes comme le tri fusion ou le tri rapide sont bien plus efficaces pour les grands ensembles de données.