Réseau de tri | EPFL Graph Search

Ê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 GraphSearch.

Découvrez-en plus sur les applications Graph.

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.

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

Personnes associées (1)

Concepts associés (5)

Cours associés (8)

Séances de cours associées (160)

MOOCs associés (2)

Réseau de tri

Comparison sort

A comparison sort is a type of sorting algorithm that only reads the list elements through a single abstract comparison operation (often a "less than or equal to" operator or a three-way comparison) that determines which of two elements should occur first in the final sorted list. The only requirement is that the operator forms a total preorder over the data, with: if a ≤ b and b ≤ c then a ≤ c (transitivity) for all a and b, a ≤ b or b ≤ a (connexity). It is possible that both a ≤ b and b ≤ a; in this case either may come first in the sorted list.

The Art of Computer Programming

The Art of Computer Programming (TAOCP) est une série de livres en plusieurs volumes sur la programmation informatique, écrits par Donald Knuth : Volume 1, Fundamental Algorithms (troisième édition 1997) ; Volume 2, Seminumerical Algorithms (troisième édition 1997) ; Volume 3, Sorting and Searching (seconde édition, 1998) ; Volume 4A, Combinatorial Algorithms, Part 1 (2011) ; Volume 4B, Combinatorial Algorithms, Part 2 (2022). En 2022, sur les sept volumes initialement prévus, seuls l’entièreté des trois premiers volumes et les deux premiers tomes du quatrième volume ont été publiés.

Organisé en deux parties, ce cours présente les bases théoriques et pratiques des systèmes d’information géographique, ne nécessitant pas de connaissances préalables en informatique. En suivant cette

Discrete mathematics is a discipline with applications to almost all areas of study. It provides a set of indispensable tools to computer science in particular. This course reviews (familiar) topics a

The labels "biosensor" and "eBiochip" have been employed to refer to the most diverse systems and in several fields of application. The course is meant not only to provide means to dig into this sea

The students learn the theory and practice of basic concepts and techniques in algorithms. The course covers mathematical induction, techniques for analyzing algorithms, elementary data structures, ma

Sans titre CS-250: Algorithms I

Requêtes conditionnelles : résumé MOOC: Geographical Information Systems 1

Couvre les principales fonctions d'agrégation pour les calculs statistiques sur les ensembles de données.

Requêtes d'agrégation et tri MOOC: Geographical Information Systems 1

Couvre les principales fonctions d'agrégation pour les calculs statistiques sur les ensembles de données.