Tri bitonique

Un article de Wikipédia, l'encyclopédie libre.
Sauter à la navigation Sauter à la recherche

Tri bitonique
Image illustrative de l’article Tri bitonique
Réseau de tri bitonique à huit entrées ; 24 comparateurs, profondeur 6.

Problème lié Algorithme de tri
Temps d'exécution pire-cas en parallèle
Complexité algorithmique spatiale comparateurs

Le tri bitonique ou tri par fusion bitonique est un algorithme parallèle de tri. Il est utilisé également comme méthode de construction de réseaux de tri. L'algorithme a été conçu par Ken Batcher en 1968. Les réseaux de tri obtenus consistent en comparateurs et ont un temps d'exécution en parallèle de , où est le nombre de données à trier. Ces réseaux sont parmi les réseaux de tri les plus efficaces.

Une suite est triée quand elle est non décroissante (ou non croissante). Une suite est bitonique quand elle est croissante puis décroissante, ou décroissante puis croissante, les deux au sens large.

Introduction[modifier | modifier le code]

Une suite d'éléments d'un ensemble ordonné est dite bitonique quand elle est croissante puis décroissante, ou décroissante puis croissante, les deux notions prises au sens large. Formellement, c'est une suite telle que ou pour un entier entre et . Une suite croissante et une suite décroissante sont des cas particuliers d'une suite bitonique. Toute permutation circulaire d'une suite bitonique est elle-même bitonique. Par exemple

(1, 4, 6, 8, 3, 2), (9, 3, 1, 2, 5, 7)

sont des suites bitoniques. Toute suite à un, deux ou trois éléments est bitonique. La suite (1, 4, 2, 3) ne l'est pas. Les suites bitoniques composées de 0 et de 1 sont formées d'une plage de 0 suivie d'une plage de 1 suivie d'une plage de 0, ou de toute permutation circulaire de telles suites. Une suite formée uniquement de 0 ou de 1 est dite bitonique pure[1]:p. 689.

Algorithme[modifier | modifier le code]

Principe[modifier | modifier le code]

Comme tout réseau de tri, le tri bitonique de Batcher[2] prend en entrée une suite et produit en sortie la suite qui est la même suite, mais triée. L'algorithme de tri bitonique[1]:p. 689-692,[3] est un algorithme récursif basé sur un réseau particulier appelé fusionneur[4]. Un fusionneur à n entrées a la propriété que si les entrées sont formées de deux suites triées et alors la sortie est une suite triée.

La figure ci-dessous montre un réseau de tri bitonique 16 entrées :

Réseau de tri bitonique pour 16 entrées. La partie droite sur fond bleu est un fusionneur. La partie gauche est composée de deux réseaux de tri bitoniques à 8 entrées superposés, opérant en parallèle. Chacun de ces réseaux est à son tour formé d'un fusionneur à 8 entrées et de deux réseaux à 4 entrées.

Un réseau de tri bitonique à n entrées est composé de deux réseaux bitoniques à n/2 entrées opérant en parallèle, chacun sur la moitié des entrées, suivi d'un fusionneur. En développant cette définition récursive, on peut voir un réseau de tri bitonique comme composé uniquement de fusionneurs, chacun ayant pour tâche de fusionner deux suite triées de taille moitié en une seule suite triée. On suppose ici et dans la suite que n est une puissance de 2. Il est utile de numéroter les fils de 1 à n. Un comparateur entre le fil i et le fil j est noté[3] . Par exemple, les huit premiers comparateurs du réseau ci-dessus sont pour .

Fusionneur[modifier | modifier le code]

Un réseau de comparateurs (à gauche) et un séparateur (à droite).

Un fusionneur est composé de deux parties. La première est un réseau de comparateurs, et la deuxième un ensemble de réseaux appelés séparateurs. Un réseau du premier type peut d'ailleurs être vu comme un séparateur où on a renversé les fils d'entrée de la deuxième moitié.

Un réseau de comparateurs à n entrées est formé des comparateurs

.

Un séparateur à n entrées est formé des comparateurs

.

Ces réseaux ont les propriétés suivantes :

Réseau de comparateursSoit une suite formée de et , et soit la suite obtenue après l'application d'un réseau de comparateurs d'ordre . Si et sont chacune triée, alors et sont bitoniques. De plus, pour .

SéparateursSoit une suite bitonique formée de et , et soit la suite obtenue après l'application d'un séparateur d'ordre . Alors et sont bitoniques. De plus, pour et l'une des deux suites et est bitonique pure.

La première propriété, celle du réseau de comparateurs, est une conséquence de la propriété des séparateurs. En effet, si et sont chacune triée, alors la suite obtenue en retournant la deuxième moitié est bitonique, donc la propriété des fusionneurs peut être appliquée.

La démonstration est par étude de cas, pas très difficile[3].

Le fusionneur d'ordre n est composé d'un comparateur d'ordre n, puis d'une suite de groupes de séparateurs, d'abord deux d'ordre n/2, puis quatre d'ordre n/4 etc. L'entrée du fusionneur est une suite dont les deux moitiés sont triées, la sortie est composée de deux suites bitoniques dont la première est plus petite que la seconde. Chacun de ces suites bitoniques entre dans une cascade de séparateurs dont le résultat est la suite triée. La concaténation de ces deux suites est elle-même triée.

Analyse[modifier | modifier le code]

Le fusionneur, qui forme une suite triée de taille à partir de deux suites de taille est de profondeur (nombre d'étapes en parallèle) . Le nombre d'étapes pour le réseau de tri total est :

,

La solution de cette équation récursive est :

.

Chaque étape du réseau compare tous les éléments de la suite, et demande donc comparateurs. Le nombre total de comparateurs est donc[3] en .

Notes et références[modifier | modifier le code]

  1. a et b Chapitre 27 : « Réseaux de tri », p. 681-700, dans Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest et Clifford Stein, Introduction à l'algorithmique, Dunod, [détail de l’édition]
  2. Kenneth E. Batcher, « Sorting Networks and Their Applications », AFIPS Conference Proceedings: 1968 Spring Joint Computer Conference, Thomson Book Company, vol. 32,‎ , p. 307-314 (DOI 10.1145/1468075.1468121)
  3. a b c et d (en) H. W. Lang, « Bitonic Sort », Algorithmen - Sortieren - Networks, FH Flensburg, Allemagne, (consulté le 22 juillet 2015).
  4. Dans la terminologie de la traduction française du livre de Cormen et. al.
(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « bitonic sort » (voir la liste des auteurs).

Articles connexes[modifier | modifier le code]

Liens externes[modifier | modifier le code]