Cours Exercice - Algorithmique

Tri par insertion

Accède gratuitement à cette vidéo pendant 7 jours Profite de ce cours et de tout le programme de ta classe avec l'essai gratuit de 7 jours !

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

Il reste 70% de cette fiche de cours à lire
Cette fiche de cours est réservée uniquement à nos abonnés. N'attends pas pour en profiter, abonne-toi sur lesbonsprofs.com. Tu pourras en plus accéder à l'intégralité des rappels de cours en vidéo ainsi qu'à des QCM et des exercices d'entraînement avec corrigé en texte et en vidéo.