Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 6 of 6

Thread: Converting merge method in c to java

  1. #1
    Junior Member
    Join Date
    Sep 2013
    Posts
    16
    Thanks
    1
    Thanked 0 Times in 0 Posts

    Default Converting merge method in c to java

    Now, I do know several versions of merge sort in java that actually work, but for my own sake, I'd like to know why my translation of the c code below is wrong. To me it seems like the logic should be the same. Nevertheless, I have verified that the c code works and that the java code does not.


    Here is the original code in c
    /* Function to merge the two haves arr[l..m] and arr[m+1..r] of array arr[] */
    void merge(int arr[], int l, int m, int r)
    {
        int i, j, k;
        int n1 = m - l + 1;
        int n2 =  r - m;
     
        /* create temp arrays */
        int *L = (int *)malloc(sizeof(int)*n1);
        int *R = (int *)malloc(sizeof(int)*n2);
     
        /* Copy data to temp arrays L[] and R[] */
        for(i = 0; i < n1; i++)
            L[i] = arr[l + i];
        for(j = 0; j <= n2; j++)
            R[j] = arr[m + 1+ j];
     
        /* Merge the temp arrays back into arr[l..r]*/
        i = 0;
        j = 0;
        k = l;
        while (i < n1 && j < n2)
        {
            if (L[i] <= R[j])
            {
                arr[k] = L[i];
                i++;
            }
            else
            {
                arr[k] = R[j];
                j++;
            }
            k++;
        }
     
        /* Copy the remaining elements of L[], if there are any */
        while (i < n1)
        {
            arr[k] = L[i];
            i++;
            k++;
        }
     
        /* Copy the remaining elements of R[], if there are any */
        while (j < n2)
        {
            arr[k] = R[j];
            j++;
            k++;
        }
    }

    Here is my translation into java
    void merge(int arr[], int l, int m, int r)
    	{
    	    int i, j, k;
    	    int n1 = m - l + 1;
    	    int n2 =  r - m;
     
    	    /* create temp arrays */
    	    int []L = new int [n1];
    	    int []R = new int [n2];
     
    	    /* Copy data to temp arrays L[] and R[] */
    	    for(i = 0; i < n1; i++)
    	        L[i] = arr[l + i];
    	    for(j = 0; j <= n2; j++)
    	        R[j] = arr[m + 1+ j];
     
    	    /* Merge the temp arrays back into arr[l..r]*/
    	    i = 0;
    	    j = 0;
    	    k = l;
    	    while (i < n1 && j < n2)
    	    {
    	        if (L[i] <= R[j])
    	        {
    	            arr[k] = L[i];
    	            i++;
    	        }
    	        else
    	        {
    	            arr[k] = R[j];
    	            j++;
    	        }
    	        k++;
    	    }
     
    	    /* Copy the remaining elements of L[], if there are any */
    	    while (i < n1)
    	    {
    	        arr[k] = L[i];
    	        i++;
    	        k++;
    	    }
     
    	    /* Copy the remaining elements of R[], if there are any */
    	    while (j < n2)
    	    {
    	        arr[k] = R[j];
    	        j++;
    	        k++;
    	    }
    	}






    The error is always at the line R[j] = arr[m + 1+ j];
    I thought it might be an off-by one error, so I tried putting in +1 or -1 in a few places, but still couldn't get it to work. Maybe someone here will have more success finding it.
    I've heard that c doesn't translate all that well into java (I have virtually no experience with c), but I can't see how the operations used in the two above are all that different.


  2. #2
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    25,042
    Thanks
    63
    Thanked 2,708 Times in 2,658 Posts

    Default Re: Converting merge method in c to java

    The error is always at the line R[j] = arr[m + 1+ j];
    Can you explain what the "error" is?

    merge the two haves arr[l..m] and arr[m+1..r] of array arr[]
    Can you explain what the code is supposed to do? Perhaps by giving an example of the input and the output (or the before and after)
    If you don't understand my answer, don't ignore it, ask a question.

  3. #3
    Junior Member
    Join Date
    Sep 2013
    Posts
    16
    Thanks
    1
    Thanked 0 Times in 0 Posts

    Default Re: Converting merge method in c to java

    The error is an array index out of bound exception. I can't get much more detail than that, particularly as I don't know how to how to iterate through the eclipse debugger on my laptop (F6 doesn't work).

    The merge method is supposed to merge an array, when each half of that array is sorted, into a fully sorted array.
    It is supposed to take this input like this: (int [] halfSortedArray, int firstIndexInArray, int midPointOfArray,int lastIndexInarray)

    An example of the algorithm in operation would be this;
    int [] array = {3,4,5,6,1,2,3,4}
    merge(array,0,3,7)
    output: 1,2,3,3,4,4,5,6

    It is usually used in conjunction with a mergeSort algorithm. Sorry I wasn't very clear about explaining it, but I'll bet you are already familiar with it. Nevertheless, for clarity, here is a java example that does the same thing that does actually work:

    public static void merge(int[] a, int l, int m, int r) {
    		int[] numbers = a;
    		int number = a.length;
    		int[] helper = new int[number];
     
    		int p = l;
    		int u = l;
    		int v = m + 1;
     
    		// Copy both parts into the helper array
    		for (int i = l; i <= r; i++) {
    			helper[i] = numbers[i];
    		}
     
    		// create empty array
    		// int [] result = emptyArray(r-l+1);
     
    		// Copy the smallest values from either the left or the right side back
    		// to the original array
    		while (p <= m && v <= r) {
    			if (helper[p] <= helper[v]) {
    				numbers[u] = helper[p];
    				p++;
    			} else {
    				numbers[u] = helper[v];
    				v++;
    			}
    			u++;
    		}
    		// Copy the rest of the left side of the array into the target array
    		while (p <= m) {
    			numbers[u] = helper[p];
    			u++;
    			p++;
    		}
     
    	}// end merge

  4. #4
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    25,042
    Thanks
    63
    Thanked 2,708 Times in 2,658 Posts

    Default Re: Converting merge method in c to java

    What is the value of the index that is out of bounds? It is usually shown in the error message.
    What are the values of m and j when the error happens?

    here is a java example that does the same thing that does actually work:
    If you have a working program, what needs to be done now?
    If you don't understand my answer, don't ignore it, ask a question.

  5. #5
    Junior Member
    Join Date
    Sep 2013
    Posts
    16
    Thanks
    1
    Thanked 0 Times in 0 Posts

    Default Re: Converting merge method in c to java

    It's not so much about getting the code to work as it is about cementing my understanding of it. The C code happens to be closer to the pseudocode in Introduction to Algorithms and other places. I wanted to convert the same logic to java to aid my understanding. Nothing more. I have a good few examples working, but they all use different logic to do it. It's funny since the actual mergeSort method is nearly always the same, but the merge method is done in so many different ways. I also want to get used to translating pseudocode. I keeping getting caught by common things like pseudocode indexing from 1 to n where a computer indexes from 0 to n-1, particularly assigning int values of 1 where it is 0 in actual code, as is the case when you compare the Introduction to Algorithms Code with the C implementation.

    I've just had a proper run through the debugger. m remains 3 throughout, and, given an array of length 8, the error occurs when j =4. So, that means that given an array numbered from 0-7, it tries to assign a value from arr[8], which it can't do.

    Going over this made me notice the asymmetry between the i and j for loops; one uses < and one uses <=. I changed that j for loop to <, and now I have a version that seems to work.

    static void merge(int arr[], int l, int m, int r)
    	{
    	    int i, j, k;
    	    int n1 = m - l;
    	    int n2 =  r - m;
     
    	    /* create temp arrays */
    	    int []L = new int [n1];
    	    int []R = new int [n2];
     
    	    /* Copy data to temp arrays L[] and R[] */
    	    for(i = 0; i < n1; i++)
    	        L[i] = arr[l + i];
    	    for(j = 0; j < n2; j++)
    	        R[j] = arr[m + 1+ j];
     
    	    /* Merge the temp arrays back into arr[l..r]*/
    	    i = 0;
    	    j = 0;
    	    k = l;
    	    while (i < n1 && j < n2)
    	    {
    	        if (L[i] <= R[j])
    	        {
    	            arr[k] = L[i];
    	            i++;
    	        }
    	        else
    	        {
    	            arr[k] = R[j];
    	            j++;
    	        }
    	        k++;
    	    }
     
    	    /* Copy the remaining elements of L[], if there are any */
    	    while (i < n1)
    	    {
    	        arr[k] = L[i];
    	        i++;
    	        k++;
    	    }
     
    	    /* Copy the remaining elements of R[], if there are any */
    	    while (j < n2)
    	    {
    	        arr[k] = R[j];
    	        j++;
    	        k++;
    	    }
    	}

    I still have to test it thoroughly, but looks like it was an off by one error. Why am I not surprised? It's always an off by one error!

  6. #6
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    25,042
    Thanks
    63
    Thanked 2,708 Times in 2,658 Posts

    Default Re: Converting merge method in c to java

    Glad you got it working.
    If you don't understand my answer, don't ignore it, ask a question.

Similar Threads

  1. Merge 20+ xml files with 7000+nodes into one using java
    By mija in forum What's Wrong With My Code?
    Replies: 2
    Last Post: July 3rd, 2013, 02:33 AM
  2. Help ! merge this code into 1 main method . ASAP :( tnx
    By anitsirc in forum Object Oriented Programming
    Replies: 2
    Last Post: November 23rd, 2011, 11:53 AM
  3. how to merge java objects with effective dates
    By java4ulok in forum What's Wrong With My Code?
    Replies: 4
    Last Post: June 10th, 2011, 01:24 PM
  4. Replies: 1
    Last Post: February 10th, 2011, 08:57 AM
  5. Converting a method from ArrayList so it is capable with an Array
    By BlueJ1 in forum Collections and Generics
    Replies: 2
    Last Post: July 8th, 2009, 05:22 PM