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