Un algorithme de tri par sélection est un algorithme qui permet de trier une liste dans l’ordre croissant. Tout en conservant la même structure, c'est-à-dire que le programme conserve la liste d’origine au lieu d’en créé une nouvelle.

Dans une Liste à n élément (d’indice 0 à n-1, car on commence par 0 et non par 1), l’algorithme cherche le plus petit entier de la liste et l'échange avec l’élément d’indice 0.

Rechercher le second plus petit élément du tableau, et l'échanger avec l'élément d'indice 1

Continuer de cette façon jusqu'à ce que le tableau soit entièrement trié.

Le rouge est ici le minimum et le bleu le “curseur” qui vérifie s'il est plus petit que le minimum enregistré

"""
Algorithme de tri par sélection
"""
 
# Initialisation de Variables
t = [1,6,9,3,2,0,7,5,8,4] # Tableau d'entiers
 
"""
Objectif : Algorithme de tri par sélection
Entrée : Liste
Sortie : Liste trié
"""
def tri_select(t):
    for i in range(len(t)-1):
        min = i # min = l'indice du premier élément de la liste non triée
        for j in range(i,len(t)): # Pour la suite de la liste non triée
            if t[j] < t[min] : # si l'élément à l'indice j est plus petit que celui a l'indice min 
                min = j # l'indice min devient alors l'indice j
        t[min],t[i] = t[i],t[min] # échange l'élément à l'indice min avec celui de l'indice i 
    return t
 
#Programme principal
 
print(t)
# [1, 6, 9, 3, 2, 0, 7, 5, 8, 4]
 
print(tri_select(t))
# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

La complexité, c'est le nombre de fois que va “boucler” notre programme en fonction de la taille de l'entrée. ex : donner la taille d'une liste sans utiliser la fonction “len()” serait de complexite O(n).

Dans notre cas, la complexité est de O(n²) on appelle cela une complexité quadratique, c'est-à-dire que le nombre d'oppération est proportionnelle au carré de l'entrée