Worldlex Wiki Le réseau de tri par paires est un réseau de tri découvert et publié par Ian Parberry en 1992 dans Parallel Processing Letters . Le réseau de tri par paires a la même taille (nombre de comparateurs) et la même profondeur que le réseau de tri par fusion pair-impair . Au moment de la publication, le réseau était l'un des nombreux réseaux connus avec une profondeur de . Il nécessite des comparateurs et a une profondeur de .
La procédure de tri mise en œuvre par le réseau est la suivante (guidée par le principe zéro-un ) :
- Trier les bits consécutifs par paires de l'entrée (correspond à la première couche du diagramme)
- Trier toutes les paires dans l'ordre lexicographique en triant récursivement tous les bits impairs et les bits pairs séparément (correspond aux 14 couches suivantes du diagramme)
- Trier les paires dans l'ordre non décroissant à l'aide d'un réseau spécialisé (correspond aux dernières couches du diagramme)
Relation avec le tri par fusion impair-pair de Batcher
Le réseau de tri par paires est très similaire au tri par fusion impair-pair de Batcher, mais diffère dans la structure des opérations. Alors que Batcher divise, trie et fusionne de manière répétée des sous-séquences de plus en plus longues, la méthode par paires effectue d'abord toute la subdivision, puis effectue toute la fusion à la fin dans la séquence inverse. Dans certaines applications comme l'encodage des contraintes de cardinalité, le réseau de tri par paires est supérieur au réseau Batcher.