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.

Un réseau de tri qui trie d'abord les n premières valeurs, puis insère la valeur restante (tri par insertion).

Un réseau de tri qui descend d'abord la plus grande valeur vers le bas, puis trie les autres valeurs (tri à bulles).

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].

tri à bulles.

tri par insertion.

En alignant les comparateurs parallèles, les deux réseaux sont identiques.

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.

Pour un nombre petit et fixé d'entrées, on peut construire des réseaux de tri optimaux, soit qu'ils sont de profondeur minimale (utile pour une exécution en parallèle), soit qu'ils comportent un nombre minimal de comparateurs (ils sont alors de taille minimale). Ces réseaux peuvent être employés dans une optique de construction récursive, comme briques qui améliorent les performances de réseaux plus grands. On peut ainsi arrêter plus tôt la construction récursive dans les réseaux de Batcher par exemple[10]. La table suivante donne les résultats d'optimalité connus :

Les seize premiers réseaux optimaux en profondeurs sont listés dans la section 5.3.4: « Networks for Sorting » du livre Art of Computer Programming de Knuth[3] et étaient déjà présents dans la première édition de 1973 ; l'optimalité des huit premières valeurs a été prouvée par Robert Floyd et Knuth dans les années 1960, alors que la preuve pour les six dernières valeurs date seulement de 2014[11]. Dans leur article, ils expriment le problème, après une réduction astucieuse, par des formules de logique propositionnelle, puis utilisent un logiciel de test de satisfiabilité. Les cas neuf et dix ont été résolus plus tôt, en 1991, par Parberry[10]. Une autre technique pour trouver des réseaux optimaux est décrite dans une page de Jason D. Hugues[13].

Des réseaux optimaux en taille sont connus pour un nombre d'entrées compris entre un et dix ; pour des valeurs plus élevées, des minorants de la taille S(n) peuvent être déduit inductivement d'un lemme dû à Van Voorhis : ${\displaystyle S(n+1)\geq S(n)+\lceil \log _{2}n\rceil }$. Les dix réseaux optimaux sont connus depuis 1969, dont les huit premiers sont connus de Floyd et Knuth, mais l'optimalité des cas n = 9 et n = 10 n'a été prouvée qu'en 2014[12]. De nouveaux résultats (en 2017)[14] donnent une réponse sur l'optimalité en profondeur.

La complexité du problème de tester si un réseaux de tri est correct est dans la classe des problèmes co-NP-complets[15]^,[16]. Le cas général est donc intraitable.