Première > Numérique et sciences informatiques > Algorithmique > Tri par insertion

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 !

Démarrer l'essai gratuit

Tri par insertion

Permalien

Télécharger la fiche de cours Les téléchargements sont réservés uniquements aux abonnés

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] \lefta

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.