Can the sorting of a list be verified without comparing neighbors?How many comparisons in the worst case, does it take to merge 3 sorted lists of size n/3?Why does this mergesort variant not do Θ(n) comparisons on average?Can the zero-one principle be used to prove the stability of a sorting networkElement-wise merging and re-sorting lists of sorted elementsHow to prove a greedy algorithm that uses the longest increasing subsequence?Analysis on comparisons in a heap-like sorting algorithmReverse engineer sorting algorithmOptimize sorting matrix entries by row and columnSorting lower bounds for almost sorted arrayCan this “double pop” Heapsort variation speed up sorting on average?
Is it possible to remotely hack the GPS system and disable GPS service worldwide?
Python program to take in two strings and print the larger string
How did NASA Langley end up with the first 737?
Can I install a back bike rack without attachment to the rear part of the frame?
Manager questioning my time estimates for a project
WordPress 5.2.1 deactivated my jQuery
Why did Jon Snow do this immoral act if he is so honorable?
Function argument returning void or non-void type
Best material to absorb as much light as possible
What's difference between "depends on" and "is blocked by" relations between issues in Jira next-gen board?
Find this cartoon
How to patch glass cuts in a bicycle tire?
Is it legal to have an abortion in another state or abroad?
Why is the Eisenstein ideal paper so great?
Drums and punctuation
Why would a rational buyer offer to buy with no conditions precedent?
Is there any relationship between frequency of signal and distance it travels?
Why are Stein manifolds/spaces the analog of affine varieties/schemes in algebraic geometry?
Why isn't Tyrion mentioned in the in-universe book "A Song of Ice and Fire"?
Gravitational Force Between Numbers
What Armor Optimization applies to a Mithral full plate?
How do I superimpose two math symbols?
便利な工具 what does な means
Did 20% of US soldiers in Vietnam use heroin, 95% of whom quit afterwards?
Can the sorting of a list be verified without comparing neighbors?
How many comparisons in the worst case, does it take to merge 3 sorted lists of size n/3?Why does this mergesort variant not do Θ(n) comparisons on average?Can the zero-one principle be used to prove the stability of a sorting networkElement-wise merging and re-sorting lists of sorted elementsHow to prove a greedy algorithm that uses the longest increasing subsequence?Analysis on comparisons in a heap-like sorting algorithmReverse engineer sorting algorithmOptimize sorting matrix entries by row and columnSorting lower bounds for almost sorted arrayCan this “double pop” Heapsort variation speed up sorting on average?
$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?
sorting
asked May 10 at 18:58
Display NameDisplay Name
1965
$endgroup$
|
show 1 more comment
$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?
sorting
asked May 10 at 18:58
Display NameDisplay Name
1965
$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
|
show 1 more comment
$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?
sorting
asked May 10 at 18:58
Display NameDisplay Name
1965
$endgroup$
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?
sorting
sorting
asked May 10 at 18:58
Display NameDisplay Name
1965
asked May 10 at 18:58
Display NameDisplay Name
1965
asked May 10 at 18:58
Display NameDisplay Name
1965
asked May 10 at 18:58
Display NameDisplay Name
1965
asked May 10 at 18:58
Display NameDisplay Name
1965
1965
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
|
show 1 more comment
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
1
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$
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
$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
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$
@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$
@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
$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
|
show 1 more comment
1 Answer
1
active
oldest
votes
$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
$$
answered May 10 at 19:24
Yuval FilmusYuval Filmus
200k15193355
$endgroup$
add a comment |
Your Answer
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "419"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);
else
createEditor();
);
function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);
);
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f109204%2fcan-the-sorting-of-a-list-be-verified-without-comparing-neighbors%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$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
$$
answered May 10 at 19:24
Yuval FilmusYuval Filmus
200k15193355
$endgroup$
add a comment |
$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
$$
answered May 10 at 19:24
Yuval FilmusYuval Filmus
200k15193355
$endgroup$
add a comment |
$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
$$
answered May 10 at 19:24
Yuval FilmusYuval Filmus
200k15193355
$endgroup$
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
$$
answered May 10 at 19:24
Yuval FilmusYuval Filmus
200k15193355
answered May 10 at 19:24
Yuval FilmusYuval Filmus
200k15193355
answered May 10 at 19:24
Yuval FilmusYuval Filmus
200k15193355
answered May 10 at 19:24
Yuval FilmusYuval Filmus
200k15193355
200k15193355
add a comment |
add a comment |
Thanks for contributing an answer to Computer Science Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f109204%2fcan-the-sorting-of-a-list-be-verified-without-comparing-neighbors%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
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