¿Hay algún algoritmo de clasificación de comparación conocido que no se reduzca a redes de clasificación, de modo que cada elemento se compare veces?
Hasta donde sé, la única forma de ordenar con la comparación en cada elemento es construir una red de clasificación AKS para n entradas, y ejecutar la entrada en la red de clasificación.
AKS no es fácil de implementar y tiene un factor constante poco práctico, por lo que existen motivaciones para buscar otros algoritmos.
Aquí se presenta un algoritmo con comparaciones por ítem que no parece implicar una red de clasificación . (IIRC, esto fue presentado por primera vez por Rob Johnson en el seminario de algoritmos de Stony Brook).
ds.algorithms
sorting
sorting-network
Chao Xu
fuente
fuente
Respuestas:
Al discutir esto con Michael T. Goodrich, parece que el algoritmo de clasificación paralela de Cole para EREW PRAM hace el trabajo. Ver
En ese algoritmo hay rondas y en cada ronda cada elemento participa en comparaciones O ( 1 ) . (Uno tiene que entender el algoritmo para ver que no abusamos de hacer copias de cada elemento).O(logn) O(1)
Una extensión de ese algoritmo para la máquina de puntero paralelo se da en
fuente