Moving even elements to the front of an array while keeping relative order

Question

public static void teePaarisPaaritud(int[] a){
    teePaarisPaaritudRek(a, 0);
}

private static void teePaarisPaaritudRek(int[] a, int i) {
    if(i == a.length-1) return;

    if(a[i] % 2 != 0){
        int temp = a[i];
        a[i] = a[i+1];
        a[i+1] = temp;
        teePaarisPaaritudRek(a, i+1);
    }
    teePaarisPaaritudRek(a, i+1);
}

I wrote this recursive method. The intended function is to sort the int[] by moving the even elements to the front and odd ones to the back, while keeping the original order between the even elements and odd elements.

For example with the input of int[] a = {-1,0,-7,3,10,4,0,2,-1,-5,6} the output should be [0,10,4,0,2,6,−1,−7,3,−1,−5]. However, my code misses the mark by a little and the output I get is [0, 10, 4, 0, 2, 6, -7, 3, -1, -5, -1] instead.

As you can see the 2nd -1 is in the back, but it should be before the -7. I've tried setting the base to if(i == a.length-2) return;. That didn't work, because then the 6 would remain in the end. The issue only arises when the length of the input array is even.

Answer 1

You can change your condition and recursion as follows:

if (a[i] % 2 != 0 && a[i + 1] % 2 == 0) {
    // swap and recurse starting from the beginning
}

// don't swap and recurse

In other words: if the next element is even, then go ahead and swap, moving the odd element to the right; otherwise, don't swap the elements. Your existing approach swaps elements even if they're both odd, which disorders the odd subarray.

Furthermore, restarting the whole process whenever a swap occurs handles cases where a swap isn't performed because two odd elements are next to each other.

public class Main {
    public static void moveEvenToFront(int[] a) {
        moveEvenToFrontRec(a, 0);
    }

    private static void moveEvenToFrontRec(int[] a, int i) {
        if (i == a.length - 1) {
            return;
        }
        else if (a[i] % 2 != 0 && a[i+1] % 2 == 0) {
            int temp = a[i];
            a[i] = a[i+1];
            a[i+1] = temp;
            moveEvenToFrontRec(a, 0);
            return;
        }

        moveEvenToFrontRec(a, i + 1);
    }

    public static void main(String[] args) {
        int[] a = {-1, 0, -7, 3, 10, 4, 0, 2, -1, -5, 6};
        moveEvenToFront(a);

        for (int n : a) {
            System.out.print(n + " ");
        }
    }
}

I think moveEvenToFrontRec(a, Math.max(i - 1, 0)); would work too instead of restarting all the way from the front, but I haven't checked this thoroughly.

That said, I wouldn't use recursion for this. It's harder to code, has more overhead and will blow the stack if the list is more than a few thousand items. Recursion is appropriate for logarithmic divide and conquer problems like binary search and balanced tree traversals.

The time complexity of your recursive algorithm is quadratic. A more efficient algorithm is to use a bit of extra space and loop over the array multiple times:

class Main {
    public static void moveEvenToFront(int[] a) {
        int[] cpy = a.clone();
        int i = 0;

        for (int n : cpy) {
            if (n % 2 == 0) {
                a[i++] = n;
            }
        }

        for (int n : cpy) {
            if (n % 2 != 0) {
                a[i++] = n;
            }
        }
    }

    public static void main(String[] args) {
        int[] a = {-1, -2, 1, 0, 2, 3, 4, 5};
        moveEvenToFront(a);

        for (int n : a) {
            System.out.print(n + " "); // => -2 0 2 4 -1 1 3 5
        }
    }
}

This can be optimized further, and the allocation cost may make it less efficient on very small arrays than the allocation-free quadratic approach.

Here's a quadratic iterative version, non-optimal but shared for comparison to OP's recursion:

public static void moveEvenToFront(int[] a) {
    for (boolean swapped = true; swapped; ) {
        swapped = false;

        for (int i = 0; i < a.length - 1; i++) {
            if (a[i] % 2 != 0 && a[i + 1] % 2 == 0) {
                int temp = a[i];
                a[i] = a[i + 1];
                a[i + 1] = temp;
                swapped = true;
            }
        }
    }
}

Merge sort mentioned in this answer also seems good, linearithmic and constant space. The intuition there is that the base case element of 1 is already ordered properly, then when merging two subarrays, relative order is maintained and it's easy to append the even element subarray first.