views:

252

answers:

6

I have the following function to sort an unordered array to having even numbers in the front and odd numbers in the back. Is there a way to get it done without using any loops?

//front is 0, back =array.length-1;
arrangeArray (front, back);

public static void arrangeArray (int front, int back)
{
    if (front != back || front<back)
    {
        while (numbers [front]%2 == 0)
            front++;


        while (numbers[back]%2!=0)
            back--;


        if (front < back)
        {
            int oddnum = numbers [front];
            numbers[front]= numbers[back];
            numbers[back]=oddnum;

            arrangeArray (front+1, back-1);
        }
    }
}
A: 

What you want to do is

arrangeArray(front, back, bool recursed=false) {
    if (recursed) {
        arrangeArray(front, back/2, true);
        return arrangeArray(back/2, back, true);
    }
    // Do stuff here.
}
DeadMG
Hmm... If you call it with record=false, it does nothing. If you call it with recursed=true, it recurses forever.
Oddthinking
+2  A: 

Mergesort is fairly trivial to code without loops:

void mergesort(int lo, int hi)
{
    if (lo<hi)
    {
        int m=(lo+hi)/2;
        mergesort(lo, m);
        mergesort(m+1, hi);
        merge(lo, m, hi);
    }
}

I'll leave making it sort even/odd as an exercise to the reader :)

(Sounds like homework)

Stephen
I don't think the structure of merge sort is the right kind of structure for this problem. This recurses in towards the middle, there's no divide and conquer involved, just pure iterative recursion.
Charles Ma
Charles: How is splitting the array in the middle, using recursion on both halves, and then merging them, not a divide-and-conquer algorithm?
hzap
I was saying that this problem doesn't require divide and conquer (which merge sort IS), divide and conquer problems are usually solved in O(nlogn), where as this one can be done in O(n)
Charles Ma
Oh and I'm assuming that it doesn't require numbers to be sorted among themselves, just the even half on the front (not necessarily sorted) and odd ones in the back.
Charles Ma
@Charles Ma: Yep, you got a +1 from me.
Stephen
See my answer for a complete and working recursive `O(N)` solution.
polygenelubricants
How is the merge done without using a loop of some sort?
Nathan Ernst
+2  A: 

When you do recursion, you have a base step and a recursive step.

In this case, the base condition is when front == back, because you start from the edges and end up in the middle. When you get to the middle you know it's done.

Before you do the recursive step, you have to do a bit of sorting. You're only doing the sorting one step at a time, so only deal with the elements at array[front] and array[back] for now. After you arrange those into the right place, do a recursive call.

You'll end up with something like this:

public static void arrangeArray (int front, int back)
{
   if(front >= back) return;
   int f = numbers[front];
   int b = numbers[back];
   if(f%2 == 0) {
      front++;
   } else {
      numbers[back] = f;
      back--;
   }
   if (b%2 == 0) {
      numbers[front] = b;
      front++;
   } else {
      back--;
   }  
   arrangeArray(front, back);                                         
}

It's untested and probably doesn't work for edge conditions, but it's a good start :)

Charles Ma
+2  A: 

Wouldn't that simply be:

//front is 0, back =array.length-1; 
arrangeArray (front, back); 

public static void arrangeArray (int front, int back) 
{ 
    if (front != back || front<back)
    { 
        if (numbers [front]%2 == 0) 
            arrangeArray (front+1, back); 
        else
        if (numbers[back]%2!=0) 
            arrangeArray (front, back-1); 
        else
        if (front < back) 
        { 
            int oddnum = numbers [front]; 
            numbers[front]= numbers[back]; 
            numbers[back]=oddnum; 

            arrangeArray (front+1, back-1); 
        } 
    } 
} 

?

500 - Internal Server Error
+1  A: 

May I recommend this Python snippet to inspire high level thinking?

compare = lambda x,y: x - y if x%2 == y%2 else y%2 - x%2
>>> sorted([3,4,2,1,5,6,7,90,23,44], cmp=compare)
[1, 3, 5, 7, 23, 2, 4, 6, 44, 90]

I think one needs to build a comparator function that returns negative, 0, and positive and use that.

Hamish Grubijan
A: 

The following should be instructive. It's a recursive O(N) solution that rearranges the even numbers in front and odd numbers in the back, but doesn't do any ordering beyond that.

static boolean isEven(int n) {
    return (n & 1) == 0;
}
static boolean isOdd(int n) {
    return !isEven(n);
}
static int[] swapped(int[] nums, int i, int j) {
    int t = nums[i];
    nums[i] = nums[j];
    nums[j] = t;
    return nums;
}
static int[] arrange(int[] nums, int lo, int hi) {
    return
        (lo >= hi) ? nums :
        (isEven(nums[lo])) ? arrange(nums, lo + 1, hi) :
        (isOdd(nums[hi])) ? arrange(nums, lo, hi - 1) :
        arrange(swapped(nums, lo, hi), lo + 1, hi - 1);
}   
static void evenOddSort(int... nums) {
    System.out.println(java.util.Arrays.toString(
        arrange(nums, 0, nums.length - 1)
    ));
}   
public static void main(String[] args) {
    evenOddSort(1,3,5,7,2,4,6);
} // prints "[6, 4, 2, 7, 5, 3, 1]"

I think the ternary operator makes the recursion flow more naturally, but if you're not that comfortable with how it works, you can just use traditional if-else.

static int[] arrange(int[] nums, int lo, int hi) {
    if (lo >= hi) {
        return nums;
    } else if (isEven(nums[lo])) {
        return arrange(nums, lo + 1, hi);
    } else if (isOdd(nums[hi])) {
        return arrange(nums, lo, hi - 1);
    } else {
        return arrange(swapped(nums, lo, hi), lo + 1, hi - 1);
    }
}
polygenelubricants
Abuse of nested ternary operators. :P
Stephen
@Stephen: I disagree. There's a reason why the ternary operator is right-associative, and it's to allow this kind of expression-level `if-else` like constructs.
polygenelubricants
I agree with Stephen. Just because you can write it without parentheses doesn't mean you should. The expression x ^ a + b ^ c + d is perfectly well-defined, but those who don't know the precedence rules by heart will be incredibly confused.
Keith Randall