Segregate even and odd numbers in a given array

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?

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

StackExchange Code Review Q#90595, answer score: 13