Is there a way to more elegantly sort an array into even and odds?

Question

I am attempting to sort an array of integers such that all even numbers precede odd numbers, without using any external libraries. You may recognize this from: http://codingbat.com/prob/p105771

" Return an array that contains the exact same numbers as the given array, but rearranged so that all the even numbers come before all the odd numbers. Other than that, the numbers can be in any order. You may modify and return the given array, or make a new array. " I have code that accomplishes this goal:

    public int[] evenOdd(int[] nums) {
    int c=0;
    int c2=0;
    int [] nums2=new int[nums.length];
    for(int i=0;i<nums.length;i++)
    {
        if(nums[i]%2==0)
        {
            nums2[c]=nums[i];
            c++;
        }
        else
        {
            nums2[nums.length-c2-1]=nums[i];
            c2++;
        }
    }
    return nums2;
}

I have also approached the problem by calling array.sort() and then inserting the numbers by index, incrementing by two, then inserting the remainder. This also works.

So, to make a long post short-is there a more elegant way to accomplish this goal in future? Thanks!

Aside from some questions of style, your code is actually pretty good. In that task you can't do better than `O(N)` in terms of complexity, because you have to touch every element at least once, obviously. But `O(n)` you managed to achive. So, it's already better than sorting. The interesting open problem is how to achieve `O(n)` without extra-array :) — Dzmitry Paulenka, Jan 19 '16 at 23:07

score 2 · Accepted Answer · answered Jan 19 '16 at 23:16

Just a follow-up to my comment. Here is how you can do it in O(n) without extra-space:

public class Main {
    public static void main(String[] args) {
        evenOdd(new int[]{1, 2, 3, 4, 5, 6, 7});
        evenOdd(new int[]{2, 3, 4, 5, 6, 7});
        evenOdd(new int[]{1, 1, 1, 1, 1});
        evenOdd(new int[]{2, 2, 2, 2});
    }

    public static void evenOdd(int[] a) {
        int firstOdd = 0;
        for (int i = 0; i < a.length; ++i) {
            if (a[i] % 2 == 0) {
                int t = a[firstOdd];
                a[firstOdd] = a[i];
                a[i] = t;
                firstOdd++;
//            } else {
//                else is redundant, just leave odd in-place
            }
        }
        System.out.println(Arrays.toString(a));
    }
}

Indeed, but it would be great if there’s stable solution… — Holger, Jan 21 '16 at 09:22

Jim W · Answer 2 · 2016-01-20T00:16:41.503

Create a wrapper object that contains an int, call it SortingWrapper. This object should implement Comparable, such that its natural sort order is based on the sort order of value%2. Then just sort the array with Arrays.sort(). Based on the compareTo() implementation, the evens will naturally (ie, according to their natural sort order) bubble one way, all the odds will bubble the other.

Alternatively, you could just uses Integers as your wrapper and pass a Comparator that does the same thing to Arrays.sort().

edit- here is the general idea. You might have to play around with the sort order, but I think this pretty much works. I suspect that this array will count as "mostly sorted" which would make performance tend more towards O(n) than log(n), based upon the javadoc for Arrays.sort().

public void sortOddsAndEvents(Integer[] input)
{
    Arrays.sort(input, new Comparator<Integer>()
    {
        @Override
        public int compare(Integer arg0, Integer arg1)
        {
            if (arg0.equals(arg1)) return 0;
            else return Integer.compare(arg0.intValue()%2, arg1.intValue()%2);
        }

    });
}

score 0 · Answer 3 · edited Jan 19 '16 at 23:43

0

public int[] evenOdd(int[] nums) {

  int evenCounter = -1, oddCounter = nums.length;
  int[] ordered = new int[nums.length];

  for (int i = 0; i < nums.length; i++) {

      int current = (nums[i] % 2 == 0) ? ++evenCounter : --oddCounter;
      ordered[current] = nums[i];
  }
  return ordered;
}

edited Jan 19 '16 at 23:43

Jonas N

1,757
2
21
41

answered Jan 19 '16 at 23:06

ymz

6,602
1
20
39

Is there a way to more elegantly sort an array into even and odds?

3 Answers3