Results 1 to 14 of 14
  1. #1
    Yakg is offline Member
    Join Date
    Dec 2010
    Posts
    59
    Rep Power
    0

    Default mergesort recursion

    hi, I am trying to combine 2 arrays into a sorted one through recursion (no loops alowed)

    This is what I've written so far, it is not complete.
    Has anyone did it before as I'm having trouble finding it online.

    Thanks.

    The code:

    Java Code:
    public class M4{
        public static int [] merge (int [] ar1,int [] ar2){
            int l1 = ar1.length, l2 = ar2.length, l3 = l1+l2;
            int result [] = new int [l3];
            return merge(ar1,ar2,result,l1,l2,l3);
        }
        
        public static int [] merge (int [] ar1, int [] ar2, int [] result, int l1, int l2, int l3){
            if (l3 == 0){
                if  (ar1[0] <= ar2[0]){
                    if(l2>-1)
                    l2=l2-1;  
                    else  
                    result [0] =ar1[0];
                    return result;
                 }
            else{
                 if(l1>-1)
                  l1=l1-1;
                  else
                    result [0] = ar2[0];
                    return result;
                }}
           
            if (l3>l2 || l3>l1)
           result =  merge (ar1,ar2,result,l1,l2,l3-1);
           
           result = merge (ar1,ar2,result,l1-1,l2-1,l3-1);  //recursive calls
           
           
            if  (ar1[l1] <= ar2[l2]){
              if(l2>0)
              l2=l2-1;  
              else  
              result [l3] = ar1 [l1];
              return result;
            }
            else{
                 if(l1>0)
                  l1=l1-1;
                  else
                  result [l3] = ar2 [l2];
                    return result;
                }
            }
    
            public static void main (String args[]){
                int ar1[] = {2,4,6};
                int ar2[] = {1,2,2};
                merge(ar1,ar2);
            }
        }

  2. #2
    Petr's Avatar
    Petr is offline Senior Member
    Join Date
    Jan 2011
    Location
    Russia
    Posts
    618
    Rep Power
    4

    Default

    Do you have a special task? Do you need make a sort algorithm?
    because Java has library for this aim.
    Skype: petrarsentev
    http://TrackStudio.com

  3. #3
    doWhile is offline Moderator
    Join Date
    Jul 2010
    Location
    California
    Posts
    1,642
    Rep Power
    7

    Default

    Has anyone did it before as I'm having trouble finding it online.
    Did what? Trouble finding what? What exactly is the question/problem?

  4. #4
    Yakg is offline Member
    Join Date
    Dec 2010
    Posts
    59
    Rep Power
    0

    Default basically it's

    sorting two array into one.
    For example if given: int a [] = {2,4,6}, int b [] = {1,2,2}.
    so the result array should be: {1,2,2,2,4,6}.

    Recursively without loops.


    Hope it's understood this time thanks.

  5. #5
    Yakg is offline Member
    Join Date
    Dec 2010
    Posts
    59
    Rep Power
    0

    Default Forgot to mention that

    no other ways are allowed and nor the use of libraries.

  6. #6
    doWhile is offline Moderator
    Join Date
    Jul 2010
    Location
    California
    Posts
    1,642
    Rep Power
    7

    Default

    sorting two array into one.
    For example if given: int a [] = {2,4,6}, int b [] = {1,2,2}.
    so the result array should be: {1,2,2,2,4,6}.

    Recursively without loops.


    Hope it's understood this time thanks.
    And if you run the above (assuming it can compile because you've given us little information regarding its behavior) how does it behave?

  7. #7
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,337
    Blog Entries
    7
    Rep Power
    20

    Default

    Quote Originally Posted by Yakg View Post
    no other ways are allowed and nor the use of libraries.
    First define a couple of indexes: i1, i2 and i3; a[i1] is the number to read from array a, b[i2] is the number to read from array b and result[i3] is the number to write to the result array. A few conditions need to be tested:

    1) i1 == a.length && i2 == b.length: the merging is ready, return result
    2) else if i1 == a.length: add b[i2] to result and call recursively with i2= i2+1
    3) else if i2 == b.length add a[i1] to result and call recursively with i1= i1+1
    4) else find the smallest of a[i1] and b[i2], add it to result and call recursively with i1= i1+1 or i2= i2+2

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  8. #8
    Yakg is offline Member
    Join Date
    Dec 2010
    Posts
    59
    Rep Power
    0

    Default My idea was

    to compare between the two arrays
    so if the left array is <= the right,
    than copy the number to the result array and increase
    the left index and the result index by 1.
    And do the opposite if left is >.

    I'm trying to do this comparison, that each of the arrays position will progress only when their correspond condition is true.
    What actually happens is that at the end of the recursive call they all progress together (the positions).

    I think I need to control their progression individually somehow.
    Does anyone know how to do this separately?

  9. #9
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,337
    Blog Entries
    7
    Rep Power
    20

    Default

    Quote Originally Posted by Yakg View Post
    I think I need to control their progression individually somehow.
    Does anyone know how to do this separately?
    Yup, I do, see my reply #8.

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  10. #10
    Yakg is offline Member
    Join Date
    Dec 2010
    Posts
    59
    Rep Power
    0

    Smile I saw it only after...Joshua

    The big question is how to write it in a compiled friendly way....
    I'll try to find an example as I don't want to bother to much. I'll try breaking my head working on this in the meantime.

    Many thanks.

  11. #11
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,337
    Blog Entries
    7
    Rep Power
    20

    Default

    Quote Originally Posted by Yakg View Post
    The big question is how to write it in a compiled friendly way....
    I'll try to find an example as I don't want to bother to much. I'll try breaking my head working on this in the meantime.

    Many thanks.
    You're welcome; I do the skeleton of the code for you:

    Java Code:
    private int[] merge(int[] a, int[] b, int[] result, int i1, int i2, int i3) {
       if (i1 == a.length && i2 == b.length) // step 1 in reply #8
          return result;
       else if (i1 == a.length) { // step 2 in reply #8
          result[i3++]= b[i2++];
          return merge(a, b, result, i1, i2, i3);
       }
       else // you do the rest ...
    }
    kind regards,

    Jos
    Last edited by JosAH; 02-20-2011 at 05:51 PM.
    cenosillicaphobia: the fear for an empty beer glass

  12. #12
    Yakg is offline Member
    Join Date
    Dec 2010
    Posts
    59
    Rep Power
    0

    Default Hi, everyone I'm back again

    I'll be glad if someone post the recursion mergesort code, as I think I have an idea but not enough time to practice for tomorrow's test. That will be one last big favour I need and hopefully will all go well.

    Thanks.

  13. #13
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,337
    Blog Entries
    7
    Rep Power
    20

    Default

    Quote Originally Posted by Yakg View Post
    I'll be glad if someone post the recursion mergesort code, as I think I have an idea but not enough time to practice for tomorrow's test. That will be one last big favour I need and hopefully will all go well.

    Thanks.
    But I gave it all away in my last reply; all you have to do is complete the last two if-conditions in the same manner as I did in the first two if-conditions. Also reread my previous reply explaining what the code should do and how it should do it. I am not going to complete all your homework.

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  14. #14
    Yakg is offline Member
    Join Date
    Dec 2010
    Posts
    59
    Rep Power
    0

    Default Did it!!

    finally I understand the principle I was completely taking this the wrong way.
    Came back to read your previous reply (Jos) and got it.

    This forum's members have helped me allot through my studies.
    Keep up this tremendous work. :)

Similar Threads

  1. help with mergesort
    By desconocido in forum New To Java
    Replies: 5
    Last Post: 09-15-2010, 03:56 AM
  2. recursion and tail-recursion differences
    By OptimusPrime in forum New To Java
    Replies: 2
    Last Post: 12-28-2009, 06:26 PM
  3. mergeSort
    By Blue_beaver in forum New To Java
    Replies: 2
    Last Post: 10-11-2009, 10:55 PM
  4. Recursion
    By jachandru in forum New To Java
    Replies: 1
    Last Post: 01-24-2009, 12:52 PM
  5. Recursion
    By Mika in forum New To Java
    Replies: 5
    Last Post: 01-04-2009, 01:13 AM

Posting Permissions

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