Algorithme de tri, tel que chaque élément est comparé

39

Existe-t-il des algorithmes de tri comparatifs connus qui ne se réduisent pas au tri des réseaux, de telle sorte que chaque élément soit comparé ?O(logn)

Autant que je sache, le seul moyen de trier avec comparaison sur chaque élément est de construire un réseau de tri AKS pour n entrées et d'exécuter l'entrée sur le réseau de tri.O(logn)n

AKS n'est pas facile à implémenter et a un facteur constant peu pratique, il existe donc des motivations pour rechercher d'autres algorithmes.

Un algorithme avec des comparaisons par article qui ne semble pas impliquer un réseau de tri est présenté ici . (iirc, cela a été présenté pour la première fois par Rob Johnson au séminaire sur les algorithmes de Stony Brook).O(log2n)

Chao Xu
la source
2
Je ne comprends pas la question: de nombreux algorithmes séquentiels semblent correspondre à votre demande. Par exemple, le tri par fusion est un algorithme de tri classique et ne fait pas plus que comparaison log n par élément. Peut-être vous interrogez-vous sur les algorithmes de tri parallèle ? logn
Jeremy
4
@ Jeremy: Si la fusion de deux listes, et ( b 1 , . . . , B n ) , vous pouvez finir par comparer un 1 contre chacun des b 1 , . . . , b n , c’est-à-dire Ω ( n ) comparaisons pour un élément. Et ce n'était qu'une étape de "fusion". Bien sûr la moyenne(a1,...,an)(b1,...,bn)a1b1,...,bnΩ(n)Le nombre de comparaisons est nécessairement faible, mais la question concerne la complexité du cas le plus défavorable .
Jukka Suomela
6
Je crois que c'est possible. Les réseaux de tri sont des données inconscientes et disposent de moyens de comparaison prédéterminés, mais un algorithme de tri peut être capable de choisir entre différents ensembles d'opérations dépendant des données. On peut modifier trier de fusion dans un algorithme avec comparaison pour chaque élément, et ne semble pas impliquer un réseau de tri reddit.com/comments/9jqsi/...O(log2n)
Chao Xu
1
(une1,,unen)(b1,,bn)nlgn
2
Maintenant, il y a une nouvelle question connexe (mais j'espère beaucoup plus facile): cstheory.stackexchange.com/questions/8073/…
Jukka Suomela

Réponses:

17

Après en avoir discuté avec Michael T. Goodrich, il semble que l’algorithme de tri parallèle de Cole pour EREW PRAM remplisse son rôle. Voir

O(bûchen)O(1)

Une extension de cet algorithme pour la machine à pointeur parallèle est donnée dans

Quelqu'un
la source
Nous aimerions savoir qui vous êtes! : D
Tayfun Pay
@quelqu'un est Sergio Cabello
quelqu'un
O(bûchen)O(bûchen)