Voir la source de Réseau de tri

[[Fichier:SimpleSortingNetwork2.svg|thumb|Un réseau de tri simple composé de quatre fils et cinq connecteurs.]]
En [[Informatique]], un '''réseau de tri''' est un [[algorithme de tri]] qui trie un nombre fixe de valeurs en utilisant une suite fixe de comparateurs. On peut voir un réseau de tri comme un réseau composé de ''fils'' et de ''comparateurs''. Les valeurs, prises dans un [[Relation d'ordre|ensemble ordonné]], circulent le long des fils. Chaque comparateur connecte deux fils, compare les données qui entrent par les fils et les trie, sortant la plus petite donnée sur l'un des fils, la plus grande sur l’autre.

Les réseaux de tri diffèrent des [[Algorithme de tri#Tris par comparaison|algorithmes de tri par comparaison]] dans le sens où ils ne sont pas capables de traiter un nombre arbitraire d'entrées ; de plus, leur séquence de comparaisons est définie à l'avance, et indépendante du résultat des comparaisons précédentes. L'indépendance des séquences de comparaison est utile pour l'exécution en parallèle et pour la réalisation en [[Matériel informatique|hardware]]. Elle peut aussi être vue comme une protection contre un logiciel malveillant qui chercherait à examiner la nature des séquences triées.

== Introduction ==
[[Fichier:Sorting-network-comparator-demonstration.svg|thumb|150px|Mode opératoire d'un comparateur dans un 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 {{mvar|x}} et le fil inférieur {{mvar|y}}, alors après avoir touché un comparateur les fils portent <math>x' = \min(x, y)</math> et <math>y' = \max(x, y)</math> respectivement, de sorte que la paire de valeur est triée<ref name="clrs">Chapitre 27 : « Réseaux de tri », {{p.|681-700}}, dans {{Cormen2fr}}{{plume}}</ref>{{rp|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.

[[Fichier:SimpleSortingNetworkFullOperation.svg|thumb|450px|center|<center>Un réseau de tri de quatre valeurs et un exemple d'une suite triée.</center>]]

=== Profondeur et taille ===
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 [[Parallélisme (informatique)|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{{refm|"clrs"}}{{Rp|p. 683-684}}{{,}}{{refm|"FH"}}.

=== Réseaux de tri par insertion et par sélection ===
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 {{nowrap | '' 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.

{| align="center"
|style="vertical-align: top;"| [[Fichier:Réseau par insertion.svg|300px|thumb|Un réseau de tri qui trie d'abord les ''n'' premières valeurs, puis insère la valeur restante ([[tri par insertion]]).]]
|style="vertical-align: top;"| [[Fichier:Réseau par bulles.svg|300px|thumb|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<ref name="knuth"/>.
{| align="center"
|style="vertical-align: top;"| [[Fichier:Six-wire-bubble-sorting-network.svg|200px|thumb|tri à bulles.]]
|style="vertical-align: top;"| [[Fichier:Six-wire-insertion-sorting-network.svg|200px|thumb|tri par insertion.]]
|style="vertical-align: top;"| [[Fichier:Six-wire-pyramid-sorting-network.svg|200px|thumb|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 {{math|2''n'' - 3}}<ref name="knuth"/>, 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''.

=== Principe du zéro-un ===
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 {{math|''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<sup>''n''</sup>, en utilisant ce qu'on appelle le principe du zéro-un. Même s'il est toujours exponentiel, 2<sup>''n''</sup> est plus petit que {{math|''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''<sup>n</sup>'' 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 <math>f</math> est appliquée aux entrées, c'est-à-dire si <math>x</math> et <math>y</math> sont remplacés par <math>f(x)</math> et <math>f(y)</math>, alors le comparateur produit <math>\min(f(x),f(y))= f(\min(x,y))</math> et <math>\max(f(x),f(y))= f(\max(x,y))</math>. En [[Raisonnement par récurrence|raisonnant par récurrence]] sur la profondeur du réseau, ce résultat est étendu en un [[Lemme (mathématiques)|lemme]] stipulant que si un réseau transforme une suite <math>(a_1,\ldots,a_n)</math> en <math>(b_1,\ldots, b_n)</math>, alors il transforme <math>(f(a_1),\ldots,f(a_n))</math> en <math>(f(b_1),\ldots,f(b_n))</math>.
 
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 <math>(a_1,\ldots,a_n)</math> que le réseau ne trie pas correctement. Alors il existe des entrées <math>a_i<a_j</math> avec <math>i<j</math> que le réseau échange à la sortie.
On définit une fonction monotone croissante particulière par
:<math>
f(x) = \begin{cases}
        1\ &\mbox{si } x > a_i \\
        0\ &\mbox{sinon.}
       \end{cases}
</math> 
Puisque le réseau place <math>a_j</math> avant <math>a_i</math>, le lemme dit qu'il place <math>f(a_j)</math> avant <math>f(a_i)</math> dans la séquence de sortie pour l'entrée <math>(f(a_1),\ldots,f(a_n))</math>. Mais comme <math>f(a_j) = 1</math> et <math>f(a_i) = 0</math>, le réseau ne trie pas correctement la séquence zéro-un <math>(f(a_1),\ldots,f(a_n))</math>, en contradiction avec l'hypothèse de départ<ref name="clrs"/>{{Rp|p. 686–688}}. Ceci prouve le principe du zéro-un.

== Construction de réseaux de tri ==

Malgré leur simplicité, la [[théorie des réseaux]] de tri est étonnamment profonde et complexe. Les réseaux de tri ont été étudiés pour la première fois vers 1954 par Armstrong, Nelson et O'Connor{{refm|"knuth"}} qui ensuite ont déposé un brevet pour ce concept<ref>
{{Brevet|US|3029413|"Sorting system with {{Mvar|n}}-line sorting switch", enregistré le 21 février 1957, publié le 10 avril 1962, déposé par Daniel G. O'Connor et Raymond J. Nelson}}</ref>.

Les réseaux de tri peuvent être employés soit en [[Matériel informatique|matériel]] soit en [[logiciel]]. [[Donald Knuth]] décrit la réalisation d'un comparateur d'entiers binaires par un dispositif électronique simple à trois états{{refm|"knuth"}}. En 1968, [[Ken Batcher]] suggère leur emploi pour la construction de [[Interrupteur|réseaux de commutation]] pour un ordinateur qui remplacerait à la fois les [[bus informatique]]s et les [[interrupteur]]s plus rapides mais plus coûteux<ref>{{Lien conférence |prénom=K. E. |nom=Batcher, |url=http://www.cs.kent.edu/~batcher/sort.ps |titre=Sorting networks and their applications |conférence=Proc. AFIPS Spring Joint Computer Conference |pages=307–314 |année=1968}}</ref>. Depuis les années 2000, les réseaux de tri, et particulièrement le [[tri bitonique|tri par fusion bitonique]], sont utilisés par la communauté [[General-purpose processing on graphics processing units|GPGPU]] pour la construction d'algorithmes de tri qui tournent dans le [[processeur graphique]]<ref>{{article|auteur1= J.D. Owens |auteur2= M. Houston |auteur3= D. Luebke|auteur4=S. Green |auteur5=J.E. Stone|auteur6= J.C. Phillips |titre = GPU Computing | journal = Proceedings of the IEEE  |volume=96 |  numéro =  5 |pages=879 - 899|année = mai 2008 | doi=10.1109/JPROC.2008.917757}}.</ref>.

Il existe plusieurs algorithmes pour construire des réseaux de tri simples et efficaces de profondeur {{math|''O''(log<sup>2</sup> ''n'')}} et de taille {{math|''O''(''n'' log<sup>2</sup> ''n'')}}. Parmi eux, il y a notamment<ref name="FH">{{Lien web|langue=en|url=http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/networks/sortieren.htm
|titre= Sorting Networks
|série= Algorithmen - Sortieren - Networks
|auteur= H. W. Lang   |jour= 5 |mois=  mars |année= 1997
|éditeur= FH Flensburg, Allemagne|en ligne le= 18 mai 2010|consulté le=22 juillet 2015|id=FH
}}.</ref> 
* le réseau de {{Lien|trad=Batcher odd–even mergesort|langue=en|fr=tri de fusion pair-impair de Batcher}}, 
* le [[tri bitonique]], 
* le [[tri de Shell]] et 
* le {{Lien|trad=Pairwise sorting network|langue=en|fr=réseau de tri par paires}}.
Ces réseaux sont souvent utilisés en pratique. D'autres, comme le réseau de [[tri pair-impair]] par transposition, sont plus simples à réaliser mais moins efficaces.

On peut aussi construire, au moins en théorie, des réseaux de taille arbitraire de profondeur logarithmique, en utilisant une méthode appelée ''réseau AKS'', d'après ses inventeurs [[Miklós Ajtai|Ajtai]], [[János Komlós (mathématicien)|János Komlós]], et [[Endre Szemerédi|Szemerédi]]<ref>{{article | auteur1=[[Miklós Ajtai]]|auteur2=János Komlós|auteur3=[[Endre Szemerédi]]|titre=Sorting in c log n parallel steps |périodique=Combinatorica|volume=3 |numéro=1 |passage=1-19|année=1983 |doi=10.1007/BF02579338}}.</ref>. Alors qu'il s'agit d'une découverte importante en théorie, le réseau AKS n'a que peu ou pas d'applications pratiques en raison de la constante de proportionnalité cachée dans la [[Comparaison asymptotique|notation ''O'']], et qui s'élève à plusieurs milliers<ref name="clrs"/>{{rp|669}}. Pour toutes les valeurs « pratiques » de ''n'', un réseau de profondeur {{math|''O''(log<sup>2</sup> ''n'')}} est plus efficace. La constante cachée est due en partie à la construction d'un [[Taux d'expansion (théorie des graphes)|graphe d'expansion]] employé dans la méthode. Une version simplifiée du réseau ''AKS'' a été décrite par [[Michael S. Paterson]], qui note toutefois lui aussi que « la constante pour la borne de la profondeur rend toujours la construction impraticable »<ref>
{{article | auteur1=Michael S. Paterson|titre=Improved sorting networks with O(log N) depth |périodique=Algorithmica |volume=5 |numéro=1-4 |passage=75-92|année=1990 |doi=10.1007/BF01840378}}.</ref>. Une autre construction de réseaux de tri de taille {{math|''O''(''n'' log ''n'')}} a été découverte par {{Lien|langue=en|fr=Michael T. Goodrich}}<ref>{{Lien arXiv| auteur = Michael T. Goodrich| titre = Zig-zag Sort: A Simple Deterministic Data-Oblivious Sorting Algorithm Running in O(n log n) Time| année = 2014| eprint =1403.2777}}</ref>. Même si sa constante est bien plus petite que celle du réseau AKS, sa profondeur, en {{math|''O''(''n'' log ''n'')}}, la rend inefficace pour une implémentation en parallèle.

=== Réseaux de tri optimaux ===
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 [[Diviser pour régner (informatique)|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<ref name="parberry91MST">{{article |prénom=Ian |nom=Parberry |titre=A Computer Assisted Optimal Depth Lower Bound for Nine-Input Sorting Networks |journal=Mathematical Systems Theory |volume=24 |pages=101–116 |année=1991 |url=http://larc.unt.edu/ian/pubs/9-input.pdf}}</ref>. La table suivante donne les résultats d'optimalité connus : 

{| class="wikitable" style="text-align: center;"
|-
! style="text-align: left;" | <!-- Modèle:Mvar -->{{Mvar|n}}
| style="width: 20px;" | 1 || style="width: 20px;" | 2 || style="width: 20px;" | 3 || style="width: 20px;" | 4 || style="width: 20px;" | 5 || style="width: 20px;" | 6 || style="width: 20px;" | 7 || style="width: 20px;" | 8 || style="width: 20px;" | 9 || style="width: 20px;" | 10 || style="width: 20px;" | 11 || style="width: 20px;" | 12 || style="width: 20px;" | 13 || style="width: 20px;" | 14 || style="width: 20px;" | 15 || style="width: 20px;" | 16
|- 
! style="text-align: left;" | Profondeur<ref name="bundala_zavodny"/>
| 0 || 1 || 3 || 3 || 5 || 5 || 6 || 6 || 7 || 7 || 8 || 8 || 9 || 9 || 9 || 9
|- 
! style="text-align: left;" | Taille, majorant<ref name="codish"/>
| 0 || 1 || 3 || 5 || 9 || 12 || 16 || 19 || 25 || 29 || 35 || 39 || 45 || 51 || 56 || 60
|- 
! style="text-align: left;" | Taille, minorant (si différent)<ref name="codish"/>
|  ||  ||  ||  ||  ||  ||  ||  ||  ||  || 33 || 37 || 41 || 45 || 49 || 53
|}

Les seize premiers réseaux optimaux en profondeurs sont listés dans la section 5.3.4: « Networks for Sorting » du livre ''[[The Art of Computer Programming|Art of Computer Programming]]'' de Knuth<ref name="knuth">Section 5.3.4: Networks for Sorting, pages 219–247, dans {{Knuth-TAOCPVol3}}.</ref> 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<ref name="bundala_zavodny">{{article| doi = 10.1007/978-3-319-04921-2_19| titre = Optimal Sorting Networks| journal = Language and Automata Theory and Applications| collection = Lecture Notes in Computer Sceince | numéro dans collection = 8370| passage = 236-247 | année = 2014| nom1 = Bundala | prénom1 = Daniel | nom2 = Závodný | prénom2 = Jakub | isbn = 978-3-319-04920-5| arxiv = 1310.6271}}</ref>. 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<ref name="parberry91MST"/>. Une autre technique pour trouver des réseaux optimaux est décrite dans une page de Jason D. Hugues<ref>{{Lien web
|langue= en
|url= http://www.cs.brandeis.edu/~hugues/sorting_networks.html
|titre= Sorting networks and the END algorithm
|série= Rabb School of Continuing Studies
|auteur= Jason D. Hugues
|éditeur= Brandeis University 
|consulté le=22 juillet 2015
|id= Hugues
}}.</ref>.

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 {{math|''S''(''n'')}} peuvent être déduit inductivement d'un lemme dû à Van Voorhis : <math>S(n+1)\ge S(n)+\lceil\log_2n\rceil</math>. Les dix réseaux optimaux sont connus depuis 1969, dont les huit premiers sont connus de Floyd et Knuth, mais l'optimalité des cas {{math|''n'' {{=}} 9}} et {{math|''n'' {{=}} 10}} n'a été prouvée qu'en 2014<ref name="codish">La preuve est annoncée dans {{Lien arXiv 
|auteur =  Michael Codish, Luís Cruz-Filipe, Michael Frank et Peter Schneider-Kamp
|eprint=1405.5754 
|titre=Twenty-Five Comparators is Optimal when Sorting Nine Inputs (and Twenty-Nine for Ten)  |année=2014 }}. L'article en revue paraît en 2016 : {{Article | auteur1 = Michael Codish | auteur2 = Luís Cruz-Filipe | auteur3 = Michael Frank | auteur4 = Peter Schneider-Kamp | titre = Sorting nine inputs requires twenty-five comparisons | périodique = Journal of Computer and System Sciences | éditeur = Elsevier BV | volume = 82 | numéro = 3 | mois = mai | année = 2016 | pages = 551-563 | ISSN = 0022-0000 | doi = 10.13039/501100003977}}.</ref>. De nouveaux résultats (en 2017)<ref name="BundalaCodish2017">{{article|langue=en|nom1=Bundala|prénom1=Daniel|nom2=Codish|prénom2=Michael|nom3=Cruz-Filipe|prénom3=Luís|nom4=Schneider-Kamp|prénom4=Peter|nom5=Závodný|prénom5=Jakub|titre=Optimal-depth sorting networks|journal=Journal of Computer and System Sciences|volume=84|année=2017|pages=185–204|doi=10.1016/j.jcss.2016.09.004}}.</ref> donnent une réponse sur l'optimalité en profondeur.

=== Complexité de test de réseaux de tri ===

La complexité du problème de tester si un réseau de tri est correct est dans la classe des problèmes [[co-NP]]-complets<ref name="parberry91">
{{Lien conférence |nom=Parberry|prénom=Ian|titre=On the Computational Complexity of Optimal Sorting Network Verification|journal=Proc. PARLE '91: Parallel Architectures and Languages Europe, Volume I: Parallel Architectures and Algorithms, Eindhoven, The Netherlands |année=1991|pages=252–269}}.</ref>{{,}}<ref>{{chapitre|titre=On the Computational Complexity of Optimal Sorting Network Verification |prénom= Ian|nom= Parberry|auteur= |date= |année=1991 |ouvrage= PARLE '91: Parallel Architectures and Languages Europe|volume = I. Parallel Architectures and Algorithms|collection = Lecture Notes in Computer Science | numéro dans collection = 505 |éditeur=Springer |pages=252–269 }}.</ref>. Le cas général est donc intraitable.

== Notes et références ==
{{Références}}
{{Traduction/Référence|en|Sorting network|665477275|type=note}}

== Lien externe ==
* {{Lien web |url=http://rjlipton.wordpress.com/2014/04/24/galactic-sortning-networks/ |prénom1=Richard J. |nom1=Lipton |lien auteur1=Richard J. Lipton |prénom2=Ken |nom2=Regan |date=24 avril 2014 |titre=Galactic Sorting Networks |website=Gödel’s Lost Letter and P=NP}}

{{portail|Informatique théorique}}

[[Catégorie:Algorithme de tri]]