Problem: Given a vector, a position in that vector, and a predicate that expresses a total ordering on a domain that includes the elements of that vector, identify the element that would occupy the specified position if the vector were completely sorted.
One approach is to sort the vector and inspect the position, but that's unnecessarily inefficient. A faster way is to partition the vector, using the value currently occupying the specified position as the pivot, and then to re-partition just the sub-vector that contains the specified position, and so on recursively, narrowing the sub-vector at each step, until one of the pivots turns out to be correctly placed in the specified position.
The internally defined
partition! procedure is a lightly
edited version of the one developed elsewhere
in this collection. The main change is that we are now partitioning not
the entire vector but the sub-vector that runs from a specified starting
start up to, but not including, a specified ending
The main program is simply a recursion in which(define kth-least (lambda (vec k . opt) (let ((partition! (let ((precedes? (if (null? opt) < (car opt)))) (lambda (start stop pivot) (letrec ((rightwards (lambda (current) (if (and (< current stop) (precedes? (vector-ref vec current) pivot)) (rightwards (+ current 1)) current))) (leftwards (lambda (current) (if (or (< current start) (precedes? (vector-ref vec current) pivot)) current (leftwards (- current 1)))))) (let loop ((left-pointer (rightwards start)) (right-pointer (leftwards (- stop 1)))) (if (< left-pointer right-pointer) (begin (vector-swap! vec left-pointer right-pointer) (loop (rightwards (+ left-pointer 1)) (leftwards (- right-pointer 1)))) left-pointer))))))) (let loop ((start 0) (stop (- (vector-length vec) 1))) (let* ((pivot (vector-ref vec stop)) (break (partition! start stop pivot))) (vector-swap! vec break stop) (cond ((< k break) (loop start (- break 1))) ((< break k) (loop (+ break 1) stop)) (else pivot)))))))
stop, initially the leftmost and rightmost positions in the vector, differ by less on each recursive call. At each step, the last element of the sub-vector is chosen as the pivot, and the rest of the sub-vector is partitioned. The variable
breakis set to the leftmost position occupied by a value greater than or equal to the pivot, and then the pivot is swapped into that position, so that items in positions to the left of
breakare all strictly less than the pivot, and those to the right of
breakare all greater than or equal to the pivot. This means that the pivot is now in whatever position it would occupy in a completely sorted vector.
At this point there are three possibilities: If
k is less
break, we need only look at the sub-vector to the left of
the pivot, and a recursive call is issued to search that sub-vector.
k is greater than
break, we search
the sub-vector to the right of the pivot. In either of these cases, the
sub-vector to be searched has been reduced by at least one element (since
it does not include the pivot). The third possibility is that
break are equal; in this case, the problem
is solved, since the pivot, now occupying position
k, is in
the correct position.
Since in each call we either find the element we're looking for or reduce the number of elements in the sub-vector, the recursion must ultimately terminate in a successful solution.
This document is available on the World Wide Web as
John David Stone (email@example.com)