Partition a list of numbers into even and uneven numbers

Question

Input: An array of integers.

Output: That same array, but with the even numbers at the front and the uneven numbers at the back of the array.

I wrote three different solutions, depending on the needs of the client.

First solution:

// linear time not stable and not in-place
private static void partition1(int[] a){
    // not in place:
    int front = 0;
    int back = a.length -1;
    int[] tmp = new int[a.length];

    for (int t = 0; t < a.length; t++){
        if (a[t] % 2 == 0){
            tmp[front++] = a[t];
        } else { // not even -> must be uneven.
            tmp[back--] = a[t];
        }
    }

    for (int i = 0; i < a.length; i++){
        a[i] = tmp[i];
    }
}

Second solution:

// linear time, stable, not in-place
private static void partition2(int[] a){
    int front = 0;

    // to make it stable, figure out where to start placing the last ones
    int back = 0;
    for (int i = 0; i < a.length; i++){
        if (a[i] % 2 == 0)
            back++;
    }

    int[] tmp = new int[a.length];

    for (int t = 0; t < a.length; t++){
        if (a[t] % 2 == 0){
            tmp[front++] = a[t];
        } else { // not even -> must be uneven.
            tmp[back++] = a[t];
        }
    }

    for (int i = 0; i < a.length; i++){
        a[i] = tmp[i];
    }
}

Third solution:

// linear time, not stable, in-place
private static void partition3(int[] a){
    // invariant: [ even | i ... j | uneven ]

    int front = 0;
    int back = a.length - 1;

    // no tmp array!!
    int tmp;
    while (front < back){
        if (a[front] % 2 == 0){
            front++;
        } else if (a[back] % 2 == 1){
            back--;
        } else { // number at front is uneven and number at back is even
            tmp = a[front];
            a[front] = a[back];
            a[back] = tmp;
            front++;
            back--;
        }
    }
}

Feedback I'm looking for:

• Are these variable names OK?
• Is the code semantically correct?
• Can it be asymptotically faster?
• Any other style feedback.

Answer 1

Your naming for the array parameter 'a' is not good. Use something along the lines of input, input_array instead.

Also, rather than manually copying each element of the array in

for (int i = 0; i < a.length; i++){
    a[i] = tmp[i];
}

Use a = tmp.clone(); or a = Arrays.copyOf(tmp, tmp.length)

Arrays.copyOf has slightly bette performance than clone, but both are much better than manually iterating through the array as you are doing.

Also, rather than computing a.length each iteration you can use int size = a.length and then do for (int i = 0; i < size; i++) for even better performance.

Answer 2

As an exercise, I am pretty sure this would have been presented almost immediately before studying the Quick Sort, and Merge Sort algorithms. It has a strong parallel to the partitioning that is done for those.

As a general note, I know you have used the % 2 == 0 to test for identifying even numbers, I would recommend, for the reason that % operator requires division, that you instead use the mechanism & 1 == 0 to test for evenness. It is true that the compiler may well optimize the % in to a bitwise and, but I would not chance it.

Additionally, in a few places, you use manual code to copy data from the tmp to the array arrays. Use System.arraycopy instead.

Solution 3

Your solution3 is very similar to the Quick Sort partitioning, and for that reason, like it. It has some performance problems in that it repeats many tests. For example, an input array consisting of only odd numbers will have the element 0 tested for evenness every time, and there are ways to do that just once. So, while the time complexity is still \$O(n)\$, the computation is doing twice as many checks as necessary.

A different way of doing the partitioning with essentially the same result, but doing a evenness check only once per number, is as follows:

int front = 0;
int back = a.length - 1;

// no tmp array!!
while (front < back){
    while (front < back && a[front] & 1 == 0) {
        front++;
    }
    while (front < back && a[back] & 1 == 1) {
        back--;
    }
    // swap the back evennumber with the odd front number
    // occasionally front may == back.
    int tmp = a[front];
    a[front] = a[back];
    a[back] = tmp;
    front++;
    back--;
}

Solution 2

The second solution you have is similar to the merge sort in some ways, but not exactly. The merge sort is a stable not-in-place mechanism. While your solution loops through the content once to count the even numbers, I would also recommend a solution that just has one insertion point. Note that you test the evenness twice for each value. The following solution also does that... it's not worse:

int pos = 0;
int[] tmp = new int[array.length];
for (int val : array) {
    if (val & 1 == 0) {
        tmp[pos++] = val;
    }
}

for (int val : array) {
    if (val & 1 == 1) {
        tmp[pos++] = val;
    }
}

// Use System.arraycopy instead of a loop:

System.arraycopy(tmp, 0, array, 0, tmp.length);

Solution 1

This solution has the least issues with it, other than the manual copy from tmp to array. Again, use System.arraycopy

Insertion Sort

This is a missing solution, and it has some value to it, even though it is not O(n) performance. The reason it is useful is because, in an actual sort, it can do more logic than just test evenness for each value.

Consider this code:

int evenpoint = 0;
for (int i  = 0; i < array.length; i++) {
    if (array[i] & 1 == 0) {
        // needs to be inserted...
        int tmp = array[i];
        System.arraycopy(array, evenpoint, array, evenpoint + 1, i - evenpoint - 1);
        array[evenpoint++] = tmp;
    }
}

The above code takes each value, and, if it's even, it 'inserts' it before the odd values. The above algorithm draws a number of similarities to the insertion sort, which is, surprisingly, very fast for smaller data sets.

Answer 3

It would be better to use foreach to iterate over an array, whenever you can.

A variant on the second solution can be faster, if you copy the even numbers immediately as you see them, so that you don't need to repeat the modulo again. It will also make the array copy step at the end faster, as you can copy only the odd values.

private static void partition2alt(int[] arr) {
    int[] tmp = new int[arr.length];

    int front = 0;
    int back = 0;

    for (int item : arr) {
        if (item % 2 == 0) {
            arr[front++] = item;
        } else {
            tmp[back++] = item;
        }
    }

    System.arraycopy(tmp, 0, arr, front, back);
}

I used barq's good suggestion to use System.arraycopy for the array copying, as it's more optimized than doing it manually.

To make it easier to play with the different algorithms, it's good to add some unit tests, for example:

@Test
public void testStable() {
    int[] orig = {1, 8, 3, 2, 9, 6, 7, 5, 4};
    int[] partitioned = {8, 2, 6, 4, 1, 3, 9, 7, 5};

    int[] arr = orig.clone();
    partition2alt(arr);
    assertArrayEquals(partitioned, arr);
}

UPDATE

More about using for-each loops, in response to @barq's comments.

Trying to optimize a for-each loop by using a counting loop with a pre-calculated limit is micro-optimization, which you should only do when speed is critical, and there's nothing else you can improve on the overall design of the complete app.

Unless you are at the point of micro-optimization, using a for-each loop is the best practice. It's clear, easy to read, and it lets you focus on the logic (the elements), without having to keep track of the count.

The compiler often optimizes things for you. According to Google's performance tips for Android development, using a for-each loop is just as fast or faster than a counting loop, in case of arrays such as int[]. This is not true for an ArrayList, in which case a counting loop is 3x faster. But then again, you should only try to optimize the loop when there's nothing else to improve on the structure of your program.