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.

About these ads

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
    bad_idx = val_parteo(part);
    if bad_idx != -1:
    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
                bad_idx = val_parteo(part);
                if bad_idx != -1:
                    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.
      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_

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

    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 {

  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[0] 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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 630 other followers

%d bloggers like this: