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?
Can the sorting of a list be verified without comparing neighbors?
How do I get past a 3-year ban from overstay with VWP?
Is it a bad idea to replace pull-up resistors with hard pull-ups?
Understanding basic photoresistor circuit
What are some possible reasons that a father's name is missing from a birth certificate - England?
How could we transfer large amounts of energy sourced in space to Earth?
Help decide course of action for rotting windows
Washer drain pipe overflow
Can you book a one-way ticket to the UK on a visa?
Why does "decimal.TryParse()" always return 0 for the input string "-1" in the below code?
Thesis' "Future Work" section – is it acceptable to omit personal involvement in a mentioned project?
Are there variations of the regular runtimes of the Big-O-Notation?
International Code of Ethics for order of co-authors in research papers
Can 'sudo apt-get remove [write]' destroy my Ubuntu?
What is the best way for a skeleton to impersonate human without using magic?
LocalDate.plus Incorrect Answer
Is a vertical stabiliser needed for straight line flight in a glider?
Why did God specifically target the firstborn in the 10th plague (Exodus 12:29-36)?
Why was the Ancient One so hesitant to teach Dr. Strange the art of sorcery?
Does a member have to be initialized to take its address?
What did Rocket give Hawkeye in "Avengers: Endgame"?
Is Simic Ascendancy triggered by Awakening of Vitu-Ghazi?
Why was this sacrifice sufficient?
Two researchers want to work on the same extension to my paper. Who to help?
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 3 hours ago
Display NameDisplay Name
1183
$endgroup$
add a 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 3 hours ago
Display NameDisplay Name
1183
$endgroup$
$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
10 mins ago
add a 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 3 hours ago
Display NameDisplay Name
1183
$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 3 hours ago
Display NameDisplay Name
1183
asked 3 hours ago
Display NameDisplay Name
1183
asked 3 hours ago
Display NameDisplay Name
1183
asked 3 hours ago
Display NameDisplay Name
1183
asked 3 hours ago
Display NameDisplay Name
1183
1183
$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
10 mins ago
add a comment |
$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
10 mins ago
$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
10 mins ago
$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
10 mins ago
add a 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 2 hours ago
Yuval FilmusYuval Filmus
198k15187351
$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 2 hours ago
Yuval FilmusYuval Filmus
198k15187351
$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 2 hours ago
Yuval FilmusYuval Filmus
198k15187351
$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 2 hours ago
Yuval FilmusYuval Filmus
198k15187351
$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 2 hours ago
Yuval FilmusYuval Filmus
198k15187351
answered 2 hours ago
Yuval FilmusYuval Filmus
198k15187351
answered 2 hours ago
Yuval FilmusYuval Filmus
198k15187351
answered 2 hours ago
Yuval FilmusYuval Filmus
198k15187351
198k15187351
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
$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
10 mins ago