date: 2023-10-16
Type: Cours
Projet: Blindcode
Cours: AlgorithmieTri par Sélection
Le tri par sélection est un autre algorithme simple de tri qui, comme le tri à bulles, est utile pour comprendre les principes fondamentaux du tri d'éléments dans un tableau. Dans ce chapitre, nous allons explorer le fonctionnement du tri par sélection et analyser sa complexité.
Le tri par sélection fonctionne en sélectionnant à chaque étape l'élément le plus petit (ou le plus grand, selon l'ordre de tri souhaité) parmi les éléments non triés du tableau, puis en l'échangeant avec l'élément à la position courante. L'algorithme répète ce processus pour chaque élément du tableau, en les triant un par un.
Voici un exemple de code en pseudo-code illustrant le tri par sélection :
FONCTION triSelection(tableau : TABLEAU) : TABLEAU
n : ENTIER <- LONGUEUR(tableau)
POUR i DE 0 À n-1 FAIRE
indiceMin : ENTIER <- i
POUR j DE i+1 À n-1 FAIRE
SI tableau[j] < tableau[indiceMin] ALORS
indiceMin <- j
FIN SI
FIN POUR
SI indiceMin != i ALORS
ÉCHANGER(tableau[i], tableau[indiceMin]) // Échange les éléments
FIN SI
FIN POUR
RETOURNER tableau
FIN FONCTION
La complexité temporelle du tri par sélection est généralement O(n^2) dans tous les cas, que le tableau soit déjà trié ou non. Cela signifie que le temps d'exécution augmente quadratiquement avec la taille du tableau. Dans le meilleur des cas, la complexité reste O(n^2), ce qui le rend moins efficace que d'autres algorithmes de tri.
La complexité spatiale est généralement O(1), car l'algorithme effectue des échanges en place, sans nécessiter de mémoire supplémentaire en fonction de la taille du tableau.
Tout comme le tri à bulles, le tri par sélection est rarement utilisé en pratique pour trier de grandes quantités de données en raison de sa lenteur. Il est principalement utilisé à des fins pédagogiques pour illustrer les concepts de base du tri. Des algorithmes plus efficaces, tels que le tri rapide (QuickSort) et le tri fusion (MergeSort), sont préférés pour trier efficacement de grands ensembles de données.
Malgré sa simplicité, le tri par sélection est un algorithme utile pour comprendre les principes du tri par comparaison et pour discuter des performances et des limites des différents algorithmes de tri.
créé le 2023-10-16 à 13:42