Class 26: More Divide & Conquer: Quicksort

Reading

Sections 7.1 and 7.2 of Introduction to Algorithms.

Homework

Here's an implementation in Scheme of the partition function for partitioning a vector of integers with smaller values in the left partition, larger on the right:

(define (partition A i j s)
  (do ()
    ((< j i) j)
    (do () ((not (< (vector-ref A i) s)) ) (set! i (+ i 1)))    
    (do () ((or (> i j) (< (vector-ref A j) s)) ) (set! j (- j 1)))
    (if (< i j)
        (let ((tmp (vector-ref A i)))
          (vector-set! A i (vector-ref A j))
          (vector-set! A j tmp)))))

This partition implementation is the Scheme version of our psuedo-code below. Here is a Scheme implementation of quicksort for sorting vectors of integers in ascending order.

(define (qsort A i j)
  (if (not (= i j))
      (let ((k (partition A i j (vector-ref A i))))
        (if (< k i)
            (set! k i))
        (qsort A i k)
        (qsort A (+ k 1) j))))

You can test these pretty easily to see that they work. For example:

> (define (rand-int-vec n) (do ((v (make-vector n 0)) (i 0 (+ i 1))) ((= i n) v) (vector-set! v i (random (* 10 n)))))
> (define A (rand-int-vec 10))
> A
#10(1 63 15 0 65 17 68 63 56 51)
> (qsort A 0 9)
> A
#10(0 1 15 17 51 56 63 63 65 68)
> 

Your homework is to redefine partition and qsort so they take another argument, a "before?" predicate, and so that the vector is sorted with respect to that "before?" predicate: Example:

> (define (rand-int-vec n) (do ((v (make-vector n 0)) (i 0 (+ i 1))) ((= i n) v) (vector-set! v i (random (* 10 n)))))
> (define A (rand-int-vec 10))
> A
#10(80 36 46 8 36 43 33 41 92 66)
> (qsort A 0 9 <)
> A
#10(8 33 36 36 41 43 46 66 80 92)
> (qsort A 0 9 >)
> A
#10(92 80 66 46 43 41 36 36 33 8)
> (qsort A 0 9 (lambda (x y) (< (abs (- x 50)) (abs (- y 50)))))
> A
#10(46 43 41 36 36 66 33 80 92 8)
> 
	

Turn In: a printout of your source code and a screen capture of it working on the above 3 examples.

Partition

Our only divide and conquer sorting algorithm so far is mergesort. When we try mergesort with arrays we find that it has the undesireable property of requiring us to allocate additional memory. You see, if the "divide" step simply uses two halves of the initial array as its smaller subproblems, when we go to merge we won't have anyplace to put results as we merge ... the sublists we're mergeing will be in the way.

So we thought about ways we might do the "divide" step of a divide and conquer sorting method differently so as to be able to sort "in place", i.e. without having to allocate additional memory. We came to the conclusion that a "divide" step that moved all the small values to the left side of the array and all the large values to the right would be perfect, since when the "conquer" step was over, i.e. when the two halves had been sorted, there would be no "merge" step - the array would already be sorted at that point.

The parition algorithm takes an array A, and range i..j in that array, and a split value s, and moves around elements of A in i..j so that everything less than s is on the left side, and everything >= s is on the right side. Additionally, it needs to tell us where the boundary between the "left" and right "partitions" is, so it returns an index k, which is the index of the last element in the left-hand partition.

k <-- partition(A,i,j,s)
      while(true)
      {
        while(A[i] < s) ++i;
        while(j >= i && A[j] >= s) --j;
        if (j > i)
          swap(A[i],A[j]);
        else
          break;
      }
      return j;

Without thinking too hard, you should see that this is a Θ(n) algorithm, where n is the size of the array range i..j. At least if we assume that swapping and comparing elements of A takes constant time.

Quicksort

Using partition, we get a new divide an conquer sorting algorithm called quicksort. The idea is pretty simple: use partition to split the array into two ranges, recursively sort each range and then you're done. The only problem is this: what should we use for a split value? The mose basic quicksort algorithm simply uses the first element in the range as a split value, i.e. A[i]. The idea is that if the input is random, the first element is just as likely to be a good split value as any other.

So quicksort is

quicksort(A,i,j)

   1) call partition on A and the range i..j using the first element of the range as the split value (Deal with empty partition! as per class discussion)
   2) recursively sort the left range
   3) recursively sort the right range

In the best case, our split value will always partition the array into two equal sized pieces. This gives a recurrence relation of

T(n) = 2 T(n/2) + Θ(n)

where n is the size of the range we're sorting. Using the master method, this gives T_B(n) = Θ(n lg n). In the worst case, our split value will always partition the array into pieces of size 1 and n-1. This gives a recurrence relation of

T(n) = T(n-1) + Θ(n)

where n is the size of the range we're sorting. As we discussed in class, the master method doesn't apply here. So we simply applied the recurrence over and over until we saw a pattern and deduced that T_W(n) = Θ(n^2).