Éditeur Python
Le tri sélection
Un exemple de tri sélection
Principe
Le tri sélection est un algorithme de tri simple et intuitif. Il consiste à rechercher le minimum de la liste et à le placer en première position, puis à répéter le processus sur le reste de la liste.
Cet algorithme est simple à mettre en oeuvre, mais il est peu efficace pour des listes de grande taille.
Détaillons un peu l'algorithme. Le tri par sélection fonctionne en divisant le tableau en deux parties : une sous-liste triée au début et une sous-liste non triée qui occupe le reste du tableau. Initialement, la sous-liste triée est vide, tandis que la sous-liste non triée contient tous les éléments. L'algorithme répète les étapes suivantes jusqu'à ce que la sous-liste non triée soit vide :
- Sélectionner le plus petit élément de la sous-liste non triée.
- Échanger cet élément avec le premier élément de la sous-liste non triée.
- Considérer cet élément comme faisant désormais partie de la sous-liste triée.
Ce processus est répété pour chaque élément du tableau, en déplaçant à chaque fois la "frontière" entre la sous-liste triée et non triée d'un élément vers la droite.
À faire vous même
Écrivez une fonction
tri_par_selection
qui trie un tableau d'entiers en utilisant l'algorithme de tri par sélection.
Testez votre fonction avec un tableau d'entiers aléatoires.
Implémentation en Python
def tri_par_selection(arr):
# Parcourir tous les éléments du tableau
for i in range(len(arr)):
# Trouver le minimum dans la sous-liste non triée
min_idx = i
for j in range(i+1, len(arr)):
if arr[min_idx] > arr[j]:
min_idx = j
# Échanger l'élément trouvé avec le premier élément de la sous-liste non triée
arr[i], arr[min_idx] = arr[min_idx], arr[i]
Notez bien qu'il n'est pas nécessaire d'avoir un return dans la fonction,
car les modifications sont faites directement sur le tableau passé en argument
(c'est un paramètre mutable en Python).
Utilisation
Pour utiliser cette fonction de tri, il suffit de passer un tableau (ou une liste en Python) d'éléments à la fonction. Par exemple :
from random import randint
mon_tableau = [randint(0, 100) for _ in range(10)]
print("Le tableau initial est :", mon_tableau)
tri_par_selection(mon_tableau)
print("Le tableau trié est :", mon_tableau)Cette instruction affichera le tableau trié en ordre croissant.
Preuve de la Correction du Tri par Sélection
Pour prouver la correction de l'algorithme de tri par sélection, nous devons démontrer deux choses : premièrement, que l'algorithme produit une sortie qui est une permutation de l'entrée (intégrité des données) et deuxièmement, que cette sortie est triée dans l'ordre désiré (croissant, par exemple).
Intégrité des données
À chaque itération, l'algorithme sélectionne le plus petit élément de la sous-liste non triée et l'échange avec l'élément à la position actuelle de l'itération. Cela signifie qu'aucun élément n'est créé ou supprimé, mais simplement déplacé. Ainsi, la sortie est une permutation des entrées.
Sortie triée
L'invariant de boucle du tri par sélection est que, pour chaque itération i, les éléments de la position 0 à i-1 dans le tableau sont les éléments les plus petits du tableau original et sont triés entre eux. Cet invariant est maintenu car, à chaque itération, le plus petit élément de la sous-liste non triée est placé à la fin de la sous-liste triée. Quand il n'y a plus d'éléments dans la sous-liste non triée (c'est-à-dire que toute la liste est considérée comme triée), l'invariant garantit que la liste entière est triée.
Preuve de la Complétion
La complétion de l'algorithme est garantie par le fait que le nombre d'itérations est fini et déterminé par la taille n du tableau. Pour un tableau de taille n, il y aura exactement n itérations de la boucle externe, car à chaque itération, un élément est retiré de la sous-liste non triée et ajouté à la sous-liste triée, diminuant la taille de la sous-liste non triée jusqu'à ce qu'elle soit vide.
Évaluation de la Complexité Quadratique
La complexité temporelle de l'algorithme de tri par sélection peut être évaluée en considérant le nombre d'opérations effectuées. Pour un tableau de taille n, la première itération de la boucle externe nécessite n-1 comparaisons, la deuxième nécessite n-2 comparaisons, et ainsi de suite, jusqu'à la dernière itération qui nécessite 1 comparaison. Le nombre total de comparaisons \(C\) peut être calculé comme suit :
$$C = (n-1) + (n-2) + ... + 1 = \frac{n(n-1)}{2}$$
Cette expression est de l'ordre de \(O(n^2)\), ce qui montre que la complexité temporelle du tri par sélection est quadratique.