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:

La colonne courante j est parcourue de bas en haut, et la ligne courante est la ligne i:


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): 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.