# Recursive method that checks if the first n elements of an array is sorted?

• 01-15-2011, 11:51 AM
matrixcool
Recursive method that checks if the first n elements of an array is sorted?
Hi guys,

I'm trying to write a recursive method that checks if the first elements of an array of integers are sorted in ascending order but it didn't work for me !!

Code:

`public static Boolean isSorted(int [] a, int n){}`

I tried to copy elements from array a with length n into another array b then , compare every two elements starting from b[0] and b[1] such that :

Code:

```if (b[0] < b[1] ) // that means those elements are in ascending order       {         return true;       }```

but I couldn't complete it ,, could anyone please help me to write the rest of the code :(
• 01-15-2011, 12:21 PM
JosAH
There is no need to copy elements over to another array. Just assume that elements 0 ... i-1 are in sorted order and assume the length of the array is n. If i < n-1 and elements i-1 and i are in sorted order call your method recursively for the next elements. Otherwise if i == n-1 the entire array is sorted, otherwise the array isn't sorted.

kind regards,

Jos
• 01-15-2011, 08:58 PM
matrixcool
How can I do it recursively for the next elements without copying the array into array of length n ?
• 01-15-2011, 09:47 PM
sunde887
add an instance variable:
Code:

`public boolean isSorted(int[] a, int n)`
on each recursive pass add 1 to n.
Code:

```if(a[n] > a[n + 1]) { return false; }```
if it makes it past this clause, the next clause should be:
Code:

`return isSorted(a, n + 1)`
• 01-15-2011, 09:53 PM
matrixcool
I need to check if the first n integers are in ascending order , but you said iSorted(a,n+1) !!

How is that ?
• 01-15-2011, 10:00 PM
matrixcool
it worked ! but I don't know how !!
I tried many arrays and it's absolutely working 100% !!
Quote:

if (a[n] > a[n-1] ){
return false & isSorted(a,n-1);
}
else{
return true;
}
could any one please explain how it worked !!
• 01-15-2011, 10:02 PM
sunde887
sorry, adding a 3rd variable would probable be necessary, which would basically allow you to choose a range.

Code:

`isSorted(int[] a, int i, int n)`
if you have a 30 item array and you wanna check the first 5 items, you would call the method as:
Code:

`isSorted(a, 0, 5)`
each recursive pass would add 1 to i, and the function will return true if i == n.

alternately you could just take
Code:

`isSorted(int[] a, n)`
and move down and if n == 0, return true.
Code:

```if(a[i] < a[i+1]) { return false; }```
• 01-15-2011, 10:14 PM
gcalvin
Quote:

Originally Posted by matrixcool
Hi guys,

I'm trying to write a recursive method that checks if the first elements of an array of integers are sorted in ascending order but it didn't work for me !!

Code:

`public static [COLOR="Red"]Boolean[/COLOR] isSorted(int [] a, int n){}`

Are you sure you want Boolean and not boolean there? Are you going to be storing these results in a List or something?

Like Jos said, you don't need to do any array copying, and you don't need an instance variable as sunde suggested either.

Base case: n <= 1 : return true.
Other cases: if a[n-2] is greater than a[n-1] return false, otherwise return isSorted(a, n-1).

In other words, if n is 10, I want to see if a[9] (the 10th element) and a[8] (the 9th element) are in proper order. If they're not, I should return false. If they are, then I want to call a method that checks if the first 9 elements are in order, and that method happens to be another instance of myself, with n reduced by one.

-Gary-
• 01-15-2011, 10:39 PM
matrixcool
Thanks a lot guys :)