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

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)

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

bad_idx = val_parteo(part);

if bad_idx != -1:

print "Bug found", arr, "\n", part, "\nError at", idx

check_alg()

print "Finished"

Ouch, it doesn’t get the python code – ate it all :-(

How do I post a snippet?

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

Just a variation on quicksort partition

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"

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

# 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

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

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.

Usage:

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

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.

* 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:

* constant xtra storage – same as above

* time – O(nn^2), i guess

* preserves all even values and all odd values original _order_

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

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

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

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

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

evenOdd x = [n | n <- x, even n] ++ [m | m <- x, odd m]

[/sourcecode language="css"]

My Python solution, similar to Mike’s:

This may be less efficient, as it will swap elements when i = j, but I believe python optimizes that case to a no-op.

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

my solution is pretty much the same as jasonostrander

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]);

}

}

void arrange_even_add(int num[], int count)

{

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 {

#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

//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[0] for num in arr[1:]: if num < 0 { maxSum=max(currentSum, maxSum) currentSum = 0 } else, currentSum += num return maxSum

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