• 博客访问： 852738
• 博文数量： 104
• 博客积分： 3715
• 博客等级： 中校
• 技术积分： 1868
• 用 户 组： 普通用户
• 注册时间： 2006-04-30 08:38

2013年（1）

2012年（9）

2011年（41）

2010年（3）

2009年（3）

2008年（47）

2012-05-05 20:27:38

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.

1. #lang racket

2. ;; find the first element satisfied pred?
3. (define (find-next pred? vec start)
4.   (let loop ((index start))
5.     (if (or (>= index (vector-length vec))
6.             (pred? (vector-ref vec index)))
7.         index
8.         (loop (+ index 1)))))

9. ;; find the previous element statisfied pred?, exclude start
10. (define (find-prev pred? vec start)
11.   (let loop ((index (- start 1)))
12.     (if (or (< index 0)
13.             (pred? (vector-ref vec index)))
14.         index
15.         (loop (- index 1)))))

16. (define (eo-partition vec)
17.   (let loop ((start 0) (end (vector-length vec)))
18.     (define left (find-next odd? vec start))
19.     (define right (find-prev even? vec end))
20.     (if (>= left right)
21.         vec
22.         (let ((tmp (vector-ref vec left))
23.               (nstart (+ left 1))
24.               (nend (- right 1)))
25.           (vector-set! vec left (vector-ref vec right))
26.           (vector-set! vec right tmp)
27.           (loop nstart nend)))))