Différences

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

--- itc:tps:tp5:exercice1 [2022/01/01 20:11] – 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 64: / Ligne 64: @@
         m est la valeur de L en indice_milieu
         SI m <= e ALORS
-            continuer avec la zone [indice_debut + 1 : b]
+            continuer avec la zone [indice_milieu + 1 : b]
         SINON
-            continuer avec la zone [a:indice_debut-1 ]
+            continuer avec la zone [a:indice_milieu]
         FIN
     FIN
@@ Ligne 74: / Ligne 74: @@
 <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 ''%%recherche_rang_insertion(L:list, a:int, b:int, e) -> int'' traduisant l'algorithme ci-dessus.
+  * É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>