Existe algum algoritmo de classificação de comparação conhecido que não se reduz a redes de classificação, de modo que cada elemento seja comparado vezes?
Até onde eu sei, a única maneira de classificar com a comparação em cada elemento é construir uma rede de classificação AKS para entradas e executar a entrada na rede de classificação.n
A AKS não é fácil de implementar e possui um fator constante impraticável; portanto, existem motivações para procurar outros algoritmos.
Um algoritmo com comparações por item que não parece implicar em uma rede de classificação é apresentado aqui . (iirc, isso foi apresentado pela primeira vez por Rob Johnson no seminário sobre algoritmos de Stony Brook).
ds.algorithms
sorting
sorting-network
Chao Xu
fonte
fonte
Respostas:
Ao discutir isso com Michael T. Goodrich, parece que o algoritmo de classificação paralela de Cole para o EREW PRAM faz o trabalho. Vejo
Nesse algoritmo, existem rodadas e em cada rodada cada elemento participa das comparações O ( 1 ) . (É preciso entender o algoritmo para garantir que não abusemos de fazer cópias de cada elemento.)O(logn) O(1)
Uma extensão desse algoritmo para a máquina de ponteiro paralelo é dada em
fonte