10
\$\begingroup\$

Given an array A[], write a function that segregates even and odd numbers. The functions should put all even numbers first, and then odd numbers.

Example:

  • Input = {12, 34, 45, 9, 8, 90, 3}
  • Output = {12, 34, 8, 90, 45, 9, 3}

  • Input = {6, 4, 6, 8, 1, 1, 1}
  • Output = {6, 4, 6, 8, 1, 1, 1}

public static void main (String args[]) {
    int []array = {6,1,6,8,2,2,3};
    evenOddFunction(array);
    System.out.println(Arrays.toString(array));
}

private static void evenOddFunction(int []data) {
    int leftSide = 0;
    int rightSide = data.length - 1;

    while(rightSide >= leftSide) {
        if(data[leftSide] % 2 != 0 && data[rightSide] % 2 == 0) {
             // swapping as soon as we find even and odd combination
             swappEvenOdd(data, leftSide, rightSide);
             leftSide++;
             rightSide--;
        } else {
            if(data[leftSide] % 2 == 0) {
                leftSide++;
            }
            if(data[rightSide] % 2 == 1) {
                rightSide--;
            }
        }
    }
}

private static void swappEvenOdd(int []data , int left, int right) {
    // swapping even and odd numbers
    int temp = data[left];
    data[left] = data[right];
    data[right] = temp;
}

I don't want to use another array for this so went with swap logic. Any chances of improvement/optimizations in this code?

What is the minimum space and time complexity we can achieve for this problem?

\$\endgroup\$
  • 1
    \$\begingroup\$ Your function does segregate evens and odds, but does not produce the output in exactly the same order as in the examples. \$\endgroup\$ – 200_success May 13 '15 at 1:19
  • \$\begingroup\$ @200_success output format doesn't matter in this case. Just even numbers should be first and then odd numbers. \$\endgroup\$ – david May 13 '15 at 1:25
  • \$\begingroup\$ The C++ Standard Library has partition and stable_partition algorithms for these tasks. Surely there must be similiar stuff available for Java? \$\endgroup\$ – TemplateRex May 13 '15 at 7:13
  • \$\begingroup\$ @TemplateRex I'm sure there is a third party library that includes that functionality, but AFAIK, the JDK does not. \$\endgroup\$ – Simon Forsberg May 13 '15 at 11:43
13
\$\begingroup\$

I strongly doubt that your program does exactly this:

Example:
  Input = {12, 34, 45, 9, 8, 90, 3}
  Output = {12, 34, 8, 90, 45, 9, 3}

AFAIK the output will be

  Output = {12, 34, 90, 8, ...}

