Tri par sélection
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.
1) 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].
2) 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.
3) 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)$.
Tri par insertion
Tri par insertion
Il existe plusieurs tris différents : le tri par insertion en est un exemple.
On dispose de $n$ données à trier. Le principe de l’algorithme de tri est qu’à chaque étape, on suppose que les $k$ premières données sont triées et on place la $(k + 1)$-ième à sa juste place parmi les $k$ premières valeurs. On itère ensuite ce processus à l’ensemble de la liste.
On doit trier une liste de $n$ éléments. On donne l’algorithme ci dessous.
for $i$ from $0$ to $n-2$
$k leftarrow i + 1$
$new leftarrow L[k]$
while $new < L[k-1]$ and $k > 0$
$L[k] leftarrow L[k-1]$
$k leftarrow k-1$
$L[k] leftarrow new$
$new$ correspond à l’élément que l’on souhaite place lors de la $i$ème itération. On appelle aussi cet élément la clé.
La condition $k > 0$ permet d’éviter de sortir de la liste à gauche.
Afin d’améliorer la compréhension de l’algorithme, on propose une version littérale de l’algorithme.
Pour chaque valeur de $i$ variant de $0$ à $n-2$, on travaille sur la liste $L[0:i+1]$ pour placer $L[i+1]$ à sa juste place.
Pour ce faire, on compare $new$ aux données précédentes, en commençant par la donnée d’indice $i$. On remonte la liste jusqu’à trouver la bonne place entre deux données successives, l’une plus petite, l’autre plus grande. L’élément à trier peut être placé en début de liste.
On s’intéresse à présent sur la terminaison de cet algorithme, afin de savoir si il n’existe pas de situation pour laquelle l’algorithme ne se terminerait pas.
On remarque pour cela que l’algorithme est constitué de deux boucles.
La première est la boucle for dont le nombre de passage est fini et fixé : il y en a $n-1$.
La deuxième boucle est une boucle interne while. Les valeurs prises par l’indice variant $k$ constituent une suite d’entiers strictement décroissante, incluse dans la suite $i+1, i,…, 2, 1$.
L’algorithme peut sortir de la boucle avant que $k$ n’atteigne la valeur $1$, dans le cas où l’élément n’est pas placé en première position. Il y a donc au plus $i+1$ passages. On vient donc de vérifier la terminaison de cet algorithme.
Un des autres aspects qu’il faut regarder en écrivant un algorithme est son coût. On distingue ici deux cas.
Le premier cas est celui d’une liste déjà triée dans l’ordre croissant. Dans ce cas, $i$ prend $n-1$ valeurs et il n’y a qu’une seule comparaison dans la boucle while : le coût dans ce cas est donc de $n$. C’est un coût linéaire.
Le deuxième cas correspond au cas où la liste est triée dans l’ordre décroissant. $i$ prend à nouveau $n-1$ valeurs mais pour chaque valeur de $i$, il y a $i+1$ comparaison car on place à chaque fois l’élément en première position. Au total, il y a donc $1 + 2 + … + (n-1)$ comparaisons, soit pour de grandes valeurs de $n$ un coût comparable à $n^2$.
Cet algorithme est donc couteux lorsque la liste est mal triée.
A l’inverse, pour des listes relativement bien triées, cet algorithme est particulièrement efficace.