Différences

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

--- itc:tps:tp5:exercice1 [2022/01/01 19:29] – 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 1: / Ligne 1: @@
 ====== Tri par insertion dichotomique ======
+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:tableau:tri:insertion|tri par insertion]].</WRAP>
 ===== Principe =====
@@ Ligne 8: / Ligne 13: @@
     * sinon on prend le deuxième et on le compare au premier pour les mettre dans le bon ordre.
   * Si on suppose les ''i'' premiers éléments déjà classés on prend le ''(i + 1)''-ème que l’on compare, par exemple en descendant à partir de la position ''i'', jusqu’à trouver, ou pas, un plus petit que lui et l'insérer alors à la bonne place.
+===== Algorithme =====
+<code lang-none>
+FONCTION tri_par_insertion
+ENTRÉE: tableau_a_trier, le tableau à trier
+La fonction ne renvoie rien, le tableau est trié en place
+DÉBUT
+  soit n la longueur de tableau_a_trier
+  POUR i allant de 1 à n - 1 FAIRE
+    soit item l'élément de rang i dans tableau_a_trier
+    soit j = i
+    TANT QUE j > 0 et l'élément de rang j-1 supérieur à item FAIRE
+      copier l'item de rang j-1 au rang j
+      j passe à j-1
+    FIN
+    copier item au rang j
+  FIN
+FIN
+</code>
+Ici, le tri se fait en place, ce qui est une bonne chose du point de vue de l'utilisation de la mémoire. On peut apporter des améliorations pour limiter le nombre de comparaisons ou d'échanges, mais cela ne
+change pas le principe d’insertion : il y a deux boucles imbriquées, ici une boucle globale en ''for'' et à l'intérieur une boucle en ''while''.
+<WRAP box>
+  - Traduisez cet algorithme en Python et testez.
+  - Écrivez une fonction ''liste_aleatoire(N:int, n:int)'' créant une liste aléatoire de ''n'' entiers ''i'' tels que ''0 <= i < N''.
+  - À l’aide de la fonction ''time'' du module ''time'', donner la durée d’exécution de la fonction ''tri_insertion'' pour quelques listes aléatoires de grande taille.\\ On pourra commencer par
+$N = 10^7$ et $n$ dans $\left\lbrace 100, 1000, 10 000\right\rbrace$.
+</WRAP>
+//On prouvera plus tard la correction du programme et on étudiera sa complexité.//
+===== L'insertion dichotomique =====
+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 l'algorithme qui suit :
+<code lang-none>
+FONCTION recherche_rang_insertion
+ENTRÉES
+    L: un tableau
+    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>
+  * Écrivez, dans l'ordre, les fonctions traduisant les algorithmes ci-dessus.
+  * Testez et vérifiez si l'insertion dichotomique fait gagner du temps temps.
+</WRAP>