Table of Contents   |   Proof Methods   |   Glossary

Proofs of Correctness

(Algorithm from Cormen, et al. pg. 154)

Quicksort ( A, p, r)
  1. if p < r
  2.      then q := Partition(A, p, r)
  3.              Quicksort (A, p, q)
  4.              Quicksort (A, q+1, r)

Partition (A, p, r)

  1. x := A[p]
  2. i := p - 1
  3. j := r + 1
  4. while True
  5.    do repeat  j := j - 1
  6.           until A[j] <= x
  7.         repeat  i := i + 1
  8.           until A[i] >= x
  9.       if i < j
  10.         then exchange A[i] <-> A[j]
  11.         else return j  

1) Prove that the Quicksort Algorithm is correct.

2) Quicksort sorts lists of length 1 correctly.

3) The inductive hypothesis is that Q can correctly sort lists of length k for all k >+ 1 and <= n

4) Prove that Quicksort works correctly on lists of length n + 1.

The algorithm begins by dividing a list of length n + 1 into two lists of length q and (n + 1 - q).  The list of length q contains all the numbers that are < A[p].  The list of length (n + 1 - q) contains all the numbers > A[p].

Since q < n + 1, Quicksort (q) must sort correctly.

n + 1 - q < n + 1 so Quicksort (n + 1 - q)  must sort correctly.

The final step of the algorithm is to combine the two (smaller) correctly sorted lists (Remember, one contains all numbers < A[p], the other contains all numbers > A[p] in size order), returning a correctly sorted list.

This is an applet that will demonstrate Quicksort on a list of 10 items.  If you open the Java Console in your browser and click on the grey square to run the applet, you will be able to see a trace of what the algorithm is doing as it sorts.  This is similar to the trace that we wrote out in the Factorial proof.  You can use this trace to augment your understanding of the algorithm and its correctness.

5) Therefore the Quicksort Algorithm is correct.

Prove that the basic Bubblesort algorithm is correct.

Back to:

Top of Page   |   Table of Contents   |   Proof Methods   |   Glossary1