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 5 of 5

Thread: Issue when returning an array

  1. #1
    Junior Member
    Join Date
    Jan 2012
    Posts
    2
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Question Issue when returning an array

    I'm writing my own mergeSort method from scratch for a CS course, but somewhere a long the way it seems to lose it's way...

    public static int[] mergeSort(int[] array) {
     
    		if (array.length <= 1){
    			return array;
    		}
     
    		int[] left;
    		int[] right;
     
    		if (array.length%2 == 1){
    			left = new int[array.length/2+1];
    		}else {
    			left = new int[array.length/2];
    		}
    		right = new int[array.length/2];
     
    		System.arraycopy(array, 0, left, 0, left.length);
    		System.arraycopy(array, left.length, right, 0, right.length);
     
    		mergeSort(left);
    		System.out.println("A left value returned with result: " + printArray(left));
    		mergeSort(right);
    		System.out.println("A right value returned with result: " + printArray(right));
     
     
    		//printArray(merge(left, right));
    		return merge(left, right);
    	}
     
    	public static int[] merge(int[] left, int[] right) {
     
    		int[] result = new int[left.length+right.length];
     
    		int count = 0;
     
    		while (left.length > 0 || right.length >0) {
    			if (left.length > 0 && right.length > 0) {
    				if (left[0] <= right[0]){
    					System.out.println("Left most of " + printArray(left) + " is less than left most of " +printArray(right));
    					result[count] = left[0];
    					left = helperFunction(left);
    				}
    				else {
    					System.out.println("Left most of " + printArray(right) + " is less than left most of " +printArray(left));
    					result[count] = right[0];
    					right = helperFunction(right);
    					}
    				}
    			else if (left.length > 0) {
    				System.out.println("Left most of " + printArray(left) + " is the next to add.");
    				result[count] = left[0];
    				left = helperFunction(left);
    			}
    			else if (right.length > 0) {
    				System.out.println("Left most of " + printArray(right) + " is the next to add.");
    				result[count] = right[0];
    				right = helperFunction(right);
    			}
    			count++;
    		}
    		System.out.println("The result is: "+printArray(result));
    		return result;
    	}
     
    	public static int[] helperFunction(int[] array) {
    		int[] helperArray;
    		helperArray = new int[array.length-1];
    		System.arraycopy(array, 1, helperArray, 0, array.length-1);
    		return helperArray;
    	}
     
    	public static String printArray(int[] array) {
    		String result = "[";
    		for(int i=0;i<array.length;i++){
    			result += (array[i]);
    			if (i!=array.length-1){
    				result += ", ";
    			}
    		}
    		result += "]";
     
    		return result;
    	}

    Those are the methods I'm using. helperMethod just removes the first element of an array, the printArray method is there for testing purposes, along with the extensive amount of line printing.

    When I call mergeSort on the array {3, 2, 1} the out put is:

    [3, 2, 1]
    A left value returned with result: [3]
    A right value returned with result: [2]
    Left most of [2] is less than left most of [3]
    Left most of [3] is the next to add.
    The result is: [2, 3]
    A left value returned with result: [3, 2]

    A right value returned with result: [1]
    Left most of [1] is less than left most of [3, 2]
    Left most of [3, 2] is the next to add.
    Left most of [2] is the next to add.
    The result is: [1, 3, 2]
    If you take a look at the lines in red, I call printArray on the "result" right before I return it and it's fine and sorted. Then after it's been returned to mergeSort, I have a println that should in theory be printing the same array, but it's been flipped.

    What gives?

    If anyone can explain what's going on I would greatly appreciate it.
    Last edited by Broxxar; January 21st, 2012 at 08:57 PM.


  2. #2
    Super Moderator pbrockway2's Avatar
    Join Date
    Jan 2012
    Posts
    987
    Thanks
    6
    Thanked 206 Times in 182 Posts

    Default Re: Issue when returning an array

    mergeSort(left);
    System.out.println("A left value returned with result: " + printArray(left));
    Your println() might be a bit confusing here. It is true that mergeSort(left) does return *something* but that's not what you print: you print left. Only under rather special conditions does mergeSort() return the same array it was passed. To see the difference try:

    int[] returnedArr = mergeSort(left);
    System.out.println("A left value returned with result: " + printArray(returnedArr));
    System.out.println("While left, itself, contains: " + printArray(left));

    You need to be clear in your own mind about the distinction between left and the array returned by mergeSort(left). And which you intend sending on to merge().

  3. #3
    Junior Member
    Join Date
    Jan 2012
    Posts
    2
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Issue when returning an array

    Just noticed it (in the wikipedia pseudocode algorithm) right as you replied pbrockway2.

    You are correct, the left being sent on is not what I want it to be:

    mergeSort(left);
    should instead be:
    left = mergeSort(left);

    Problem solved!

  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: Issue when returning an array

    Too late. Deleted.

  5. #5
    Super Moderator pbrockway2's Avatar
    Join Date
    Jan 2012
    Posts
    987
    Thanks
    6
    Thanked 206 Times in 182 Posts

    Default Re: Issue when returning an array

    Quote Originally Posted by Broxxar View Post
    Problem solved!
    Great - I'm glad you've got it figured out.

Similar Threads

  1. Array issue
    By Mini83 in forum Collections and Generics
    Replies: 5
    Last Post: August 18th, 2011, 09:18 AM
  2. returning 2d array in java
    By dr.code.skm in forum Member Introductions
    Replies: 2
    Last Post: July 20th, 2011, 10:14 AM
  3. Having trouble returning the right out put.
    By byako in forum What's Wrong With My Code?
    Replies: 1
    Last Post: March 26th, 2011, 11:49 PM
  4. returning a 2D array
    By straw in forum What's Wrong With My Code?
    Replies: 3
    Last Post: March 11th, 2010, 04:30 AM
  5. Returning Random Strings from an Array
    By cfmonster in forum Collections and Generics
    Replies: 3
    Last Post: September 8th, 2009, 11:13 PM