Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Réseau de tri
Résumé
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 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 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 hardware. Elle peut aussi être vue comme une protection contre un logiciel malveillant qui chercherait à examiner la nature des séquences triées.
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 x et le fil inférieur y, alors après avoir touché un comparateur les fils portent et respectivement, de sorte que la paire de valeur est triée.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.