Différences

Ci-dessous, les différences entre deux révisions de la page.

--- les_programmes_a_connaitre:algorithmique_premiere:tri_insertion [2023/02/05 22:44]
eg [L'algorithme de tri par insertion c'est quoi?]
+++ les_programmes_a_connaitre:algorithmique_premiere:tri_insertion [2023/02/10 13:48] (Version actuelle)
eg
@@ Ligne 3: / Ligne 3: @@
 ====== 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.
+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.
-{{  :les_programmes_a_connaitre:algorithmique_premiere:tri_insertion1.gif|}}
-====== Comment ça fonctionne?  ======
-Dans une liste de n éléments nous partirons de l'élément n0 jusqu'à n-1 en comparant  n0 à n1, si n1 est plus grand que n0 alors aucun changement ne sera fait. On passe à l'élément suivant, on compare n1 à n2 on se rend compte que n2 est plus petit que n1 alors on sort n2 de la liste on change de place n1, on compare ensuite n0 à n2, n0 est plus petit que n2 donc n0 reste à sa place et on insert n2 à la place d'origine de n1.
+====== 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.
@@ Ligne 47: / Ligne 48: @@
 == 1- ==
-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²).
+{{ :les_programmes_a_connaitre:algorithmique_premiere:classes-de-complexite-1024x512.png?400|}}
-{{ :les_programmes_a_connaitre:algorithmique_premiere:graphique3.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).
+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

Différences

Outils de la page