Diagramme interactif de reseaux de tri avec animation pas a pas
Un reseau de tri est un reseau de comparateurs a structure fixe qui trie toute sequence d'entree en utilisant un arrangement predetermine d'operations de comparaison et d'echange. Contrairement aux algorithmes adaptatifs comme le tri rapide, un reseau de tri effectue exactement les memes comparaisons independamment des donnees d'entree.
Chaque comparateur connecte deux fils (positions i et j) et dirige la plus petite valeur vers le fil superieur et la plus grande vers le fil inferieur. Si les valeurs sont deja dans l'ordre, rien ne change ; sinon, elles sont echangees.
La profondeur d'un reseau de tri est le nombre maximum de couches de l'entree a la sortie. Les comparateurs a la meme profondeur n'ont pas de dependances de donnees et peuvent s'executer simultanement en parallele.
Les algorithmes de tri traditionnels decident de la prochaine comparaison en fonction des resultats precedents. Les reseaux de tri predeterminent toutes les comparaisons, les rendant ideaux pour l'implementation materielle et le calcul parallele sur GPU.
Les reseaux de tri sont largement utilises dans : le tri sur GPU (le tri bitonique est la base du tri CUDA), la conception de circuits de tri materiels, le tri oblitere en calcul securise, l'optimisation de requetes de bases de donnees et le tri de paquets reseau.
Pour les petits N, les comptes optimaux connus sont : N=4 requiert 5 comparateurs, N=5 necessite 9, N=6 necessite 12, N=7 necessite 16, N=8 necessite 19, N=9 necessite 25, N=10 necessite 29, N=16 necessite 60. Le principe 0-1 prouve que verifier toutes les 2^N entrees binaires suffit pour confirmer la correction du reseau.