.précédent | suivant | table des matières
C’est une forme dégénérée du tri par fusion. Ce tri est utilisé pour trier un ensemble représenté en mémoire vive. C’est un tri qui est intéressant dans le cas où le tableau à trier est déjà presque ordonné.
La division de E en deux sous parties E1 et E2 se fait de la façon suivante : si l'ensemble E a n éléments, les n-1 premiers sont rangés dans E1 et le dernier est rangé dans E2. L'algorithme est alors une forme dégénérée du schéma initial, et son temps de calcul est dans .
La fonction de fusion de deux ensembles ordonnés devient, dans ce cas dégénéré, une procédure d'insertion d'un élément dans un ensemble ordonné.
La fonction suivante insère l'élément e dans la partie de tableau qui va de l'indice 0 à n-1. Cette partie est ordonnée.
public static void insertionR(int[] t, int n, int e) {
// n nombre d'éléments de t
// e élément à insérer
if ((n == 0) || (e >= t[n - 1]))
t[n] = e;
else {
t[n] = t[n - 1];
insertionR(t, n - 1, e);
}
}
La forme itérative de cette procédure est :
public static void insertionI ( int t[], int n, int e){
// n nombre d'éléments de t
// e élément à insérer
int i;
for(i=n; ((i!=0)&&(e<t[i-1])); --i) // arrêt : ((i==0)||(e>=t[i-1]))
t[i]=t[i-1];
t[i]=e;
}
La version récursive du tri par insertion est :
public static void triInsertionR(int t[], int n) {
if (n > 1) {
triInsertionR(t, n - 1);
insertionR(t, n - 1, t[n - 1]);
}
}
Et la version itérative :
public static void triInsertionI(int t[], int n){
for(int i=1; i<n; ++i)
insertionI(t, i, t[i]);
}