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?

Improve this question
$\endgroup$
6
  • 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, 2019 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, 2019 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, 2019 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, 2019 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, 2019 at 21:04

1 Answer 1

Reset to default
35
$\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 $$

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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