====== 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 =====

On considère une tableau ''L'' d'éléments comparables que l'on trie selon le protocole suivant.
  * On classe au fur et à mesure de l'avancée dans le tableau :
    * si le tableau n’a qu’un seul élément il est déjà trié,
    * 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>