i.e., the elements get reordered because of the swapping. But that's alright according to what's required.


 private static void evenOddFunction(int []data) {

It's not a function, it's a method. And calling something evenOddMethod wouldn't be any better as there's no information therein. something like evenOddSegregator sounds better, but method names should be verbs. So maybe segregateEvenOdd?

    if(data[leftSide] % 2 != 0 && data[rightSide] % 2 == 0) {
        ...
    } else {
        if(data[leftSide] % 2 == 0) {
            ...
        }
        if(data[rightSide] % 2 == 1) {
            ...
        }

I hate repeated conditions. What about

    if(data[leftSide] % 2 == 0) {
        ...
    } else if(data[rightSide] % 2 == 1) {
        ...
    } else {
        ...
    }

It's not exactly the same, but this doesn't matter.

private static void swappEvenOdd(int []data , int left, int right) {

This is misnomer (and a type, too). There's nothing even nor odd in this method.

Any chances of improvement/optimizations in this code?

I guess your code is optimal, apart from this low-level optimization: Instead of (x % 2) use x & 1; it's much faster, works better for negative numbers, etc. But the JIT knows this trick too and there's not so much to gain.


An untested, stupid, but funny solution:

Comparator<Integer> comparator = new Comparator<>() {
    public int compare(Integer a, Integer b) {
        return (a & 1) - (b & 1);
    }
}
Collections.sort(Ints.asList(data), comparator);

The comparator claims that an even number is smaller than an odd number and sort does all the work. It's even stable, i.e., it doesn't reorder what it doesn't have to and produces the output from your example. Guava's Ints adapts the array as a List<Integer>.

\$\endgroup\$
6
\$\begingroup\$

Interface

It would have been helpful to add a disclaimer in the JavaDoc that the order of elements is not stable, especially considering that the examples you provided suggested that it might be stable.

Naming a function somethingFunction is highly redundant. I consider it to be an extreme form of Hungarian notation. I suggest evenOddPartition as the name for this function.

And what good is such a partitioning function? Although the problem statement does not require it, I think it would be a good idea for the function to tell you where the even-odd boundary lies. Therefore, I propose that it should return an int that indicates the count of even elements (or, alternatively viewed, the index of the first odd element, if there is one).

Finally, I should point out that you were asked to "write a function" that takes an array, not to "write a program" that does the task. I think that implies that the function you write should be public, not private.

Efficiency

Your strategy is to increment the leftSide index and decrement the rightSide index until they meet. The total number of index changes is, of course, data.length, so your algorithm is O(n), where n is the size of the array. Obviously, that bound cannot be improved upon, since there is no way to perform this task without inspecting every element at least once.

However, some micro-optimizations are still possible. To reach the else … if … leftSide++ branch, you would need to perform one index bounds check and three modulo-2 tests, which is quite redundant. Ideally, each leftSide++ should involve just one bounds check and one parity check.

I therefore propose this solution:

/**
 * Rearranges data such that all even numbers occur before odd numbers
 * (but otherwise not necessarily in any particular order).
 *
 * @return The count of even elements
 */
public static int evenOddPartition(int[] data) {
    int i = 0, j = data.length - 1;
    do {
        while (i <= j && (data[i] & 1) == 0) { i++; }
        while (i <= j && (data[j] & 1) != 0) { j--; }

        if (i >= j) {
            return i;
        }
        int swap = data[i];
        data[i] = data[j];
        data[j] = swap;
    } while (true);
}

I've chosen to just write the swap inline, rather than as a helper function. (By the way, why did you spell "swap" as swapp?) Arguably, breaking out the code into a helper function helps readability, and a JIT should be able to figure out that your private static helper function can be inlined, so in the long term, you have no function-call overhead. Still, the hassle can be avoided by just writing the code inline. I think that naming the temporary variable swap (better than temp) provides enough of a visual hint that readability doesn't suffer.

\$\endgroup\$
  • \$\begingroup\$ Speaking of variable names, you named two variables i and j... surely you could come up with something better than that? :) \$\endgroup\$ – Simon Forsberg May 13 '15 at 11:41
5
\$\begingroup\$

@maaartinus has excellent advice about the naming and structure of your code. I even appreciate his suggestion about doing an odd/even sort. It's slower for larger scales, but the code simplicity sure wins out.

Talking about scales.... part of your question is: What is the minimum space and time complexity we can achieve for this problem?

Well, the sort from maaartinus would be time-complexity of \$O(n \log n)\$ from the sort. That is not horrible, really, but it is not as good as the \$O(n)\$ of your implementation. It would not be possible to beat your \$O(n)\$ time complexity. As for space complexity yours, and maaartinus's jestful sort would both be \$O(1)\$, essentially nothing added.

What's the minimum possible? Time is \$O(n)\$, and space is \$O(1)\$. Bottom line, your code is about as good as you can hope for, in terms of scalability and complexity. I realize that maaartinus is not really serious about converting to a sort, but, in reality... perhaps he should be. The real issue with that is the need to box the values to Integers, etc.

What I really want to comment on, though, is your algorithm. Problems like this have 'landmarks'. Things you look for when processing the data. The landmarks are an indication of how you think... what you think the highlights are.

In your code, your loop changes 1 thing each iteration... either the left pointer, the right pointer, or it swaps a pair. In a sense, your code is:

  1. loop until done
  2. is the pointer setup swappable? If yes, then swap them, reloop
  3. otherwise, bring the pointers one step closer to being swappable

Now, there's nothing wrong with that, but it is not the way I think about things, so I like to code it differently. I like to have "positive states"... where I know where things are at. I would prefer the logic:

  1. identify something swappable
  2. if it is successful, swap them, otherwise done.
  3. loop to 1

To solve things my way, you have to be assertive about your conditions. Here's the code I would use (using names maaartinus suggests):

private static void segregateEvenOdd(int[] array) {
    int left = oddToSwap(array, 0, array.length - 1);
    int right = eventoSwap(array, array.length - 1, left);
    while (left < right) {
        int tmp = array[left];
        array[left] = array[right];
        array[right] = tmp;
        left = oddToSwap(array, left + 1, right);
        right = evenToSwap(array, right - 1, left);
    }
}

How do you read that? Well, it's as follows:

  1. move left to the first odd value
  2. move right to the last even value
  3. if there's a match, then swap them, and go to 1, else end.

There needs to be the implementation of the two helper methods:

private static int evenToSwap(final int[] array, int right, final int left) {
    while (right > left && (array[right] & 1) == 1) {
        right--;
    }
    return right;
}

private static int oddToSwap(final int[] array, int left, final int right) {
    while (right > left && (array[left] & 1) == 0) {
        left++;
    }
    return left;
}

I much prefer the above solution because it fits my way of thinking. On the other hand, it has other benefits too.... for example, it only checks each value once with the modulo's. Your solution could compare values multiple times.

A worst-case scenario for your code is that you have data that is all odd. In that case, you will check the modulo of the data at data[0] \$2n\$ times. With my code, it will be checked just once.

\$\endgroup\$

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.