Tri bitonique

Tri bitonique

Réseau de tri bitonique à huit entrées ; 24 comparateurs, profondeur 6.

Découvreur ou inventeur	Ken Batcher
Date de découverte	1968
Problèmes liés	Parallel algorithm (en), algorithme de tri
Structure des données	Tableau

Complexité en temps

Pire cas	$O(\log ^{2}(n))$
Moyenne	$O(\log ^{2}(n))$
Meilleur cas	$O(\log ^{2}(n))$

Complexité en espace

Pire cas	$O(n\log ^{2}(n))$

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 $O(n\log ^{2}n)$ comparateurs et ont un temps d'exécution en parallèle de $O(\log ^{2}n)$, où $n$ 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 monotone (croissante ou décroissante). Une suite est bitonique quand elle est croissante puis décroissante, ou décroissante puis croissante, les deux au sens large.

Introduction

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

Algorithme

Principe

Comme tout réseau de tri, le tri bitonique de Batcher prend en entrée une suite $(a_{1},\ldots ,a_{n})$ et produit en sortie la suite $(b_{1},\ldots ,b_{n})$ qui est la même suite, mais triée. L'algorithme de tri bitonique est un algorithme récursif basé sur un réseau particulier appelé fusionneur. Un fusionneur à n entrées a la propriété que si les entrées sont formées de deux suites triées $(a_{1},\ldots ,a_{n/2})$ et $(a_{n/2+1},\ldots ,a_{n})$ alors la sortie $(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é $[i:j]$. Par exemple, les huit premiers comparateurs du réseau ci-dessus sont $[i:i+1]$ pour $i=1,3,5,7,9,11,13,15$.

Fusionneur

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

$[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

$[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 $(a_{1},\ldots ,a_{n})$ une suite formée de $0$ et $1$, et soit $(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 $n$. Si $(a_{1},\ldots ,a_{n/2})$ et $(a_{n/2+1},\ldots ,a_{n})$ sont chacune triée, alors $(b_{1},\ldots ,b_{n/2})$ et $(c_{1},\ldots ,c_{n/2})$ sont bitoniques. De plus, $b_{i}\leq c_{i}$ pour $i=1,\ldots ,n/2$.

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

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

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

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

La solution de cette équation récursive est :

$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 $n/2$ comparateurs. Le nombre total de comparateurs est donc en $\Theta (n\log ^{2}n)$.

Notes et références

(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

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

Liens externes

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