Wiki NSI

Cette page est en lecture seule. Vous pouvez afficher le texte source, mais ne pourrez pas le modifier. Contactez votre administrateur si vous pensez qu'il s'agit d'une erreur.
====== Algorithme de tri par insertion:======
----

====== L'algorithme de tri par insertion c'est quoi?  ======
Le tri par insertion fait partie de la famille des algorithme de tri, on l'utilise intuitivement quand on doit trier une liste de cartes et de billets de banque dans un ordre croissant par exemple. L'algorithme de tri par insertion fait aussi partie de la sous famille des tris stables, c'est à dire qu'il ne change pas l'ordre d'apparition des éléments égaux.



====== Comment ça fonctionne?  ====== 
{{  :les_programmes_a_connaitre:algorithmique_premiere:tri_insertion1.gif|}}
Dans une liste de n éléments nous partirons de l'élément n2 (en pseudo-code) jusqu'à n-1 en comparant  n2 à n1, si n2 est plus grand que n1 alors aucun changement ne sera fait. On passe à l'élément suivant, on compare n2 à n3 on se rend compte que n3 est plus petit que n2 alors on sort n3 de la liste on change de place n2, on compare ensuite n1 à n3, n1 est plus petit que n3 donc n1 reste à sa place et on insert n3 à la place d'origine de n2.


**Algorithme en python**
<code python>
"""
objectif: L'objectif d'un algorithme de tri par insertion est de ranger une liste dans un ordre croissant.        
entrée: Une liste de nombres réels non ordonnés
sortie: Une liste de nombres réels ordonnés
"""
#initialisation des variables
t=[2,5,4,1,7]

def tri_par_insertion(t):
    j=1
    while j<len(t): #boucle 1   
        i=j-1
        k=t[j] #K stocke la valeur de t[j] au cas où si l'on entre dans la boucle 2
        while i>=0 and t[i]>k: #boucle 2
            t[i+1]=t[i] #on place t[i] à la place initiale de k
            i-=1 #la valeur de i déscend chaque fois que k<t[i]
        t[i+1]=k #une fois la boucle 2 terminé on place k dans t[i+1]
        j+=1 #j+1 pour passer à l'élément suivant de la liste à trier
    return t

#programme principal
print(tri_par_insertion(t))

#sortie
[1, 2, 4, 5, 7]
</code> 
**Algorithme en pseudo-code** \\
{{:les_programmes_a_connaitre:algorithmique_premiere:tri_insertion2.png?300 |}}
**Application écrite de l'algorithme**
{{:les_programmes_a_connaitre:algorithmique_premiere:algo_tri_insertion_ex.png?400|}}
====== La complexité de l'algorithme de tri par insertion  ======
le tri par insertion possède deux types de complexités:

== 1- ==
{{ :les_programmes_a_connaitre:algorithmique_premiere:classes-de-complexite-1024x512.png?400|}}
Dans le pire des cas quand on se retrouve avec une liste trié à l'envers'' [5, 4, 3, 2, 1] '' la complexité est quadratique noté Θ(n²).

==2- ==
Dans le meilleur des cas c'est à dire lorsque l'on se retrouve avec une liste entièrment trié'' [1, 2, 3, 4, 5] '', la complexité est dite linéaire noté Θ(n).
== ==
Cependant la complexité moyenne reste quadratique.
Wiki NSI

Outils pour utilisateurs

Outils du site

Outils de la page
