Une étape de l'algorithme
Situation initiale
La colonne en cours de traitement est la colonne j;
comme l'algorithme traite les colonnes de droite à gauche:
-
dans la permutation,
toutes les colonnes à droite de la colonne courante ont
déjà été traitées, et donc le tableau au Sud-Est de la case
(1,j+1) est un tableau standard
(ie. chaque ligne et chaque colonne sont ordonnées);
-
dans le tableau annexe, les colonnes à droite de la colonne courante
sont construites, et ne seront plus modifiées;
les colonnes à gauche de la colonne courante sont vides,
et ne sont pas représentées sur les figures.
La colonne courante j est parcourue de bas en haut,
et la ligne courante est la ligne i:
-
dans la permutation, chaque case du bas de la colonne
(ie. dans une ligne i' > i)
porte donc un numéro inférieur à ses voisins Sud et Est;
-
dans le tableau annexe, les cases du bas de la colonne
sont remplies.
Voici un exemple de situation avant exécution de l'algorithme:
la figure montre à gauche la permutation,
à droite le tableau annexe (sans sa première colonne, qui est vide).
La colonne courante est la seconde,
la ligne courante la troisième,
et la case courante est donc numérotée 35 dans le tableau de gauche.
Noter que le sous-tableau qui correspond, à gauche,
au tableau annexe de droite, est ordonné
(ie. chaque ligne et chaque colonne sont numérotées de façon croissante),
sauf en ce qui concerne la case courante.
Soit x le contenu de la case courante (i,j);
le chemin d'insertion,
représenté en vert sur la figure,
part de la case courante,
est constitué de pas Sud ou Est, et se dirige toujours vers
le plus petit des deux numéros voisins (au Sud ou à l'Est);
il s'arrête lorsque ces deux voisins sont supérieurs à x.
Si l'un des voisins Sud ou Est manque, la direction du chemin est forcée,
et si les deux manquent, l'arrêt est forcé.
Modification de la permutation
L'algorithme modifie la permutation en libérant la case de départ,
puis en décalant vers le Nord-Ouest les numéros des cases du chemin d'insertion,
enfin en numérotant x la case finale ainsi libérée
comme la figure l'illustre (en rouge, la situation après
exécution de l'algorithme).
Cette partie de l'algorithme peut aussi être décrite comme
une variante du jeu de taquin:
les cases sont réalisées sous forme de petits carrés mobiles de bois;
on enlève le carré courant, puis on fait glisser à sa place
celui des deux voisins qui porte le plus petit numéro,
et ainsi de suite.
Il est clair que le choix, parmi les deux voisins,
de celui qui porte le plus petit numéro,
est le seul qui fournisse un tableau dont les lignes et les colonnes
restent ordonnées.
Construction du tableau annexe
Le chemin d'insertion joint la case courante (i,j)
à la case (p,q); l'algorithme modifie la colonne courante
dans le tableau annexe, de la façon suivante
(les autres colonnes du tableau annexe restent inchangées):
-
les cases des lignes i+1 à p
sont décalées vers le haut, et leur contenu décrémenté de 1;
-
la case (p,j) reçoit pour valeur
le nombre de pas Est du chemin d'insertion,
autrement dit q-j.
Le chemin d'insertion de l'exemple comporte 3 pas Sud,
donc les trois cases supérieures de la colonne
(image de gauche) glissent vers le haut et sont
décrémentées (image de droite);
la case libérée reçoit la valeur 2,
car le chemin d'insertion comporte 2 pas Est.
Situation finale
La case numérotée 35 est passée de la ligne 3, colonne 2,
à la ligne 6, colonne 4, en suivant le chemin dessiné en rouge;
la différence entre la colonne d'arrivée
et la colonne de départ est inscrite ligne 6 du tableau annexe,
dans la colonne courante.