Tri bitonique

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 :

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] ${\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 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

${\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)}$.