Tri par sélection
Tri par sélection
Il s’agit d’un tri naïf qui consiste à parcourir la liste afin de chercher le minimum et de l’échanger avec le terme de gauche.
I. Principe de l’algorithme
On considère la liste T suivante :
T = [4, 12, 5, 8, 9, 6, 13, 3]
L’étape 0 consiste à chercher le minimum sur T[0:8] et à l’échanger avec T[0].
A l’issue de cette étape, la liste T sera alors [3, 12, 5, 8, 9, 6, 13, 4].
L’étape 1 consiste à chercher le minimum de la liste mais en ne tenant plus compte de la première valeur, et en cherchant donc dans T[1:8] puis d’échanger le minimum avec T[1].
La liste transformée est alors [3, 4, 5, 8, 9, 6, 13, 12].
II. Algorithme de tri par sélection
Pour écrire l’algorithme du tri, on commence par écrire une fonction permettant de renvoyer la position de la valeur du minimum de T compris entre a et b.
def imin(T, a, b):
imin = a
for i in range(a + 1, b):
if T[i] < T[imin]: #dès lors qu’une valeur est inférieure à la valeur d’indice imin,
imin prend comme nouvelle valeur l’indice de la valeur plus petite
imin = i
return imin
On définit à présent la fonction effectuant le tri par sélection.
def triselect(T):
N = len(T)
for i in range(N - 1):
j = imin(T, i, N) #on regarde le minium sur [0:8] puis sur [1:8],…
T[i], T[j] = T[j], T[i] #on échange les valeurs d’indices i (qui est la valeur non triée la plus à gauche) et j. return T
La liste T ainsi retournée sera donc classée et triée de la plus petite à la plus grande valeur.
III. Complexité de l’algorithme
Pour calculer la complexité de l’algorithme, on compte tout d’abord le nombre de comparaisons nécessaires pour effectuer l’algorithme.
Les comparaisons sont faites dans la fonction imin et sont effectuées une seule fois par passage dans la boucle.
Pour la recherche du premier minimum, le programme passe N – 1 fois dans la boucle : il y a donc N – 1 comparaisons.
Pour la recherche du deuxième minimum, il y a N – 2 comparaisons.
Ainsi, lors de l’exécution de l’algorithme, il y a $ N – 1 + N – 2 + … + 2 + 1 = dfrac{N(N-1)}{2} approx N^2$ (lorsque $N$ devient grand) comparaisons.
On s’intéresse ensuite au nombre d’affectations.
Pour chaque passage dans la boucle de la fonction triselect, on compte 3 affectations. En effectuant $N$ fois la boucle, il y a donc $3N$ affectations.
On remarquera que l’on ne compte par l’affectation N = len(T), comptant pour une affectation, qui est négligeable lorsque $N$ devient grand. (Si $N = 1000$, on s’accordera à dire que $3N = 3000$ et $3N + 1 = 3001$ sont du même ordre de grandeur.).
Il faut à présent regarder le nombre d’affectations dans la fonction imin. On regarde dans le pire des cas, c’est à dire lorsque la liste est triée dans l’ordre décroissant : il faut donc affecter à imin chaque indice à chaque passage dans la boucle.
Lors de la première recherche du minimum, il y a donc N – 1 affectations, puis N – 2 lors de la recherche du deuxième, … Au total, il y a donc $N – 1 + N – 2 + … + 2 + 1 = dfrac{N(N-1)}{2} approx N^2$ (quand $N$ devient grand) affectations.
Au final, la complexité est $dfrac{N(N-1)}{2} + 3N + dfrac{N(N-1)}{2} approx k N^2$ avec $k$ une constante, quand $N$ est grand.
On dira alors que la complexité est en $mathcal{O}(N^2)$.