Partition a list of numbers into even and uneven numbers

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  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  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.

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.

StackExchange Code Review Q#79242, answer score: 4