Time and Space Complexity

Complexité temporelle :

• Cas le meilleur, moyen et le pire : O(n²)
  • Le tri par sélection (Selection Sort) parcourt toujours l'intégralité de la partie non triée pour trouver le minimum, même si le tableau est déjà trié. Le nombre de comparaisons ne dépend pas de l'ordre d'entrée.

Complexité spatiale :

• O(1)
  • Le tri par sélection est un algorithme « in-place » (sur place). Il réorganise les éléments en utilisant seulement une quantité constante de mémoire supplémentaire, quelle que soit la taille de l'entrée.

Résumé :

• Le tri par sélection est simple et économe en mémoire.
• Il effectue peu d'échanges (au plus n-1), ce qui est utile lorsque les écritures sont coûteuses.
• Sa complexité temporelle quadratique en fait un mauvais choix pour les grands ensembles de données, où des algorithmes comme le tri fusion (Merge Sort) ou le tri rapide (Quick Sort) sont préférés.