Différences

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

--- itc:tps:tp5:exercice1 [2022/01/01 19:49] – goupillwiki
+++ itc:tps:tp5:exercice1 [2022/03/24 18:28] (Version actuelle) – ↷ Liens modifiés en raison d'un déplacement. 80.215.85.166
@@ Ligne 3: / Ligne 3: @@
 Le tri par insertion est comparable au [[itc:tps:tp2:exercice4|tri par sélection vu dans le TP2]]
-<WRAP tip>Vous pouvez aussi trouver des cours dans la partie 1ere NSI de ce site : une {{ :nsi:premiere:tris_selection_insertion.eleves.pdf |fiche à imprimer}} et un cours sur le [[nsi:premiere:tris_insertion|tri par insertion]].</WRAP>
+<WRAP tip>Vous pouvez aussi trouver des cours dans la partie 1ere NSI de ce site : une {{ :nsi:premiere:tris_selection_insertion.eleves.pdf |fiche à imprimer}} et un cours sur le [[nsi:premiere:tableau:tri:insertion|tri par insertion]].</WRAP>
@@ Ligne 49: / Ligne 49: @@
 En profitant du fait qu'au moment de chaque insertion, le début de liste est déjà trié, on peut
-procéder à une insertion dichotomique selon le principe qui suit :
+procéder à une insertion dichotomique selon l'algorithme qui suit :
-  * On suppose que l'on dispose d’une liste ''L'' de longueur ''n'' triée dans l’ordre croissant et d'un élément ''a'' comparable que l’on veut ajouter à la liste en l'insérant de manière telle qu'en sortie la nouvelle liste soit encore triée dans l'ordre croissant.
-  * On considère l'élément ''m'' du milieu de la liste -- il faudra choisir lequel on prend lorsque ''n''
+<code lang-none>
-est pair
+FONCTION recherche_rang_insertion
-    * Si ''a == m'' alors on peut insérer ''a'' à gauche ou à droite de ''m'' (il faudra choisir),
+ENTRÉES
-    * si ''a < m'' alors on peut recommencer en insérant ''a'' dans la sous-liste extraite de ''L'' en prenant les premiers éléments de ''L'' jusqu'à ''m''
+    L: un tableau
-    * si ''a > m'', alors on insère ''a'' dans la sous-liste de ''L'' extraite à droite de ''m''.
+    a, b: deux indices de L, a <= b. L[a:b] est trié dans l'ordre croissant
+    e: un élément de même nature que ceux de L
+SORTIE
+    l'indice a <= i <= b auquel il faudrait insérer e pour respecter l'ordre
+DÉBUT
+    TANT QUE a != b RÉPÉTER
+        indice_milieu est (a + b) // 2
+        m est la valeur de L en indice_milieu
+        SI m <= e ALORS
+            continuer avec la zone [indice_milieu + 1 : b]
+        SINON
+            continuer avec la zone [a:indice_milieu]
+        FIN
+    FIN
+    RENVOYER a
+FIN
+</code>
 <wrap info>On montre que la complexité dans le pire des cas du tri avec insertion dichotomique est en $n\,\ln(n)$.</wrap>
+<wrap tip>S'il y a des valeurs de ''L'' égales à ''e'', l'indice d'insertion trouvé sera plutôt après de façon à réduire le nombre de décalages nécessaires à l'insertion.</wrap>
+On prévoit une fonction annexe pour le décalage :
+<code lang-none>
+FONCTION decaler
+ENTRÉES
+    L: un tableau
+    a, b: deux indices de L, a <= b
+SORTIE
+    Pas de sortie, L est modifié en place.
+    Les éléments de rangs dans a:b sont décalés d'une place à droite
+DÉBUT
+    POUR i ALLANT de b-1 à a PAR PAS DE -1, FAIRE:
+        copier L[i] une case à droite
+    FIN
+FIN
+</code>
+Et la fonction de tri par insertion dichotomique :
+<code lang-none>
+FONCTION tri_par_insertion_dichotomique
+ENTRÉES
+    L: liste d'éléments comparables
+SORTIE
+    Pas de sortie, L est triée en place
+DÉBUT
+    soit n la taille de L
+    POUR i ALLANT DE 1 À n-1 FAIRE
+        soit e l'élément L[i]
+        j = recherche point insertion de e dans L[0:i]
+        decaler L[j:i]
+        écrire e à la position j
+    FIN
+FIN
+</code>
 <WRAP box>
-  * Commencez par écrire une fonction qui cherche, par dichotomie, le bon indice d'insertion d'un élément ''e'' dans une liste déjà triée ''L''.
+  * Écrivez, dans l'ordre, les fonctions traduisant les algorithmes ci-dessus.
-  * Écrivez une fonction qui implémente le tri par insertion dichotomique.
+  * Testez et vérifiez si l'insertion dichotomique fait gagner du temps temps.
 </WRAP>