Tout le monde connait les « tri à bulle », le « tri par insertion », le « tri fusion » ou même le célèbre « Quick Sort », mais connaissez-vous le « Tri par Interclassement Monotone » ? Si ce n’est pas le cas, je voudrais vous le faire découvrir dans la suite. Et j’aurai besoin de vos lumières.
Pour illustrer le fonctionnement, prenons une liste initiale (I) d’entiers pour simplifier :
Liste initiale : 0 – 1 – 2 – 4 – 5 – 6 – 3 – 9 – 8 – 7
Vous remarquez que le chiffre 3 est mal placé et que les derniers items (9, 8 et 7) sont ordonnés à l’envers. Cette situation est statistiquement valide.
Note : le cas des listes triées correspond à la pire situation pour le Quick Sort.
N’ayant rien trouvé sur le Web, je me suis adressé à Olivier Durin, mon ancien prof de l’ESIEA, qui m’a renvoyé sur son livre. Voici un résumé.
Principe
Le « Tri Interclassement Monotone » (ou monotonie) est particulièrement adapté à des listes triées par morceaux, pour permettre le tri de grandes quantités de données à l’époque où les données étaient sur des bandes magnétiques. Il est de complexité en « n.Log(n) » comme « Quick Sort », mais sans les inconvénients du pire des cas.
Note : Je vous vois venir. Comme me le disais José Paumard, on n’en est plus à l’époque des bandes magnétiques. Cela dit, le temps de transfert d’un tableau de la mémoire centrale aux caches CPU, comparé à celui d’une liste chaînée, dont les éléments sont dispersés dans la mémoire, se pose exactement dans les mêmes termes. Et puis, comme me l’expliquait Olivier, on peut utiliser ce type de tri pour trier des gros fichiers dans un environnement contraint en mémoire puisqu’il n’y a besoin que d’ouvrir deux InputStream et une seule OutputStream (ou le contraire selon l’étape) et juste une paire de variables.
On répète deux phases jusqu’à ce que ce soit trié, en utilisant des bandes magnétiques (ie. des listes) temporaires (A) et (B) :
- on recopie de la bande initiale (I) vers la bande (A) tant que la suite est croissante. On copie vers la bande (B) dès qu’il y a une décroissance. On continue sur la bande (B) jusqu’à ce qu’il y ait une décroissance en reprenant alors sur la bande (A) ;
- on fusionne les bandes (A) et (B) sur la bande (I) en copiant toujours le plus petit élément.
Par exemple, pour la première passe, ça va donner :
I : 0 – 1 – 2 – 4 – 5 – 6 – 3 – 9 – 8 – 7
A : –
B : –
puis
I : (0) – 1 – 2 – 4 – 5 – 6 – 3 – 9 – 8 – 7
A : (0)
B : –
puis
I : 0 – (1) – 2 – 4 – 5 – 6 – 3 – 9 – 8 – 7
A : 0 – (1)
B : –
…
puis
I : 0 – 1 – 2 – 4 – 5 – (6) – 3 – 9 – 8 – 7
A : 0 – 1 – 2 – 4 – 5 – (6)
B : –
puis
I : 0 – 1 – 2 – 4 – 5 – 6 – (3) – 9 – 8 – 7
A : 0 – 1 – 2 – 4 – 5 – 6
B : (3) <Рd̩croissance
puis
I : 0 – 1 – 2 – 4 – 5 – 6 – 3 – (9) – 8 – 7
A : 0 – 1 – 2 – 4 – 5 – 6
B : 3 – (9)
puis
I : 0 – 1 – 2 – 4 – 5 – 6 – 3 – 9 – (8) – 7
A : 0 Р1 Р2 Р4 Р5 Р6 Р(8) <Рd̩croissance
B : 3 – 9
puis enfin
I : 0 – 1 – 2 – 4 – 5 – 6 – 3 – 9 – 8 – (7)
A : 0 – 1 – 2 – 4 – 5 – 6 – 8
B : 3 Р9 Р(7) <Рd̩croissance
On peut maintenant s'occuper de la seconde phase, ce qui donne :
A : 0 – 1 – 2 – 4 – 5 – 6 – 8
B : 3 – 9 – 7
R : –
puis
A : (0) – 1 – 2 – 4 – 5 – 6 – 8
B : (3) – 9 – 7
R : (0)
puis
A : 0 – (1) – 2 – 4 – 5 – 6 – 8
B : (3) – 9 – 7
R : 0 – (1)
puis
A : 0 – 1 – (2) – 4 – 5 – 6 – 8
B : (3) – 9 – 7
R : 0 – 1 – (2)
puis
A : 0 – 1 – 2 – (4) – 5 – 6 – 8
B : (3) – 9 – 7
R : 0 – 1 – 2 – (3)
…
puis enfin
A : 0 – 1 – 2 – 4 – 5 – 6 – 8
B : 3 – 9 – (7)
R : 0 – 1 – 2 – 3 – 4 – 5 – 6 – 8 – 9 – (7)
On recommande tant que la liste n'est pas entièrement triée. Si on reprend depuis le début, voici ce que ça donne :
I : 0 – 1 – 2 – 4 – 5 – 6 – 3 – 9 – 8 – 7
puis
A : 0 – 1 – 2 – 4 – 5 – 6 – 8
B : 3 – 9 – 7
R : 0 – 1 – 2 – 3 – 4 – 5 – 6 – 8 – 9 – 7
puis
A : 0 – 1 – 2 – 4 – 5 – 6 – 8 – 9
B : 7
R : 0 – 1 – 2 – 3 – 4 – 5 – 6 – 7 – 8 – 9
Et voilà . Assez rapide pour vous ?
Pour la complexité, très sommairement, s’il y a N lignes, il y a donc N lectures et N écritures par phases. La longueur des sous-suites monotones est TRES grossièrement 2 puis 4 puis 8, bref, on va avoir log base 2 (N) étapes. C’est assez approximatif, mais disons que le pire des cas, c’est n.log(n) et que sur le cas de listes partiellement triées, c’est quasi linéaire.
Variante
Je peux vous proposer une variante, très personnelle, de ce tri mais qui semble moins performante. Du coup, je me demande pourquoi je la propose… En plus de la liste de départ, on va toujours gérer deux listes temporaires (A) et (B). On va parcourir la liste originale. Tant que les éléments sont croissants, on les déplacera en queue de la liste (A). Quand les éléments sont décroissants, on les déplace en tête de la liste (B). L’idée est de travailler avec des listes doublement chainées (LinkedList en Java) pour ajouter rapidement les éléments, soit en tête, soit en queue.
Par exemple, pour la première passe, ça va donner :
I : 0 – 1 – 2 – 4 – 5 – 6 – 3 – 9 – 8 – 7
A : –
B : –
puis
I : 1 – 2 – 4 – 5 – 6 – 3 – 9 – 8 – 7
A : 0
B : –
puis
I : 2 – 4 – 5 – 6 – 3 – 9 – 8 – 7
A : 0 – 1
B : –
…
puis
I : 3 – 9 – 8 – 7
A : 0 – 1 – 2 – 4 – 5 – 6
B : –
puis
I : 9 – 8 – 7
A : 0 – 1 – 2 – 4 – 5 – 6
B : 3 <Рd̩but de d̩croissance
puis
I : 8 – 7
A : 0 Р1 Р2 Р4 Р5 Р6 Р9 <Рd̩but de croissance
B : 3
puis
I : 7
A : 0 – 1 – 2 – 4 – 5 – 6 – 9
B : 8 Р3 <Рd̩but de d̩croissance
puis enfin
I : –
A : 0 – 1 – 2 – 4 – 5 – 6 – 9
B : 7 – 8 – 3
Quand la liste (I) est vide, on est arrivé à la fin de la première séparation. Il ne reste plus qu'à rassembler les listes temporaires en prenant toujours l'item le plus petit en tête des deux listes, ce qui donne :
A : 0 – 1 – 2 – 4 – 5 – 6 – 9
B : 7 – 8 – 3
R : –
puis
A : 1 – 2 – 4 – 5 – 6 – 9
B : 7 – 8 – 3
R : 0
puis
A : 2 – 4 – 5 – 6 – 9
B : 7 – 8 – 3
R : 0 – 1
…
puis
A : –
B : –
R : 0 – 1 – 2 – 4 – 5 – 6 – 7 – 8 – 3 – 9
On recommence tant que la liste (A) ne contient pas l'ensemble des éléments. Si on reprend depuis le début, voici ce que ça donne :
I : 0 – 1 – 2 – 4 – 5 – 6 – 3 – 9 – 8 – 7
puis
A : 0 – 1 – 2 – 4 – 5 – 6 – 9
B : 7 – 8 – 3
R : 0 – 1 – 2 – 4 – 5 – 6 – 7 – 8 – 3 – 9
puis
A : 0 – 1 – 2 – 4 – 5 – 6 – 7 – 8 – 9
B : 3
R : 0 – 1 – 2 – 3 – 4 – 5 – 6 – 7 – 8 – 9
puis une sortie sur la condition d'arrêt.
A : 0 – 1 – 2 – 3 – 4 – 5 – 6 – 7 – 8 – 9
B : –
R : sortie
A noter un cas particulier où la liste serait complètement triée mais dans le mauvais sens. Dans ce cas, la liste (B) contiendrait tous les éléments (insérés par la tête) et il suffirait de la renvoyer.