Tri pair-impair

Un réseau de comparateurs est fait de fils et de comparateurs. Les comparateurs comparent et échangent si nécessaire les données qui entrent par les données qui se trouvent sur les fils. Un réseau de tri est un réseau de comparateurs qui tri correctement les données. Le principe du zéro-un dit qu'un réseau de comparateurs est un réseau de tri s'il tri correctement les suites composées de 0 et de 1.

Un comparateurs pour les fils ${\displaystyle i}$ et ${\displaystyle j}$ se note ${\displaystyle [i:j]}$. Le réseau pair-impair de n données est composé de n/2 tranches de comparateurs. Chaque tranche comporte n comparateurs, d'abord de la forme ${\displaystyle [i:i+1]}$ pour les entiers ${\displaystyle i}$ pairs (si on commence à 0) puis de la forme ${\displaystyle [i:i+1]}$ pour les entiers ${\displaystyle i}$ impairs. La taille d'un tel réseau est ${\displaystyle n^{2}/2}$, sa profondeur est ${\displaystyle n}$. Ces deux nombres sont trop élevés pour en faire un réseau efficace en pratique pour des volumes importants, mais il a une structure particulièrement simple[1] - [2] L'algorithme a été présenté à l'origine par Habermann en 1972[3]. Il s'étend au cas de plusieurs items par comparateur (processeur). Ainsi, dans l'algorithme pair-impair de division-fusion de Baudet et Stevenson[4], chaque processeur trie sa propre sous-liste à chaque étape, en utilisant un algorithme propre, puis réalise une fusion avec son voisin, où les voisins alternent entre pair-impair et impair-pair à chaque étape[5].

Tri pair-impair démonstration, deuxième cas.

Par le principe du zéro-un, il suffit de démontrer qu'une suite de 0 et 1 est correctement triée. La preuve est par récurrence sur le nombre n d'éléments à trier.

Quand n=1, le réseau est composé d'un seul fil sans comparateurs, et la suite est correctement trié. Supposons donc n>1, et soit ${\displaystyle (a_{0},\ldots ,a_{n-1})}$ une suite de 0 et 1.

Si ${\displaystyle a_{n-1}=1}$, les comparateurs ${\displaystyle [n-2:n-1]}$ sont inutiles. Si on supprime ces comparateurs, il reste un réseau pair-impair à ${\displaystyle n-1}$ fils qui, par hypothèse de récurrence, trie la suite ${\displaystyle (a_{0},\ldots ,a_{n-2})}$ de longueur ${\displaystyle n-1}$. Comme l'élément ${\displaystyle a_{n-1}=1}$ est déjà à sa bonne place, la suite entière est déjà triée, et réintroduire les comparateurs ${\displaystyle [n-2:n-1]}$ ne modifie pas le résultat.

Si en revanche ${\displaystyle a_{n-1}=0}$, les comparateurs impliqués par cette valeur sont successivement ${\displaystyle [n-2:n-1],[n-3:n-2],\ldots ,[0,1]}$, et on peut considérer qu'ils réalisent chacun un échange (même si l'échange de deux valeurs toutes deux égales à 0 ne produit pas d'effet visible). On peut alors remplacer ces comparateurs correspondants par des lignes qui se croisent, et en "rehaussant" la deuxième partie du réseau d'un fil, on est ramené à un réseau à ${\displaystyle n-1}$ entrées[2].