Tri bitonique

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 ${\displaystyle (x_{1},\ldots ,x_{n})}$  telle que ${\displaystyle x_{1}\leq \cdots x_{k}\geq x_{k+1}\geq x_{n}}$  ou ${\displaystyle x_{1}\geq \cdots x_{k}\leq x_{k+1}\leq x_{n}}$  pour un entier ${\displaystyle k}$  entre ${\displaystyle 1}$  et ${\displaystyle n}$ . 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}.

Comme tout réseau de tri, le tri bitonique de Batcher^[2] prend en entrée une suite ${\displaystyle (a_{1},\ldots ,a_{n})}$  et produit en sortie la suite ${\displaystyle (b_{1},\ldots ,b_{n})}$  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 ${\displaystyle (a_{1},\ldots ,a_{n/2})}$  et ${\displaystyle (a_{n/2+1},\ldots ,a_{n})}$  alors la sortie ${\displaystyle (b_{1},\ldots ,b_{n})}$  est une suite triée.

La figure ci-dessous montre un réseau de tri bitonique 16 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] ${\displaystyle [i:j]}$ . Par exemple, les huit premiers comparateurs du réseau ci-dessus sont ${\displaystyle [i:i+1]}$  pour ${\displaystyle i=1,3,5,7,9,11,13,15}$ .

 

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

${\displaystyle [1:n],[2:n-1],\ldots ,[i:n-i+1],\ldots ,[n/2:n/2+1]}$ .

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

${\displaystyle [1:n/2+1],[2:n/2+2],\ldots ,[i:n/2+i],\ldots ,[n/2:n]}$ .

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

Réseau de comparateurs — Soit ${\displaystyle (a_{1},\ldots ,a_{n})}$  une suite formée de ${\displaystyle 0}$  et ${\displaystyle 1}$ , et soit ${\displaystyle (b_{1},\ldots ,b_{n/2},c_{1},\ldots ,c_{n/2})}$  la suite obtenue après l'application d'un réseau de comparateurs d'ordre ${\displaystyle n}$ . Si ${\displaystyle (a_{1},\ldots ,a_{n/2})}$  et ${\displaystyle (a_{n/2+1},\ldots ,a_{n})}$  sont chacune triée, alors ${\displaystyle (b_{1},\ldots ,b_{n/2})}$  et ${\displaystyle (c_{1},\ldots ,c_{n/2})}$  sont bitoniques. De plus, ${\displaystyle b_{i}\leq c_{i}}$  pour ${\displaystyle i=1,\ldots ,n/2}$ .

Séparateurs — Soit ${\displaystyle (a_{1},\ldots ,a_{n})}$  une suite bitonique formée de ${\displaystyle 0}$  et ${\displaystyle 1}$ , et soit ${\displaystyle (b_{1},\ldots ,b_{n/2},c_{1},\ldots ,c_{n/2})}$  la suite obtenue après l'application d'un séparateur d'ordre ${\displaystyle n}$ . Alors ${\displaystyle (b_{1},\ldots ,b_{n/2})}$  et ${\displaystyle (c_{1},\ldots ,c_{n/2})}$  sont bitoniques. De plus, ${\displaystyle b_{i}\leq c_{i}}$  pour ${\displaystyle i=1,\ldots ,n/2}$  et l'une des deux suites ${\displaystyle (b_{1},\ldots ,b_{n/2})}$  et ${\displaystyle (c_{1},\ldots ,c_{n/2})}$  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 ${\displaystyle (a_{1},\ldots ,a_{n/2})}$  et ${\displaystyle (a_{n+1},\ldots ,a_{n})}$  sont chacune triée, alors la suite ${\displaystyle (a_{1},\ldots ,a_{n/2},a_{n},a_{n-1}\ldots ,a_{n+1})}$  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.

Le fusionneur, qui forme une suite triée de taille ${\displaystyle n}$  à partir de deux suites de taille ${\displaystyle n/2}$  est de profondeur (nombre d'étapes en parallèle) ${\displaystyle \log n}$ . Le nombre d'étapes ${\displaystyle T(n)}$  pour le réseau de tri total est :

${\displaystyle T(n)=\log n+T(n/2)}$ ,

La solution de cette équation récursive est :

${\displaystyle T(n)=\log(n)+\log(n)-1+\log(n)-2+...+1=\log(n)(\log(n)+1)/2}$ .

Chaque étape du réseau compare tous les éléments de la suite, et demande donc ${\displaystyle n/2}$  comparateurs. Le nombre total de comparateurs est donc^[3] en ${\displaystyle \Theta (n\log ^{2}n)}$ .

• Réseau de fusion pair-impair de Batcher (en)

• Code de référence du National Institute of Standards and Technology

•   Portail de l'informatique théorique