Implémentation itérative

L'algorithme peut-être écrit sans appel récursif. L'intéret est que l'on économise le coût (en temps et en mémoire) des appels. En effet un appel récursif nécessite de stocker les valeurs des variables de l'algorithme dans une pile, ce qui prend du temps et surtout de l'espace.

Algorithme TriInsertionIter
Input:
  int N;        // N > 0
  int tbl[N];   // modifié
Output:
  // pas de retour: modification directe du tableau
Begin
  int i;

  for (i=1;i<N;i++) // commence a i=1 car rien a faire pour i=0
  {
    // si l'élément i n'est pas à la bonne place (si il n'est
    // pas le max du tableau déjà trié)
    if (tbl[i] < tbl[i-1])
    {
      // Cherche la place ou devrait etre i dans le tableau deja trie
      k=Rang(N,tbl,0,i-1,tbl[i]);
      // Insere i
      Insertion(N,tbl,i,k);
    }
  }
End