14
$\begingroup$

A $n$-item list can be verified as sorted by comparing every item to its neighbor. In my application, I will not be able to compare every item with its neighbor: instead, the comparisons will sometimes be between distant elements. Given that the list contains more than three items and also that comparison is the only supported operation, does there ever exist a "network" of comparisons that will prove that the list is sorted, but is missing at least one direct neighbor-to-neighbor comparison?

Formally, for a sequence of elements $e_i$, I have a set of pairs of indices $(j,k)$ for which I know whether $e_j > e_k$, $e_j = e_k$, or $e_j < e_k$. There exists a pair $(l,l+1)$ that is missing from the set of comparisons. Is it ever possible, then, to prove that the sequence is sorted?

$\endgroup$
  • 1
    $\begingroup$ A note in case anyone finds this page later with the question of whether you can verify a list is sorted without comparing anything; Only if you can put some limits on the inputs, and/or know something about the shape of the inputs; (e.g. radix sort). $\endgroup$ – HammerN'Songs May 10 at 21:57
  • $\begingroup$ There is, however, the possibility of optimizing the number of comparisons used in cases where it's not sorted. $\endgroup$ – Acccumulation May 10 at 22:29
  • 1
    $\begingroup$ @Acccumulation Is there actually such a possibility? Should be trivial to take any such program and cook up an adversarial list of length n that forces the program to do n-1 comparisons. See also A Killer Adversary for QuickSort, which takes this idea even further to forcing quicksort into the bad part of its asymptotic analysis. $\endgroup$ – Daniel Wagner May 11 at 1:47
  • $\begingroup$ @DanielWagner Yes, such optimization has to be done with respect to expected input of the particular application. $\endgroup$ – Acccumulation May 11 at 17:35
  • $\begingroup$ Probably not possible. But please clarify: did you mean that you only know the comparisons of the form (j,j+1), not general (j,k)? For example, do you ever know the comparison of two items of indices (j,j+3) ? $\endgroup$ – Ron May 11 at 21:04
34
$\begingroup$

It is impossible. Suppose that you have the result of all comparisons except for the pair $(i,i+1)$. Then you wouldn't be able to distinguish between the following two cases: $$ 1,2,\ldots,i-1,i,i+1,i+2,\ldots,n \\ 1,2,\ldots,i-1,i+1,i,i+2,\ldots,n $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.