Introducing 

Prezi AI.

Your new presentation assistant.

Refine, enhance, and tailor your content, source relevant images, and edit visuals quicker than ever before.

Loading…
Transcript

Tri par insertion

presente par mariem x3

et ranya

Le tri par insertion

on parle de tri lorsque l'on veut classer des donnes de type construit avec une relation d'ordre definie. Par exemple, ranger des nombres dans l'ordre croissant.

bien sur vous trouverez une fonction adaptee a cet exemple dans Python capable de realiser cela directement avec des listes, mais il est indispensable de connaitre les principales familles d'algorithmes poyvant y mener.

Le principe du tri

le principe du tri par insertion est assez simple: on prend les donnes une par une en commancant par la premiere et on les compare aux precedants

  • Au depart la premiere est suppose a sa place
  • on regarde la troisieme: on compare aux precendents en partant de la plus proche(donc la deuxieme et si necessaire a celle d'avant) et on echange si l'odre n'est pas bon.

on parcourt donc toutte la liste et pour chaque position la sous liste composee des valeurs precendents est deja triee, on insere donc la nouvelle valeur directement au bon endroit dans la liste precendente

  • on regarde la deuxieme et on compare a la premiere, on echange si besoin. les deux premieres donnes sont donc rangees dans l'ordre.
  • on regarde la 4eme donne et on la fait ainsi descendre a la position qui lui correspend jusqu'a ce que les 4 premieres donnes soient rangees.
  • on poursuit ainsi jusque la derniere donee

l'algorithme peut donc se resumer avec:

  • on dispose d'une liste de nombre de longeur L
  • pour i allant de 0 a L

j=i

tant que j>0 et la liste [j-1]>liste[j]:

  • echanger( liste[j-1], liste[j])
  • decrementer j

l'algorithme

nous voyons donc deux boucles:

une boucle bornee (for) pour i allant de 0 a L

une boucle bornn=ee (while) pour chaque valeur de i afain de trouver la bonne position de L[i] dans la sous liste deja triee

programmation avec python

Proposal Review, Evaluation & Selection

la complexite

Review

Review

Evaluation

Evaluation

Selection

Selection

Learn more about creating dynamic, engaging presentations with Prezi