Fiche de cours
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,