{ Fonction de recherche et retour                }
{ de la position d'un entier                     }
{ dans un tableau d'entiers                      }
{ trié par ordre croissant                       }
{ et restreint aux indices 0 a n-1 inclus        }
{ (n premières valeurs du tableau)               }
{ v : Valeur entière recherchée                  }
{ n : Nombre de valeurs initiales du tableau     }
{     parmi lesquelles la recherche est réalisée }
{ t : Le tableau trié d'entiers de recherche     }

entier fonction positionInsertion(-> entier v,
                                  -> entier n,
                                  -> entier [] t)
  entier p <- n
  faire
    p <- p-1
  tant que ( ( p >= 0 ) et ( v < t[p] ) )
  p <- p+1
  retourner p
fin fonction

{ Action de décalage de une cellule              }
{ vers la droite du contenu des cellules         }
{ d'indice indi à indice indf inclus             }
{ d'un tableau d'entiers                         }
{ indi : L'indice initial de décalage            }
{ indf : L'indice final de décalage              }
{ t : Le tableau d'entiers où le décalage        }
{     est réalisé                                }

action decalage(-> entier indi,
                -> entier indf,
                -> entier [] t ->)
  entier i
  pour i de indf à indi pas -1 faire
    t[i+1] <- t[i]
  fait
fin action

{ Action de tri "par insertion"                  }
{ par ordre croissant des valeurs                }
{ contenues dans un tableau d'entiers            }
{ t : Le tableau d'entiers à trier               }
{     par ordre croissant                        } 

action triInsertion(-> entier [] t ->)
  entier i
  entier p
  entier v
  pour i de 1 à longueur(t)-1 faire
    p <- positionInsertion(t[i],i,t)
    si p <> i alors
      v <- t[i]
      decalage(p,i-1,t)
      t[p] <- v
    fsi
  fait
fin action