Red de ordenamiento por pares

La red de ordenamiento por pares es una red de ordenamiento descubierta y publicada por Ian Parberry en 1992 en Parallel Processing Letters . ^[1] La red de ordenamiento por pares tiene el mismo tamaño (número de comparadores) y profundidad que la red de ordenamiento por fusión de pares e impares . En el momento de la publicación, la red era una de varias redes conocidas con una profundidad de . Requiere comparadores y tiene una profundidad de . ${\displaystyle O(\log ^{2}n)}$ ${\displaystyle n(\log n)(\log n-1)/4+n-1}$ ${\displaystyle (\log n)(\log n+1)/2}$

El procedimiento de clasificación implementado por la red es el siguiente (guiado por el principio cero-uno ):

1. Ordenar pares consecutivos de bits de la entrada (corresponde a la primera capa del diagrama)
2. Ordene todos los pares en orden lexicográfico ordenando recursivamente todos los bits impares y pares por separado (corresponde a las siguientes 14 capas del diagrama)
3. Ordenar los pares en orden no decreciente utilizando una red especializada (corresponde a las capas finales del diagrama)

Relación con la combinación de ordenamiento impar-par de Batcher

La red de ordenación por pares es muy similar a la red de ordenación por combinación de pares e impares de Batcher, pero difiere en la estructura de las operaciones. Mientras que Batcher divide, ordena y fusiona repetidamente subsecuencias cada vez más largas, el método por pares realiza primero toda la subdivisión y luego toda la fusión al final en la secuencia inversa. En ciertas aplicaciones, como la codificación de restricciones de cardinalidad, la red de ordenación por pares es superior a la red de Batcher. ^[2]

Referencias

1. Parberry, Ian (1992), "The Pairwise Sorting Network" (PDF) , Parallel Processing Letters , 2 (2, 3): 205–211, doi :10.1142/S0129626492000337, S2CID  2986739, archivado desde el original (PDF) el 2019-10-29
2. "Redes de ordenación".

Enlaces externos

• Redes de Ordenamiento – Archivo de página web del autor.