Even-Odd Partition

另一个简单的题目from planet scheme.

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  or  a suggested solution, or to post your own solution or discuss the exercise in the comments below.

我的代码如下：

#lang racket

;; find the first element satisfied pred?
(define (find-next pred? vec start)
  (let loop ((index start))
    (if (or (>= index (vector-length vec))
            (pred? (vector-ref vec index)))
        index
        (loop (+ index 1)))))

;; find the previous element statisfied pred?, exclude start
(define (find-prev pred? vec start)
  (let loop ((index (- start 1)))
    (if (or (< index 0)
            (pred? (vector-ref vec index)))
        index
        (loop (- index 1)))))

(define (eo-partition vec)
  (let loop ((start 0) (end (vector-length vec)))
    (define left (find-next odd? vec start))
    (define right (find-prev even? vec end))
    (if (>= left right)
        vec
        (let ((tmp (vector-ref vec left))
              (nstart (+ left 1))
              (nend (- right 1)))
          (vector-set! vec left (vector-ref vec right))
          (vector-set! vec right tmp)
          (loop nstart nend)))))