Even-Odd Partition
May 4, 2012
We keep two indices: lo is the lowest-indexed element in the vector that we have not yet examined, and hi is the highest-indexed element in the vector that we have not yet examined. Initially, lo is 0 and hi is one less than the length of the vector. Then we iterate. At each step we look at the element at index lo. If it’s even, we increase lo by one and loop. If it’s odd, we swap the elements at lo and hi and reduce hi by one. Iteration continues until lo meets hi:
(define (even-odd vec)
(define (swap! a b)
(let ((t (vector-ref vec a)))
(vector-set! vec a (vector-ref vec b))
(vector-set! vec b t)))
(let loop ((lo 0) (hi (- (vector-length vec) 1)))
(cond ((= lo hi) vec)
((even? (vector-ref vec lo)) (loop (+ lo 1) hi))
(else (swap! lo hi) (loop lo (- hi 1))))))
If that’s not clear, here is the array at each step of the iteration, with the lo and hi indexes marked by vertical lines:
| 1 2 3 4 5 6 7 8 9 |
| 9 2 3 4 5 6 7 8 | 1
| 8 2 3 4 5 6 7 | 9 1
8 | 2 3 4 5 6 7 | 9 1
8 2 | 3 4 5 6 7 | 9 1
8 2 | 7 4 5 6 | 3 9 1
8 2 | 6 4 5 | 7 3 9 1
8 2 6 | 4 5 | 7 3 9 1
8 2 6 4 | 5 | 7 3 9 1
8 2 6 4 | | 5 7 3 9 1
This is clearly O(n) in time, as the unexamined part of the vector decreases by one element at each step. And it’s O(1) in space, storing the two indices and the swap element in addition to the input vector. Here’s an example:
> (even-odd '#(1 2 3 4 5 6 7 8 9))
#(8 2 6 4 5 7 3 9 1)
You can run the program at http://programmingpraxis.codepad.org/6JoM2tNp.
Programming Praxis 
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"
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.
sub partition { return ((grep{!($_&1)}@_), (grep{$_&1}@_)); }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.
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]//+ 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. i=0, j=nn-1; //start with all elements - unknown 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_
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)?
#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; } }@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:
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 += 1my 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.
i waanna to sort even odd number by partition (quick sort) in python .can you help me