Sorting an array recursively in Java with even numbers appearing in front of array.

Question

I'm using a method to sort out an array with even numbers coming out in the front and odd numbers in the back of the array. My assignment dictates that i accomplish this using recursion. When I try to print the sorted out array it just prints out the array unsorted. What am i doing wrong?

The left variable starts at index 0 and the right variable starts at the end of the index. They are then both compared, if left is an odd number and right is an even number then they swap values. If left turns out to be an even number then no swap takes place and it points at the next index in the array. If right turns out to be an odd number then no swap takes place and it points at the next index in the array. It does this until all the even numbers are on the right of the array.

I'm getting a

"Exception in thread "main" java.lang.StackOverflowError".

import java.util.*;
public class Problem2{

    //i=left 
    //j=right
    //first i tried to shift the whole thing
    //have all even numbers pop to the front of array when even
    public static int[] callme(int[] arry, int left, int right){
        int temp;
        if(left>=right)       //base case, return array
            return arry; 
        else if(arry[left]%2!=0 && arry[right]%2==0){//if match, do the swap
            temp=arry[left];
            arry[left]=arry[right];
            arry[right]=temp;   
            return callme(arry, left++, right--);
        }
        else{
            if(arry[right]%2!=0){//if right side is on odd #, then decrease index
                return callme(arry, left, right--);
            }
            if(arry[left]%2==0){//if left side is on even #, then increase index
                return callme(arry, left++, right);
            }
        } 
        return arry;
    }

    public static void main(String[] args){

        //int index=0;
        int[] arry={3,5,6,8};

        int[] newarry=callme(arry, 0, arry.length-1);
        System.out.print("The new sorted array is: ");
        for(int i=0; i<newarry.length;i++){
            System.out.print(newarry[i]+" ");
        } 
    }
}

Do the even numbers need to be sorted in ascending order (and similarly the odd numbers)? Or is the task just to get all the even numbers on one side without caring what order they're in? Or do the even and odd parts need to appear in the same order in which they started? — ajb
– ajb, Commented Feb 4, 2014 at 0:56

ajb · Accepted Answer · 2014-02-04 01:06:48Z

1

left++ is not the same as left + 1. If you want to call the method recursively with a left argument that is one higher, then call it with left + 1.

In this statement:

  return callme(arry, left++, right--);

the way it works is this: The program saves the current value of left, adds 1 to left, but then uses the value saved before it was incremented as the argument to the recursive call. The right-- argument works the same way. So when callme calls itself, it's calling itself with the exact same arguments it was called with. So you never get to the base case.

(Something else you should know about recursion: Each time a recursive method calls itself, it will have its own copy of the local variables, including the parameters. So even though the first method increases left, that has no impact on what left will be when it's called recursively, because the recursive methods have their own left.)

edited Feb 4, 2014 at 1:06

answered Feb 4, 2014 at 1:00

ajb

31.8k4 gold badges63 silver badges86 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

user1908627 Over a year ago

That was the problem. Thank you.

user3163916 · Accepted Answer · 2014-02-04 01:00:46Z

0

If you just want the even numbers to be on the top, no need to do left and right.

You could do:

int temp;

for (int i = 0; i < array.length; i++)
  if (array[i] % 2)
    for (int j = i + 1; j < array.length; j++)
      if !(array[j] % 2) {
        temp = array[j];
        array[j] = array[i];
        array[i] = temp;
        j = array.length;
      }

answered Feb 4, 2014 at 1:00

user3163916

3284 silver badges17 bronze badges

2 Comments

ajb Over a year ago

He said he had to use recursion. Does this do so? (Yes, I would never use recursion in real life to solve this problem. But this is apparently a class assignment, and professors seem to love teaching about recursion. It's mathematically elegant, or something.)

user3163916 Over a year ago

Thanks for the reminder, I was on the 'efficient' mindset. That's quite unfortunate though, recursion could be used for a much suitable problem, while for this particular one, iteration works better.

Collectives™ on Stack Overflow

Sorting an array recursively in Java with even numbers appearing in front of array.

2 Answers 2

1 Comment

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related