4.4 Tri par sélection⚓︎
Voici le lien du notebook associé.
1. Animation⚓︎
Considérons la liste [5, 4, 2, 1]
Voici le fonctionnement de l'algorithme :
2. Principe⚓︎
description de l'algorithme
Le travail se fait essentiellement sur les indices.
- du premier élément jusqu'à l'avant-dernier :
- on considère que cet élément est l'élément minimum, on stocke donc son indice dans une variable
indice_min. - on parcourt les éléments suivants, et si on repère un élément plus petit que notre mininum on met à jour notre
indice_min. - une fois le parcours fini, on échange l'élément de travail avec l'élément minimum qui a été trouvé.
- on considère que cet élément est l'élément minimum, on stocke donc son indice dans une variable
3. Implémentation de l'algorithme⚓︎
Tri par sélection 
def tri_selection(liste) :
for i in range(len(liste) - 1):
indice_min = i
for j in range(i + 1, len(liste)) :
if liste[j] < liste[indice_min]:
indice_min = j
liste[i], liste[indice_min] = liste[indice_min], liste[i]
Application :
4. Complexité de l'algorithme⚓︎
4.1 Étude expérimentale⚓︎
A l'aide du cours sur la complexité proposer sur le notebook associé, des mesures expérimentales pour déterminer la complexité du tri par insertion.
Nous allons fabriquer deux listes de taille 100 et 200 : Pour le tri par sélection, il n'y a pas cas plus défavorable comme dans le tri par insertion (cas de la liste triée dans l'ordre insère de celui recherché). Il faut pour chaque valeur du tableau, parcourir toutes les valeurs non triées.
4.2 Calcul du nombre d'opérations⚓︎
Dénombrons le nombre d'opérations, pour une liste de taille \(n\).
- boucle
for: elle s'exécute \(n-1\) fois. - deuxième boucle
forimbriquée : elle exécute d'abord \(n-1\) opérations, ..., puis 3, puis 2, puis 1.
On a donc : \(n-1+\dots+3+2+1=\dfrac{n \times (n-1)}{2}\)
Le terme de plus haut degré de l'expression \(\dfrac{n \times (n-1)}{2}\) est de degré 2 : le nombre d'opérations effectuées est donc proportionnel au carré de la taille des données d'entrée.
Ceci démontre que le tri par sélection est de complexité quadratique.
Vérification expérimentale
Insérez un compteur c dans votre algorithme pour vérifier le calcul précédent. On pourra renvoyer cette valeur en fin d'algorithme par un return c.
5. Preuve de l'algorithme⚓︎
5.1 Preuve de la terminaison de l'algorithme⚓︎
Est-on sûr que notre algorithme va s'arrêter ?
À l'observation du programme, constitué de deux boucles for imbriquées, il n'y a pas d'ambiguïté : on ne peut pas rentrer dans une boucle infinie. Le programme s'arrête forcément au bout de d'un nombre fixe d'opérations.
D'après nos calculs sur la complexité, ce nombre de tours de boucles est égal à \(\dfrac{n \times (n-1)}{2}\).
Ceci prouve que l'algorithme se terminera.
5.2 Preuve de la correction de l'algorithme⚓︎
Est-on sûr que notre algorithme va bien trier notre liste ?
Nous verrons la correction de l'algorithme de tri par insertion dans un autre cours.
6. Bonus : comparaison des algorithmes de tri⚓︎
Une jolie animation permettant de comparer les tris :
Issue de ce site.
7. Exercices_Algorithmes_de_tris⚓︎
Travail à réaliser sur le notebook Capytale du lien suivant: