Algoritmo de classificação, de modo que cada elemento seja comparado

39

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?O(logn)

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.nO(logn)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).O(log2n)

Chao Xu
fonte
2
Não entendi a pergunta: muitos algoritmos seqüenciais parecem corresponder à sua solicitação. por exemplo, Merge sort é um algoritmo de classificação clássico e não faz mais do que comparação por elemento. Talvez você esteja perguntando sobre algoritmos de classificação paralela ? logn
Jeremy
4
@ Jeremy: se você mesclar duas listas, e , poderá acabar comparando com cada uma das , ou seja, Comparações de por um elemento. E este foi apenas um passo de "mesclagem". É claro que o número médio de comparações é necessariamente pequeno, mas a questão é sobre a pior complexidade possível. ( b 1 , . . . , B n ) um 1 b 1 , . . . , b n Ω ( n )(a1,...,an)(b1,...,bn)a1b1,...,bnΩ(n)
Jukka Suomela
6
Eu acredito que isso é possível. As redes de classificação são inconscientes dos dados e têm formas predeterminadas de comparação, mas um algoritmo de classificação pode ser capaz de escolher entre diferentes conjuntos de operações, dependendo dos dados. Pode-se modificar merge sort em um algoritmo com comparação para cada elemento, e não parece implicar uma rede de classificação reddit.com/comments/9jqsi/...O(log2n)
Chao Xu
1
Jukka: Obrigado, entendi seu ponto. Mas isso é apenas ao usar a mesclagem ingênua: é possível mesclar com usando a pesquisa duplicada para colocar cada elemento, o que ainda é comparações no pior dos casos, mas comparações por elemento no máximo, o que produz a versão da classificação de mesclagem mencionada pelo Chao. ( b 1 , , b n ) n lg n(a1,,an)(b1,,bn)nlgn
Jeremy
2
Agora há uma nova pergunta relacionada (mas espero que muito mais fácil): cstheory.stackexchange.com/questions/8073/...
Jukka Suomela

Respostas:

17

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

alguém
fonte
Gostaríamos de saber quem você é! : D
Tayfun Pago
@someone é Sergio Cabello
alguém
O(logn)O(logn)