Checking whether given array is sorted by divide-and-conquer
$begingroup$
I've written a code that I try to use divide and conquer approach to determine if the given array is sorted. I wonder whether I apply the approach accurately.
public static boolean isSorted(List<Integer> arr, int start, int end) {
if (end - start == 1) // base case to compare two elements
return arr.get(end) > arr.get(start);
int middle = (end + start) >>> 1; // division by two
boolean leftPart = isSorted(arr, start, middle);
boolean rightPart = isSorted(arr, middle, end);
return leftPart && rightPart;
}
To use call,
isSorted(list, 0, list.size() - 1)
java algorithm array recursion divide-and-conquer
edited Nov 24 '18 at 22:24
Martin R
16.1k12364
asked Nov 24 '18 at 19:24
itsnotmyrealnameitsnotmyrealname
1625
$endgroup$
add a comment |
$begingroup$
I've written a code that I try to use divide and conquer approach to determine if the given array is sorted. I wonder whether I apply the approach accurately.
public static boolean isSorted(List<Integer> arr, int start, int end) {
if (end - start == 1) // base case to compare two elements
return arr.get(end) > arr.get(start);
int middle = (end + start) >>> 1; // division by two
boolean leftPart = isSorted(arr, start, middle);
boolean rightPart = isSorted(arr, middle, end);
return leftPart && rightPart;
}
To use call,
isSorted(list, 0, list.size() - 1)
java algorithm array recursion divide-and-conquer
edited Nov 24 '18 at 22:24
Martin R
16.1k12364
asked Nov 24 '18 at 19:24
itsnotmyrealnameitsnotmyrealname
1625
$endgroup$
3
$begingroup$
Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers.
$endgroup$
– Martin R
Nov 24 '18 at 22:24
$begingroup$
Test your code on3, 4, 1, 2.
$endgroup$
– vnp
Nov 25 '18 at 6:43
$begingroup$
@vnpisSorted(list, 0, 3)will callisSorted(arr, 1, 3)which will callisSorted(arr, 1, 2)which will returnfalse. That test case is fine.
$endgroup$
– AJNeufeld
Nov 25 '18 at 18:02
add a comment |
$begingroup$
I've written a code that I try to use divide and conquer approach to determine if the given array is sorted. I wonder whether I apply the approach accurately.
public static boolean isSorted(List<Integer> arr, int start, int end) {
if (end - start == 1) // base case to compare two elements
return arr.get(end) > arr.get(start);
int middle = (end + start) >>> 1; // division by two
boolean leftPart = isSorted(arr, start, middle);
boolean rightPart = isSorted(arr, middle, end);
return leftPart && rightPart;
}
To use call,
isSorted(list, 0, list.size() - 1)
java algorithm array recursion divide-and-conquer
edited Nov 24 '18 at 22:24
Martin R
16.1k12364
asked Nov 24 '18 at 19:24
itsnotmyrealnameitsnotmyrealname
1625
$endgroup$
I've written a code that I try to use divide and conquer approach to determine if the given array is sorted. I wonder whether I apply the approach accurately.
public static boolean isSorted(List<Integer> arr, int start, int end) {
if (end - start == 1) // base case to compare two elements
return arr.get(end) > arr.get(start);
int middle = (end + start) >>> 1; // division by two
boolean leftPart = isSorted(arr, start, middle);
boolean rightPart = isSorted(arr, middle, end);
return leftPart && rightPart;
}
To use call,
isSorted(list, 0, list.size() - 1)
java algorithm array recursion divide-and-conquer
java algorithm array recursion divide-and-conquer
edited Nov 24 '18 at 22:24
Martin R
16.1k12364
asked Nov 24 '18 at 19:24
itsnotmyrealnameitsnotmyrealname
1625
edited Nov 24 '18 at 22:24
Martin R
16.1k12364
asked Nov 24 '18 at 19:24
itsnotmyrealnameitsnotmyrealname
1625
edited Nov 24 '18 at 22:24
Martin R
16.1k12364
edited Nov 24 '18 at 22:24
Martin R
16.1k12364
edited Nov 24 '18 at 22:24
Martin R
16.1k12364
16.1k12364
asked Nov 24 '18 at 19:24
itsnotmyrealnameitsnotmyrealname
1625
asked Nov 24 '18 at 19:24
itsnotmyrealnameitsnotmyrealname
1625
asked Nov 24 '18 at 19:24
itsnotmyrealnameitsnotmyrealname
1625
1625
3
$begingroup$
Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers.
$endgroup$
– Martin R
Nov 24 '18 at 22:24
$begingroup$
Test your code on3, 4, 1, 2.
$endgroup$
– vnp
Nov 25 '18 at 6:43
$begingroup$
@vnpisSorted(list, 0, 3)will callisSorted(arr, 1, 3)which will callisSorted(arr, 1, 2)which will returnfalse. That test case is fine.
$endgroup$
– AJNeufeld
Nov 25 '18 at 18:02
add a comment |
3
$begingroup$
Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers.
$endgroup$
– Martin R
Nov 24 '18 at 22:24
$begingroup$
Test your code on3, 4, 1, 2.
$endgroup$
– vnp
Nov 25 '18 at 6:43
$begingroup$
@vnpisSorted(list, 0, 3)will callisSorted(arr, 1, 3)which will callisSorted(arr, 1, 2)which will returnfalse. That test case is fine.
$endgroup$
– AJNeufeld
Nov 25 '18 at 18:02
3
3
$begingroup$
Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers.
$endgroup$
– Martin R
Nov 24 '18 at 22:24
$begingroup$
Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers.
$endgroup$
– Martin R
Nov 24 '18 at 22:24
$begingroup$
Test your code on
3, 4, 1, 2.$endgroup$
– vnp
Nov 25 '18 at 6:43
$begingroup$
Test your code on
3, 4, 1, 2.$endgroup$
– vnp
Nov 25 '18 at 6:43
$begingroup$
@vnp
isSorted(list, 0, 3) will call isSorted(arr, 1, 3) which will call isSorted(arr, 1, 2) which will return false. That test case is fine.$endgroup$
– AJNeufeld
Nov 25 '18 at 18:02
$begingroup$
@vnp
isSorted(list, 0, 3) will call isSorted(arr, 1, 3) which will call isSorted(arr, 1, 2) which will return false. That test case is fine.$endgroup$
– AJNeufeld
Nov 25 '18 at 18:02
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
It looks like your are doing it mostly right. You have problems with length zero and length 1 arrays, but you should be able to fix those pretty quick.
You may be doing more work than necessary. If an array is not sorted, you might find leftPart is false, but you unconditionally go on to determine the value of rightPart anyway, despite it not mattering. The simplest way to avoid that is to combine that recursive calls and the && operation. Ie:
return isSorted(arr, start, middle) && isSorted(arr, middle, end);
Lastly, if the array contains duplicates, can it still be considered sorted? You return false for [1, 2, 2, 3].
answered Nov 24 '18 at 20:09
AJNeufeldAJNeufeld
5,9751520
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
});
});
}, "mathjax-editing");
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "196"
};
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%2fcodereview.stackexchange.com%2fquestions%2f208343%2fchecking-whether-given-array-is-sorted-by-divide-and-conquer%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 looks like your are doing it mostly right. You have problems with length zero and length 1 arrays, but you should be able to fix those pretty quick.
You may be doing more work than necessary. If an array is not sorted, you might find leftPart is false, but you unconditionally go on to determine the value of rightPart anyway, despite it not mattering. The simplest way to avoid that is to combine that recursive calls and the && operation. Ie:
return isSorted(arr, start, middle) && isSorted(arr, middle, end);
Lastly, if the array contains duplicates, can it still be considered sorted? You return false for [1, 2, 2, 3].
answered Nov 24 '18 at 20:09
AJNeufeldAJNeufeld
5,9751520
$endgroup$
add a comment |
$begingroup$
It looks like your are doing it mostly right. You have problems with length zero and length 1 arrays, but you should be able to fix those pretty quick.
You may be doing more work than necessary. If an array is not sorted, you might find leftPart is false, but you unconditionally go on to determine the value of rightPart anyway, despite it not mattering. The simplest way to avoid that is to combine that recursive calls and the && operation. Ie:
return isSorted(arr, start, middle) && isSorted(arr, middle, end);
Lastly, if the array contains duplicates, can it still be considered sorted? You return false for [1, 2, 2, 3].
answered Nov 24 '18 at 20:09
AJNeufeldAJNeufeld
5,9751520
$endgroup$
add a comment |
$begingroup$
It looks like your are doing it mostly right. You have problems with length zero and length 1 arrays, but you should be able to fix those pretty quick.
You may be doing more work than necessary. If an array is not sorted, you might find leftPart is false, but you unconditionally go on to determine the value of rightPart anyway, despite it not mattering. The simplest way to avoid that is to combine that recursive calls and the && operation. Ie:
return isSorted(arr, start, middle) && isSorted(arr, middle, end);
Lastly, if the array contains duplicates, can it still be considered sorted? You return false for [1, 2, 2, 3].
answered Nov 24 '18 at 20:09
AJNeufeldAJNeufeld
5,9751520
$endgroup$
It looks like your are doing it mostly right. You have problems with length zero and length 1 arrays, but you should be able to fix those pretty quick.
You may be doing more work than necessary. If an array is not sorted, you might find leftPart is false, but you unconditionally go on to determine the value of rightPart anyway, despite it not mattering. The simplest way to avoid that is to combine that recursive calls and the && operation. Ie:
return isSorted(arr, start, middle) && isSorted(arr, middle, end);
Lastly, if the array contains duplicates, can it still be considered sorted? You return false for [1, 2, 2, 3].
answered Nov 24 '18 at 20:09
AJNeufeldAJNeufeld
5,9751520
answered Nov 24 '18 at 20:09
AJNeufeldAJNeufeld
5,9751520
answered Nov 24 '18 at 20:09
AJNeufeldAJNeufeld
5,9751520
answered Nov 24 '18 at 20:09
AJNeufeldAJNeufeld
5,9751520
5,9751520
add a comment |
add a comment |
Thanks for contributing an answer to Code Review 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%2fcodereview.stackexchange.com%2fquestions%2f208343%2fchecking-whether-given-array-is-sorted-by-divide-and-conquer%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
3
$begingroup$
Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers.
$endgroup$
– Martin R
Nov 24 '18 at 22:24
$begingroup$
Test your code on
3, 4, 1, 2.$endgroup$
– vnp
Nov 25 '18 at 6:43
$begingroup$
@vnp
isSorted(list, 0, 3)will callisSorted(arr, 1, 3)which will callisSorted(arr, 1, 2)which will returnfalse. That test case is fine.$endgroup$
– AJNeufeld
Nov 25 '18 at 18:02