November 30, 2012
select function is recursive. The first
if stops the recursion when the length of the list is small, when it sorts to find the median. Then we calculate the median of the median of five in the variable m, and use that to partition the input, recurring on whichever of the less-than or greater-than pieces contains k; when the pivot is equal to k, recursion stops.
(define (select lt? xs k)
(define (median5 xs)
(select lt? xs (quotient (+ (length xs) 1) 2)))
(let ((len (length xs)))
(if (< len 10) (list-ref (sort lt? xs) (- k 1))
(let* ((ts (map median5 (split5 xs)))
(m (select lt? ts (quotient len 10))))
(lambda () (partition lt? xs m))
(lambda (lt eq gt)
(let ((lt-len (length lt)) (eq-len (length eq)))
(cond ((<= k lt-len)
(select lt? lt k))
((< (+ lt-len eq-len) k)
(select lt? gt (- k lt-len eq-len)))
The other pieces are standard.
Partition scans a list, putting elements in bins as they are less than, greater than, or equal to the pivot.
Split5 repeatedly calls
split from the Standard Prelude to partition the input into blocks of five.
(define (partition lt? xs x)
(let loop ((xs xs) (lt (list)) (eq (list)) (gt (list)))
(cond ((null? xs) (values lt eq gt))
((lt? (car xs) x) (loop (cdr xs) (cons (car xs) lt) eq gt))
((lt? x (car xs)) (loop (cdr xs) lt eq (cons (car xs) gt)))
(else (loop (cdr xs) lt (cons (car xs) eq) gt)))))
(define (split5 xs)
(let loop ((xs xs) (xss (list)))
(if (null? xs) (reverse xss)
(lambda () (split 5 xs))
(lambda (head tail)
(loop tail (cons head xss)))))))
Though this algorithm has guaranteed linear run time, it is typically slower than the randomized algorithm because of the time required to calculate the median of the medians of five. Thus, the randomized algorithm is probably the preferred algorithm for most purposes.
You can run the program at http://programmingpraxis.codepad.org/yLPKhxuw.
Pages: 1 2