4
\$\begingroup\$

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.
\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ I have to admit, I don't understand how any array copying could be faster than copying each element... \$\endgroup\$ – Syd Kerckhove Feb 1 '15 at 13:14
  • \$\begingroup\$ See my updated answer for more optimization. Run a benchmark to see the difference. Arrays.copyOf is a nativ call, which is likely faster and better optimized than your code is. \$\endgroup\$ – barq Feb 1 '15 at 13:18
  • \$\begingroup\$ Thanks, another question: doesn't the compiler optimize the a.length call? \$\endgroup\$ – Syd Kerckhove Feb 1 '15 at 13:19
  • \$\begingroup\$ No, it does not since 'a' may change between iterations of the loop. If this is not the case then you as a programmer can take advantage of this fact and optimize. \$\endgroup\$ – barq Feb 1 '15 at 15:54
  • \$\begingroup\$ A better solution is to declare your arrays final so that the compiler can be guaranteed that the array never changes and perform much better optimizations anyway. \$\endgroup\$ – fluffy Feb 1 '15 at 17:35
4
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ I believe my code for solution three is absolutely equivalent to yours... \$\endgroup\$ – Syd Kerckhove Feb 1 '15 at 16:14
  • \$\begingroup\$ And thank you for the last solution, it's stable and in-place, the one combination I was missing. \$\endgroup\$ – Syd Kerckhove Feb 1 '15 at 16:16
  • \$\begingroup\$ You may think so, but you'd be wrong. Let me put together a test case to show you.... \$\endgroup\$ – rolfl Feb 1 '15 at 16:16
  • \$\begingroup\$ Additionally, your code might switch the front and back elements when front is greater or equal than back. \$\endgroup\$ – Syd Kerckhove Feb 1 '15 at 16:22
  • \$\begingroup\$ @SydKerckhove - here's an IDEONE that shows the difference in the number of evenness chaecks that our code does: ideone.com/8wOzmB \$\endgroup\$ – rolfl Feb 1 '15 at 16:32
3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ for each is slower than the loop I propose as the length of arr can still change. Thus the compiler optimization in for each is worse than the manual optimization of computing the size once and considering that the size does not change. \$\endgroup\$ – barq Feb 1 '15 at 15:52
  • \$\begingroup\$ @barq In case of arrays, a for-each loop is just as fast as a counting loop. Of course the compiler can make the same optimization as you do with the length. The for-each loop has the added benefit of readability, and it's the last thing to micro-optimize. See also this: stackoverflow.com/questions/9226483/… and this: developer.android.com/training/articles/perf-tips.html \$\endgroup\$ – janos Feb 1 '15 at 16:04
  • \$\begingroup\$ Not if you precompute the length. Then a counting loop is faster. See stackoverflow.com/questions/6093537/for-loop-optimization. \$\endgroup\$ – barq Feb 1 '15 at 16:08
  • 3
    \$\begingroup\$ Arguing about the performance of for-each vs. for-with-loop-variable is pointless without a specific test case, on a specific machine, fully-compiled JIT assembler output code, and profile data in a real use case. \$\endgroup\$ – rolfl Feb 1 '15 at 16:14
  • 1
    \$\begingroup\$ @barq How do you suppose the size of an int[] can change during iteration? I cannot see arrays addressed in the linked discussion. \$\endgroup\$ – janos Feb 1 '15 at 16:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.