3
\$\begingroup\$

I'm trying to implement isSorted method checking whether given array is sorted recursively. I've written two types, one is similar to merge sort logic, the another is like loop. Can they be made more efficient? Is there any thing I overlooked?

class SortedRecursive {
    public static void main(String[] args) {
        List<Integer> test = new ArrayList<>(Arrays.asList(9, 9, 9));
        List<Integer> test2 = new ArrayList<>(Arrays.asList(9, 10, 11));
        List<Integer> test3 = new ArrayList<>(Arrays.asList(5, 5, 3, 7));
        List<Integer> test4 = new ArrayList<>(Arrays.asList(1,2,2,3,3,4));


        System.out.println("test(nlogn) -> " + isSorted(test));
        System.out.println("test(n) -> " + isSortedAnotherVersion(test, 0));
        System.out.println("test2(nlogn) -> " + isSorted(test2));
        System.out.println("test2(n) -> " + isSortedAnotherVersion(test2, 0));
        System.out.println("input(nlogn) -> " + isSorted(test3));
        System.out.println("input(n) -> " + isSortedAnotherVersion(test3, 0));
        System.out.println("output(nlogn) -> " + isSorted(test4));
        System.out.println("output(n) -> " + isSortedAnotherVersion(test4, 0));
    }

    public static boolean isSorted(List<Integer> arr) {
        if (arr == null || arr.size() == 0) {
            return false;
        }

        if (arr.size() == 1) {
            return true;
        }


        int middleIndex = arr.size() / 2 ;
        List<Integer> left = new ArrayList<>();
        List<Integer> right = new ArrayList<>();

        for (int i = 0; i < middleIndex; i++) {
            left.add(arr.get(i));
        }

        for (int i = middleIndex; i < arr.size(); i++) {
            right.add(arr.get(i));
        }

        //System.out.println("left -> " + left + " right -> " + right);

        boolean result = left.get(middleIndex - 1) <= right.get(0);

        return isSorted(left) && result && isSorted(right);

    }

    public static boolean isSortedAnotherVersion(List<Integer> arr, int index) {
        if (arr.size() == 1 || index == arr.size() - 1)
            return true;
        if (arr.get(index) > arr.get(index + 1)) return false;
        return isSortedAnotherVersion(arr, index + 1);
    }

}
\$\endgroup\$
  • \$\begingroup\$ added the another version mentioned @MikeBorkland \$\endgroup\$ – itsnotmyrealname May 18 '18 at 1:27
  • \$\begingroup\$ Looks good! It should be quite a bit faster for very large n. \$\endgroup\$ – Mike Borkland May 18 '18 at 1:50
  • 1
    \$\begingroup\$ I wonder why you want a recursive method at all, if the same can be achieved with a simple loop. \$\endgroup\$ – Martin R May 18 '18 at 5:55
  • \$\begingroup\$ @MartinR I think this is OK as an exercise to practice recursion and the principles of divide and conquer. But you are definitely right: in real life this should not be done recursively. \$\endgroup\$ – mtj May 18 '18 at 6:13
  • 1
    \$\begingroup\$ @MikeBorkland Never mind, I think I see what you mean now. Since the first solution copies every list element on a split instead of calling List.sublist, which just creates a view of the original list, the split is not a constant-time operation but proportional to the size of the list to be split. So every element in the original has to be copied \$\log(n)\$ times, making the total number of element copies \$n\cdot\log(n)\$. \$\endgroup\$ – Stingy May 18 '18 at 9:25
5
\$\begingroup\$

Version 1:

Basically OK, but the copying of elements to another list is unnecessary. Have a look at List.sublist on how to create lists from a given index range.

Additionally, you should change the return statement to result && isSorted(left) && isSorted(right) so that the recursion does not take place if result is already false. (Look up short-circuiting in logical statements.)

Version 2:

NO. It is much better not to copy the elements and use indexes into the unmodified structure, but here you recurse for every element in the list, i.e. the recursion depth equals the list size. This is a total no-go, as it will definitely blow your stack if we are talking about serious data sizes.

Nevertheless, explore the option of using indexes (maybe a start-index AND an end-index) into the given structure some more and combine it to a divide and conquer-approach as in your first solution.

Happy coding!

\$\endgroup\$
3
\$\begingroup\$

An array a is sorted if a[i] <= a[i+1] for 0 <= i < a.size() - 1. For an empty array that is a “vacuous truth” – there are no indices satisfying the condition.

Therefore your functions should return true for an empty array.

Your first function returns false for an empty array, and the second one crashes with an IndexOutOfBoundsException.

More remarks:

  • Your function takes a List as parameter, i.e. it can not only be called with an ArrayList but also with other lists (like LinkedList) for which each get(i) has to traverse the list from the head up to position i.

    I'd suggest to either take an array parameter, or to modify it to iterate over the elements instead.

  • I do not see an advantage of any recursion. The same task can be achieved with a simple loop.

  • You could make the function generic, so that it can not only be used with integer arrays/lists, but also with other (comparable) types.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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