Checking whether given array is sorted by divide-and-conquer











up vote
2
down vote

favorite












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)









share|improve this question




















  • 3




    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.
    – Martin R
    4 hours ago















up vote
2
down vote

favorite












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)









share|improve this question




















  • 3




    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.
    – Martin R
    4 hours ago













up vote
2
down vote

favorite









up vote
2
down vote

favorite











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)









share|improve this question















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






share|improve this question















share|improve this question













share|improve this question




share|improve this question








edited 4 hours ago









Martin R

15.3k12264




15.3k12264










asked 7 hours ago









itsnotmyrealname

1475




1475








  • 3




    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.
    – Martin R
    4 hours ago














  • 3




    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.
    – Martin R
    4 hours ago








3




3




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.
– Martin R
4 hours ago




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.
– Martin R
4 hours ago










1 Answer
1






active

oldest

votes

















up vote
2
down vote













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].






share|improve this answer





















  • Holy Moley! You've thrown me a curve sir. I've edited the code according to your proposals. Would you mind glancing at again?
    – itsnotmyrealname
    5 hours ago













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',
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
});


}
});














 

draft saved


draft discarded


















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








up vote
2
down vote













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].






share|improve this answer





















  • Holy Moley! You've thrown me a curve sir. I've edited the code according to your proposals. Would you mind glancing at again?
    – itsnotmyrealname
    5 hours ago

















up vote
2
down vote













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].






share|improve this answer





















  • Holy Moley! You've thrown me a curve sir. I've edited the code according to your proposals. Would you mind glancing at again?
    – itsnotmyrealname
    5 hours ago















up vote
2
down vote










up vote
2
down vote









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].






share|improve this answer












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].







share|improve this answer












share|improve this answer



share|improve this answer










answered 6 hours ago









AJNeufeld

3,700317




3,700317












  • Holy Moley! You've thrown me a curve sir. I've edited the code according to your proposals. Would you mind glancing at again?
    – itsnotmyrealname
    5 hours ago




















  • Holy Moley! You've thrown me a curve sir. I've edited the code according to your proposals. Would you mind glancing at again?
    – itsnotmyrealname
    5 hours ago


















Holy Moley! You've thrown me a curve sir. I've edited the code according to your proposals. Would you mind glancing at again?
– itsnotmyrealname
5 hours ago






Holy Moley! You've thrown me a curve sir. I've edited the code according to your proposals. Would you mind glancing at again?
– itsnotmyrealname
5 hours ago




















 

draft saved


draft discarded



















































 


draft saved


draft discarded














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





















































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







Popular posts from this blog

A CLEAN and SIMPLE way to add appendices to Table of Contents and bookmarks

Calculate evaluation metrics using cross_val_predict sklearn

Insert data from modal to MySQL (multiple modal on website)