CMSC 15100 — Lecture 27

Imperative Randomized Quicksort

Note. You do not need to know this for the exam.

(: swap! (All (A) (-> (Vectorof A) Integer Integer Void)))
;; Swap the ith and jth elements of the vector
(define (swap! v i j)
  (local
    {(define tmp (vector-ref v i))}
    (begin (vector-set! v i (vector-ref v j))
           (vector-set! v j tmp))))

(: partition! (-> (Vectorof Integer) Integer Integer Integer))
;; Partitions given portion of vector around first element in place and 
;; produces the final location of the pivot element as output
(define (partition! v l r)
  (local
    {(define pivot (vector-ref v l))
     (define i (add1 l))}
    (if (> i r)
        l
        (if (<= (vector-ref v i) pivot)
            (begin (swap! v l i)
                   (partition! v (add1 l) r))
            (begin (swap! v i r)
                   (partition! v l (sub1 r)))))))

(: quick-sort! (-> (Vectorof Integer) Void))
;; Sorts vector in-place, with randomized pivot
(define (quick-sort! vec)
  (local
    {(define len (vector-length vec))
     (: qs! (-> (Vectorof Integer) Integer Integer Void))
     (define (qs! v l r)
       (if (< l r)
           (begin (swap! v l (random l r)) 
                  (local 
                    {(define p (partition! v l r))} 
                    (begin (qs! v l (sub1 p)) 
                           (qs! v (add1 p) r))))
           (void)))}
    (qs! vec 0 (sub1 len))))