Tri par insertion à sélection linéaire

Il s'agit du tri par insertion lorsque Rang est implémenté par une recherche linéaire.

Algorithme Rang
Input:
  int N;
  int tbl[N];
  int g;
  int d;
  int val;
Output:
  int
Begin
  int i;

  i=g;
  while (val >= tbl[i])
  {
    i=i+1;
  }
  return (i);
End

Il est facile de vérifier que l'algorithme est correct (ie. il respecte les spécifications de sortie si les paramètres respectent les spécifications d'entrée - notamment $val < tbl[d]$ qui permet de garantir que la boucle s'arrête avant que $i$ dépasse $d$).
Complexité (comparaisons) en $O(n)$.
Complexité (comparaisons) de TriInsertion en $O(n^2)$.
Complexité (accès) de TriInsertion en $\theta(n^2)$.