Réseau de tri

Un réseau de tri est constitué de deux types d'objets : les fils et les comparateurs. Les fils transportent des données de gauche à droite, les valeurs transportées, une par fil, traversent le réseau toutes en même temps et de façon synchrone. Chaque comparateur relie deux fils. Quand une paire de valeurs, transportée par une paire de fils, rencontre un comparateur, le comparateur échange les valeurs si et seulement si la valeur sur le fil supérieur est plus grande que la valeur sur le fil inférieur ; de la sorte, à la sortie c'est toujours la plus petite valeur qui se trouve sur le fil supérieur et la plus grande sur le fil inférieur. Voir le mode opératoire sur la figure ci-contre.

Formellement, si le fil supérieur contient x et le fil inférieur y, alors après avoir touché un comparateur les fils portent ${\displaystyle x'=\min(x,y)}$ et ${\displaystyle y'=\max(x,y)}$ respectivement, de sorte que la paire de valeur est triée^{[1]:p. 682}. Un réseau composé de fils et de comparateurs est un réseau de comparateurs. Un réseau de comparateurs qui trie correctement toutes les entrées possibles dans l'ordre croissant est appelé un réseau de tri.

Le schéma ci-dessous montre un réseau de comparateurs. Il est facile de voir pourquoi ce réseau trie correctement les entrées : les quatre premiers comparateurs font descendre la plus grande valeur vers le fil du bas et font remonter la plus petite valeur vers le fil du haut. Le comparateur final trie simplement les valeurs des deux fils du milieu. C'est donc un réseau de tri.

L'efficacité d'un réseau de tri peut être mesurée par sa taille totale, c'est-à-dire le nombre de comparateurs utilisés, ou par sa profondeur , définie comme étant le plus grand nombre de comparateurs qu'une valeur d'entrée peut rencontrer sur son chemin à travers le réseau. Le réseau peut effectuer certaines comparaisons en parallèle, représentées dans la notation graphique par des comparateurs qui se trouvent sur la même ligne verticale. En supposant que toutes les comparaisons prennent la même unité de temps, la profondeur du réseau est égale au nombre d'unités de temps requis pour l'exécuter en parallèle^{[1]:p. 683-684,[2]}.

On construit facilement un réseau de tri de taille arbitraire récursivement en utilisant le principe à la base du tri par insertion ou celui du tri par sélection. En supposant l'existence d'un réseau de tri de la taille n , on construit un réseau de taille n + 1 par « insertion » d'une donnée supplémentaire dans le sous-réseau déjà trié en utilisant le principe du tri par insertion. Pour cela, on ajoute au réseau une suite de comparateurs qui insère cette dernière valeur à sa place. On peut également opérer en utilisant le principe du tri à bulles : on débute par la « sélection » de la valeur la plus grande parmi les entrées, à l'aide d'une suite de comparateurs qui descend la plus grande valeur vers le bas, puis on continue par le tri récursif des valeurs restantes.

Ces deux réseaux de tri, même s'ils sont construits selon des principes algorithmiques différent, ont des structures similaires en tant que réseaux. Lorsqu'on aligne les comparateurs qui peuvent opérer en parallèle, on s'aperçoit qu'en fait ils sont identiques^[3].

Ces réseaux de tri - par insertion ou par sélection - ont une profondeur 2n - 3^[3], ce qui les rend trop longs en pratique. Il existe de meilleures constructions, présentées plus loin, dont la profondeur est logarithmique en n.

Le principe du zéro-un est une propriété utile pour démontrer qu'un réseau trie correctement les données. Alors qu'il est facile de prouver la validité de réseaux de tri dans certains cas particuliers, comme les réseaux par insertion ou par bulles, la preuve n'est pas toujours aussi facile. Il y a n! permutations de nombres dans un réseau à n fils, et tester tous les cas prend un temps considérable dès que n est grand Le nombre de cas à tester peut être réduit de manière significative, à 2ⁿ, en utilisant ce qu'on appelle le principe du zéro-un. Même s'il est toujours exponentiel, 2ⁿ est plus petit que n! pour n≥ 4, et la différence croît rapidement avec n.

Le principe du zéro-un stipule que si un réseau de tri trie correctement les 2ⁿ suites composées uniquement de zéros et de uns, alors il trie correctement toute suite d'entrées.

Ce principe non seulement réduit de façon drastique le nombre de test nécessaires pour garantir la validité d'un réseau; il est également d'une grande utilité pour la construction de réseaux de tri.

Démonstration. On constate d'abord le fait suivant sur les comparateurs : si une fonction monotone croissante ${\displaystyle f}$ est appliquée aux entrées, c'est-à-dire si ${\displaystyle x}$ et ${\displaystyle y}$ sont remplacés par ${\displaystyle f(x)}$ et ${\displaystyle f(y)}$, alors le comparateur produit ${\displaystyle \min(f(x),f(y))=f(\min(x,y))}$ et ${\displaystyle \max(f(x),f(y))=f(\max(x,y))}$. En raisonnant par récurrence sur la profondeur du réseau, ce résultat est étendu en un lemme stipulant que si un réseau transforme une suite ${\displaystyle (a_{1},\ldots ,a_{n})}$ en ${\displaystyle (b_{1},\ldots ,b_{n})}$, alors il transforme ${\displaystyle (f(a_{1}),\ldots ,f(a_{n}))}$ en ${\displaystyle (f(b_{1}),\ldots ,f(b_{n}))}$.

Supposons maintenant, en raisonnant par l’absurde, que le réseau trie les séquences formées de zéros et de uns, mais qu’il existe une séquence de nombres ${\displaystyle (a_{1},\ldots ,a_{n})}$ que le réseau ne trie pas correctement. Alors il existe des entrées ${\displaystyle a_{i}<a_{j}}$ avec ${\displaystyle i<j}$ que le réseau échange à la sortie. On définit une fonction monotone croissante particulière par

${\displaystyle f(x)={\begin{cases}1\ &{\mbox{si }}x>a_{i}\\0\ &{\mbox{sinon.}}\end{cases}}}$

Puisque le réseau place ${\displaystyle a_{j}}$ avant ${\displaystyle a_{i}}$, le lemme dit qu'il place ${\displaystyle f(a_{j})}$ avant ${\displaystyle f(a_{i})}$ dans la séquence de sortie pour l'entrée ${\displaystyle (f(a_{1}),\ldots ,f(a_{n}))}$. Mais comme ${\displaystyle f(a_{j})=1}$ et ${\displaystyle f(a_{i})=0}$, le réseau ne trie pas correctement la séquence zéro-un ${\displaystyle (f(a_{1}),\ldots ,f(a_{n}))}$, en contradiction avec l'hypothèse de départ^{[1]:p. 686–688}. Ceci prouve le principe du zéro-un.