Le tri d'une liste peut-il être vérifié sans comparer les voisins?

14

Une liste de n éléments peut être vérifiée comme triée en comparant chaque élément à son voisin. Dans mon application, je ne pourrai pas comparer chaque élément avec son voisin: au lieu de cela, les comparaisons se feront parfois entre des éléments distants. Étant donné que la liste contient plus de trois éléments et que la comparaison est la seule opération prise en charge, existe-t-il un "réseau" de comparaisons qui prouvera que la liste est triée, mais qu'il manque au moins un voisin à voisin direct Comparaison?

Formellement, pour une séquence d'éléments ei , j'ai un ensemble de paires d'indices (j,k) pour lesquelles je sais si ej>ek , ej=ek , ou ej<ek . Il existe une paire (l,l+1) qui manque dans l'ensemble des comparaisons. Peut-on alors prouver que la séquence est triée?

sorting Afficher un nom
la source
1
Une note au cas où quelqu'un trouverait cette page plus tard avec la question de savoir si vous pouvez vérifier qu'une liste est triée sans rien comparer; Seulement si vous pouvez mettre des limites aux entrées et / ou connaître la forme des entrées; (par exemple, tri radix).
HammerN'Songs
Il y a cependant la possibilité d'optimiser le nombre de comparaisons utilisées dans les cas où il n'est pas trié.
Accumulation
1
@Acccumulation Existe-t-il réellement une telle possibilité? Devrait être trivial de prendre un tel programme et de préparer une liste contradictoire de longueur n qui oblige le programme à faire n-1 comparaisons. Voir aussi A Killer Adversary for QuickSort , qui pousse cette idée encore plus loin pour forcer le tri rapide dans la mauvaise partie de son analyse asymptotique.
Daniel Wagner
@DanielWagner Oui, une telle optimisation doit être effectuée par rapport à l'entrée attendue de l'application particulière.
Accumulation
Probablement pas possible. Mais veuillez clarifier: vouliez-vous dire que vous ne connaissez que les comparaisons de la forme (j, j + 1), pas générales (j, k)? Par exemple, connaissez-vous déjà la comparaison de deux éléments d'indices (j, j + 3)?
Ron

Réponses:

34

(je,je+1). Vous ne pourrez alors pas distinguer les deux cas suivants:

1,2,…,je-1,je,je+1,je+2,…,n1,2,…,je-1,je+1,je,je+2,…,n

Yuval Filmus
la source