## Even-Odd Partition

### May 4, 2012

I’m not sure where this problem comes from; it’s either homework or an interview question. Nonetheless, it is simple and fun:

Take an array of integers and partition it so that all the even integers in the array precede all the odd integers in the array. Your solution must take linear time in the size of the array and operate in-place with only a constant amount of extra space.

Your task is to write the indicated function. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

### 31 Responses to “Even-Odd Partition”

1. Let’s eat the banana from both ends.

Also, in my book it’s a good praxis to always extract some reusable bits of code, generalizing the problem and the solution.

;; Common Lisp:

(defun predicate-sort (vector predicate)

DO: Modifies the VECTOR so that all the elements for which the
PREDICATE is NIL are before all the elements for which the
PREDICATE is true.
RETURN: VECTOR

(loop
:for i = (position-if predicate vector)
:then (position-if predicate vector :start (1+ i))
:for j = (position-if-not predicate vector :from-end t)
:then (position-if-not predicate vector :end (1- j) :from-end t)
:while (and i j (< i j))
:do (rotatef (aref vector i) (aref vector j)))
vector)

(defun sort-even-odd (vector)
"
Take an array of integers and partition it so that all the even
integers in the array precede all the odd integers in the array. Your
solution must take linear time in the size of the array and operate
in-place with only a constant amount of extra space.
"
(predicate-sort vector (function oddp)))

(sort-even-odd (vector 1 2 3 4 5 6 7))
#(6 2 4 3 5 1 7)

(sort-even-odd (vector 6 2 3 4 5 1 7))
#(6 2 4 3 5 1 7)

(sort-even-odd (vector 6 2 9 3 4 5 1 7))
#(6 2 4 3 9 5 1 7)

(sort-even-odd (vector))
#()

(sort-even-odd (vector 1 3 5 7))
#(1 3 5 7)

(sort-even-odd (vector 2 4 6 8))
#(2 4 6 8)

(sort-even-odd (vector 1 3 2 4 6 8))
#(8 4 2 3 6 1)

2. ionial said

My solution in python. It is just a variation of quick-sort partition
import sys
import random

def isodd(num):
return bool(num & 1)

def parteo(a):
even = 0
odd = len(a) – 1
while even “,arr
part = parteo(arr[:]);
print “<",part
print "Bug found", arr, "\n", part, "\nError at", idx

check_alg()
print "Finished"

3. ionial said

