Results 1 to 9 of 9
  1. #1
    matrixcool is offline Member
    Join Date
    Dec 2010
    Posts
    21
    Rep Power
    0

    Question 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 !!


    Java 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 :


    Java 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 :(

  2. #2
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,783
    Blog Entries
    7
    Rep Power
    21

    Default

    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
    cenosillicaphobia: the fear for an empty beer glass

  3. #3
    matrixcool is offline Member
    Join Date
    Dec 2010
    Posts
    21
    Rep Power
    0

    Default

    How can I do it recursively for the next elements without copying the array into array of length n ?

  4. #4
    sunde887's Avatar
    sunde887 is offline Moderator
    Join Date
    Jan 2011
    Location
    Richmond, Virginia
    Posts
    3,069
    Blog Entries
    3
    Rep Power
    8

    Default

    add an instance variable:
    Java Code:
    public boolean isSorted(int[] a, int n)
    on each recursive pass add 1 to n.
    Java Code:
    if(a[n] > a[n + 1])
    {
    return false;
    }
    if it makes it past this clause, the next clause should be:
    Java Code:
    return isSorted(a, n + 1)

  5. #5
    matrixcool is offline Member
    Join Date
    Dec 2010
    Posts
    21
    Rep Power
    0

    Default

    I need to check if the first n integers are in ascending order , but you said iSorted(a,n+1) !!

    How is that ?

  6. #6
    matrixcool is offline Member
    Join Date
    Dec 2010
    Posts
    21
    Rep Power
    0

    Default

    it worked ! but I don't know how !!
    I tried many arrays and it's absolutely working 100% !!
    if (a[n] > a[n-1] ){
    return false & isSorted(a,n-1);
    }
    else{
    return true;
    }
    could any one please explain how it worked !!

  7. #7
    sunde887's Avatar
    sunde887 is offline Moderator
    Join Date
    Jan 2011
    Location
    Richmond, Virginia
    Posts
    3,069
    Blog Entries
    3
    Rep Power
    8

    Default

    sorry, adding a 3rd variable would probable be necessary, which would basically allow you to choose a range.

    Java 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:
    Java 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
    Java Code:
    isSorted(int[] a, n)
    and move down and if n == 0, return true.
    Java Code:
    if(a[i] < a[i+1])
    {
    return false;
    }

  8. #8
    gcalvin is offline Senior Member
    Join Date
    Mar 2010
    Posts
    952
    Rep Power
    5

    Default

    Quote Originally Posted by matrixcool View Post
    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 !!


    Java 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-

  9. #9
    matrixcool is offline Member
    Join Date
    Dec 2010
    Posts
    21
    Rep Power
    0

Similar Threads

  1. Array out of bound- Recursive Method
    By hpayandah in forum New To Java
    Replies: 2
    Last Post: 11-12-2010, 09:02 PM
  2. Recursive method using int array, help needed
    By chupalo17 in forum New To Java
    Replies: 4
    Last Post: 09-08-2009, 12:15 AM
  3. Replies: 8
    Last Post: 04-22-2008, 04:21 AM
  4. Replies: 1
    Last Post: 02-16-2008, 10:10 PM
  5. Replies: 2
    Last Post: 02-16-2008, 09:52 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •