Sortie

1. $tbl_{sortie}$ tel que l'élément $tbl_{entre}[i]$ soit à la position $k$ dans $tbl_{sortie}$ et $\forall j > k, tbl\_{sortie}[j] == tbl\_{entree}[j-1]$

La figure 1.2 illustre l'opération effectuée par l'algorithme Insertion.

Algorithme Insertion
Input:
  int N;
  int tbl[N];
  int i;
  int k;
Output:
  // pas de retour
Begin
  int ei,j;

  // Insertion de tbl[i] a la place k
  // -> memorise tbl[i]
  ei=tbl[i];
  // -> rotation - decale les elements pour pouvoir inserer tbl[i]
  for (j=i-1;j>=k;j=j-1)
  {
     tbl[j+1]=tbl[j];
  }
  // -> ecrit ei en k
  tbl[k]=ei;
End