Ouch, it doesn’t get the python code – ate it all :-(
How do I post a snippet?

4. programmingpraxis said

As shown in “HOWTO: Posting Source Code” in the menu bar at the top of the page.

5. ionial said

Just a variation on quicksort partition

6. ionial said

``` import sys import random```

``` def isodd(num):     return bool(num & 1) def parteo(a):     even = 0     odd = len(a) - 1     while even < odd:         if isodd(a[even]):             if isodd(a[odd]):                 odd = odd-1             else:                 t = a[odd]                 a[odd] = a[even]                 a[even] = t                 even = even + 1                 odd = odd - 1         else:             even = even + 1     return a          def val_parteo(a):     in_odd = False     for idx in range(len(a)):         if isodd(a[idx]):             in_odd = True;         elif in_odd:             return idx     return -1 def gen_arr(size):     a=[]     for idx in range(size):         a.append(random.randint(1,1000))     return a def check_alg():     for size in range(1,20):         for tst in range(1,5):             arr = gen_arr(size);             print ">",arr             part = parteo(arr[:]);             print "<",part             bad_idx = val_parteo(part);             if bad_idx != -1:                 print "Bug found", arr, "\n", part, "\nError at", idx check_alg() print "Finished" ```

7. ionial said
```import sys
import random

def isodd(num):
return bool(num & 1)

def parteo(a):
even = 0
odd = len(a) - 1
while even < odd:
if isodd(a[even]):
if isodd(a[odd]):
odd = odd-1
else:
t = a[odd]
a[odd] = a[even]
a[even] = t
even = even + 1
odd = odd - 1
else:
even = even + 1
return a

def val_parteo(a):
in_odd = False
for idx in range(len(a)):
if isodd(a[idx]):
in_odd = True;
elif in_odd:
return idx
return -1

def gen_arr(size):
a=[]
for idx in range(size):
a.append(random.randint(1,1000))
return a

def check_alg():
for size in range(1,20):
for tst in range(1,5):
arr = gen_arr(size);
print ">",arr
part = parteo(arr[:]);
print "<",part
print "Bug found", arr, "\n", part, "\nError at", idx

check_alg()
print "Finished"

```
8. ionial said

just tried all the ways to publish, hopefully you’ll not get annoyed and just delete all irrelevant commentaries – I’d do it myself if there was an option

9. snowyote said

# probably not the most idiomatic ruby, but:

def partition(arr)
bottom, top = 0, arr.length-1
while bottom < top do
if yield(arr[bottom])
bottom += 1
elsif yield(arr[top])
arr[bottom], arr[top] = arr[top], arr[bottom]
bottom += 1
top -= 1
else
top -= 1
end
end
arr
end

def even_odd_partition(arr)
partition(arr) { |n| n.even? }
end

def fuzztest(times, dim)
times.times do
a = ((1..dim).map { rand(2) })
b = a.sort
raise "Damn: #{a}" if eopart(a) != b
end
end

10. stefan said

I beleve that this should work in scheme,

(define (partition ar)
(let ((N (vector-length ar)))
(define (find pred n)
(let ((n (+ n 1)))
(if (< n N)
(if (pred (vector-ref ar n))
n
(find pred n))
#f)))
(let loop ((even (find even? -1)) (odd (find odd? -1)))
(if (and even odd)
(if (< even odd)
(loop (find even? even) odd)
(let ((temp (vector-ref ar even)))
(vector-set! ar even (vector-ref ar odd))
(vector-set! ar odd temp)
(loop (find even? even) (find odd? odd))))))
ar))

11. ardnew said

Runs in linear time O(2N) on input list of size N. Not sure what’s meant by “constant amount of extra space”, but the sum number of elements required for “extra” storage will be exactly N.

```sub partition
{
return ((grep{!(\$_&1)}@_), (grep{\$_&1}@_));
}
```

Usage:

```@new_list = partition(1 .. 100);
```
12. ardnew said

Hmm, looks like I missed the “in-place” condition, as this method generates a new list

13. Mike said

Python

Basically scan from both ends and swap an odd number from the front of the list with an even number from the back of the list.

```def evenodd(lst):
i, j = 0, len(lst)-1

while i < j:
# search forward for the next odd number
while not lst[i] & 1 and i < j:
i += 1

# search backward for the next even number
while lst[j] & 1 and j > i:
j -= 1

# swap them
lst[i], lst[j] = lst[j], lst[i]
```
14. ccnovice said
```//+ trivail auxiliary functions are left out
int even( int);
void swap(int *,int *);

//input: an array (usual pointer + size), output - array rearranged in place
void even_1st_array( int *arr, int nn) {
//i & j - last unknown indeces, for evens from beginning of array and odds from its end resp.
int i, j;

//INVARIANT: all arr[x] are : x: [0..i) - even;  x: (j..NN-1] - odd;  [i..j] - unknown yet.
while( i<j) {                         //while unknwn el-s left +(last one i==j doesn't need to be moved)
while( i<=j && even(arr[i]) i++;    //mark all seq.even el-s, that are already in place, as known-even
while( j>=i && !even(arr[j]) j--;   //same - odd vaulues, from the top
if( i<j) {          //NOW: all done (i>=j) OR we have a pair to rearrange !even(arr[i]) && even(arr[j])
swap( &arr[i], &arr[j]);
i++; j--;
}
}
}```

* constant xtra storage – 2 indeces, 1 cell in swap()
* time – linear to intut array size
* does not preserve el-s original _order_

Main loop variant with ordering bonus:

```  //INVARIANT's the same
// + orig. even el-s order && odd el-s order are preserved
i=0, j=nn-1                           //same as above: all values in unknown range
while( i<j) {                         //same: while >1 unknown
while( i<=j && even(arr[i]) i++;    // ...already in place even vals

//bubble up an odd el. thru even ones //no even (or odd) vals original order changed
while( i<j && even(arr[i+1]) swap(&arr[i],&arr[i+1]),i++;

while( j>=i && !even(arr[j]) j--;   // ...odds aldeady in place

//bubble dwn an even el. thru odd ones //...preserving the all-evens and al-odds order
while( j>i && !even(arr[j-1]) swap(&arr[j],&arr[j-1]),j--;
}
}```

* constant xtra storage – same as above
* time – O(nn^2), i guess
* preserves all even values and all odd values original _order_

15. Jussi Piitulainen said

There’s an obvious half-liner to keep the order of evens and the order of odds when *not* observing the O(1) space, O(n) time requirements: use a stable in-place sort (from the standard library of the language) by oddity. Is there a way to do this within the requirements? I suspect not. (The illustration’s in Python 3.)

```def evnodd(ints): ints.sort(key = lambda n : n % 2)
```
```>>> ms = [1, 2, 3, 4, 5, 6, 7, 8, 9, 0]
>>> evnodd(ms)
>>> ms
[2, 4, 6, 8, 0, 1, 3, 5, 7, 9]
```
16. ardnew said

@Jussi, how can you assume that sort routine runs in O(n)?

17. Axio said
```#include<iostream> // cout, cin
#include<cstdlib> // rand

using namespace std;

#define ODD(x) ((x)%2 == 0)
#define EVEN(x) ((x)%2 != 0)

void evenOddPartition (int[], size_t);
void printArray(int[], size_t);
void genArray(int[], size_t);

int main (){
size_t nums;
cout << "How many numbers do you want to split?" << endl;
cin >> nums;
int *numbers = new int[nums];

cout << "Will partition" << endl;
genArray(numbers, nums);
cout << endl;

evenOddPartition(numbers, nums);

cout << "Even-oddly partitioned, this gives" << endl;
printArray(numbers, nums);

return 0;
}

void evenOddPartition(int numbers[], size_t size){
int *left, *right;
int tmp;
left = numbers; // start of array
right = numbers;
right += size - 1; // end of array
while (left < right) { // stop if we went too far
if (ODD(*left)){ // find next even number on the left
left++;
continue;
}
if (EVEN(*right)){ // find next odd number on the left
right--;
continue;
}
tmp = *left;        // swap
*left = *right;
*right = tmp;
left++;             // and progress
right--;
}
}

void printArray(int numbers[], size_t size){
for (int i = 0 ; i< size; i++) {
cout << numbers[i] << ", ";
}
cout << endl;
}

void genArray(int numbers[], size_t size){
srand(time(NULL));
for (int i = 0 ; i< size; i++) {
numbers[i] = rand() % 100;
}
}
```
18. Jussi Piitulainen said

@ardnew, I don’t assume sort takes O(n) time. I said it does *not* satisfy the complexity requirements. Perhaps I said it in an obscure way.

19. ardnew said

@Jussi, hah sorry. I’m slow and dense

20. Jon Bodner said

Implemented in Go: https://gist.github.com/2628990

21. robert said

evenOdd x = [n | n <- x, even n] ++ [m | m <- x, odd m]
[/sourcecode language="css"]

22. jasonostrander said

Heh, and I screwed up the comment as well. Another attempt:

23. jasonostrander said
```
def evenodd(li):
i = 0
j = 0
while i < len(li):
if not li[i] & 1:
li[i],li[j] = li[j],li[i]
j += 1
i += 1
```
24. my solution is pretty much the same as jasonostrander

```def partition(a):
j = 0
for i in range(len(a)):
if a[i] % 2 == 0:
a[j], a[i] = a[i], a[j]
j += 1
```
25. VJ said

Here is the code in C that works for any numbers and complexity is O(n) and space complexity can be optimized.
#include
#include

int is_odd(int num)
{
return (num%2 != 0);
}

void display_num(int num[], int count)
{
int i;
for ( i = 0; i < count ; i++)
{
printf("%d\n", num[i]);
}
}

{
int r_odd = -1, i ;
int r_even = -1, j ;
int temp_num;

i = 0;
j = count-1;
while ( 1 )
{
// Check first half if any odd number is
// present.
if ( r_odd == -1 ) {
if ( is_odd(num[i] )) {
r_odd = i;
}
else {
i++;
}
}

if ( r_even == -1 ) {
if ( !is_odd(num[j])) {
r_even = j;
}
else {

26. anuvab1911 said

#include
#define MAX 10
using namespace std;
main()
{
srand(time(NULL));
int i,j=0,k=MAX,l,ar[MAX],temp,a=0,b=0,z;
for(i=0;i<MAX;i++)
{
ar[i]=rand()%1000;
cout<<ar[i]<<" ";
if(ar[i]%2==0)
a++;
else
b++;
}
cout<<endl<<"Output"<<endl;
z=a;
for(i=0;i<a;i++)
{
if(ar[i]%2==1)
{
temp=ar[i];
for(l=z;l<MAX;l++)
{
if(ar[l]%2==0)
{
break;
}
}
ar[i]=ar[l];
ar[l]=temp;
z++;
}
}
for(i=0;i<MAX;i++)
cout<<ar[i]<<" ";
}

The above program fills an array of size 10 with random numbers less than 1000 and sorts them as required in the even first-odd next sequence

27. Anju said

//currentSum=max(currentSum+num, num) maxSum=max(currentSum, maxSum)//Why do we need this at every iteration / pnsriag? def largestContinuousSum(arr): if len(arr)==0: return maxSum=currentSum=arr for num in arr[1:]: if num < 0 { maxSum=max(currentSum, maxSum) currentSum = 0 } else, currentSum += num return maxSum

28. ```def part(l):
i = 0
j = len(l)
while i != j:
if l[i] % 2:
j -= 1
t = l[i]
l[i] = l[j]
l[j] = t
else:
i += 1
return l
```

Swaps any odd numbers to a moving end index, which converges with the search index once it’s done.

29. Dinesh Atal said

i waanna to sort even odd number by partition (quick sort) in python .can you help me