Computer Science Fundamentals (CS153 2004S)
[Skip to Body]
Primary:
[Front Door]
[Current]
[Glance]

[Honesty]
[Instructions]
[Links]
[Search]
Groupings:
[EBoards]
[Examples]
[Exams]
[Handouts]
[Homework]
[Labs]
[Outlines]
[Readings]
[Reference]
Misc:
[Experiments in Java]
[Java API]
[Scheme Reference]
[Scheme Report]
[CS153 2003S]
[CS151 2003F]
[CS152 2000F]
[SamR]
Summary: We consider Quicksort, another divideandconquer algorithm for sorting. Unlike merge sort, which is guaranteed to be in O(nlog_{2}n), Quicksort is only likely to have running time of O(nlog_{2}n).
Contents:
As our lists and arrays get increasingly large, it becomse more and more important to use the fastest possible sorting algorithm. As we've seen in our study of binary search and merge sort, one algorithm design strategy that often helps in the creation of fast algorithms is that of divideandconquer, in which you divide the input into two halves and then work on each or both halves.
In the merge sort algorithm, we divided the list or array in a
fairly simple way; we just made sure each half had about the same number
of elements. However, there are certainly other ways we could divide
our collection of elements. For example, we might divide them into
the smaller
elements and the larger
elements.
That idea is at the core of Quicksort.
How does splitting the input into large and small values help? If we sort the small values and the large values, we can simply join the sorted collections. For lists, we might write something like
(define quicksort (lambda (lst) (if (or (null? lst) (null? (cdr lst))) lst (let ((small ...) (large ...)) (append (quicksort small) (quicksort large))))))
How do we go about identifying the large
and the small
values? That's the key problem in quicksort. You may find the answer
somewhat surprising: we pick some value (which we call the pivot)
from the collection and assume that it's the average value. That is,
everything smaller than the pivot is small
and everything larger
than the pivot is large
.
How do we select the pivot? It turns out that it works fine to select it randomly. On average, you'll select a pretty good pivot.
One potential problem is that you may never shrink the parameter
for recursive calls (as is a requirement for recursive design). For
example, if lst
contains multiple copies of one value
(and only multiple copies of that value), either small
or large
will always contain the same sequence of values.
Hence, we really need to split lst
into three parts:
things smaller than the pivot, things equal to the pivot, and
things greater than the pivot. We only recurse on the smaller and
greater sublists.
For our full implementation, we need to consider not just the threeway split described above, but also appropriate generalization (e.g., taking the procedure to compare values as a parameter). We use two comparators so that we can split in three parts.
;;; Procedure: ;;; quicksort ;;; Parameters: ;;; lst, a list to sort ;;; comesbefore?, a binary predicate that compares values. ;;; same?, a binary predicate that compares values. ;;; Purpose: ;;; Sort stuff. ;;; Produces: ;;; sortedstuff, a sorted list ;;; Preconditions: ;;; comesbefore? can be applied to any two elements of stuff. ;;; comesbefore? represents a transitive operation. ;;; same? can be applied to any two elements of stuff. ;;; For any two values, a and b, exactly one of the following holds: ;;; 1. (comesbefore? a b) ;;; 2. (same? a b) ;;; 3. (comesbefore? b a) ;;; Postconditions: ;;; sortedstuff is sorted. That is, any element may precede the ;;; subsequent element. In Scheme, we'd say that ;;; ((disjunction comesbefore? same?) (listref sorted i) ;;; (listref sorted (+ i 1))) ;;; sortedstuff is a permutation of stuff. ;;; Does not affect stuff. ;;; sortedstuff may share cons cells with stuff. ;;; Examples: ;;; To sort values, a list of numbers, in increasing order. ;;; (quicksort values < =) ;;; To sort values, a list of numbers, in decreasing order. ;;; (quicksort values > =) ;;; To sort people, a list of (lastname firstname phonenumber) ;;; triplets, by first name ;;; (quicksort people ;;; (lambda (person1 person2) ;;; (string<? (cadr person1) (cadr person2))) ;;; (lambda (person1 person2) ;;; (string=? (cadr person1) (cadr person2)))) (define quicksort (lambda (lst comesbefore? same?) ; If there are only zero or one elements in the list, ; the list is already sorted. (if (or (null? lst) (null? (cdr lst))) lst ; Otherwise, ; Identify a pivot. ; Build three lists (smaller, same, greater). ; Sort smaller and greater. ; Join the sorted parts. (let* ((pivot (selectpivot lst)) (smaller (select (rightsection comesbefore? pivot) lst)) (larger (select (leftsection comesbefore? pivot) lst)) (same (select (leftsection same? pivot) lst))) (append (quicksort smaller comesbefore? same?) same (quicksort larger comesbefore? same?))))))
You'll have an opportunity to explore further details in the lab.
It is also possible to Quicksort an array in place
. We'll
return to this technique later.
[Skip to Body]
Primary:
[Front Door]
[Current]
[Glance]

[Honesty]
[Instructions]
[Links]
[Search]
Groupings:
[EBoards]
[Examples]
[Exams]
[Handouts]
[Homework]
[Labs]
[Outlines]
[Readings]
[Reference]
Misc:
[Experiments in Java]
[Java API]
[Scheme Reference]
[Scheme Report]
[CS153 2003S]
[CS151 2003F]
[CS152 2000F]
[SamR]
Disclaimer:
I usually create these pages on the fly
, which means that I rarely
proofread them and they may contain bad grammar and incorrect details.
It also means that I tend to update them regularly (see the history for
more details). Feel free to contact me with any suggestions for changes.
This document was generated by
Siteweaver on Fri May 7 09:44:38 2004.
The source to the document was last modified on Fri Feb 27 09:36:23 2004.
This document may be found at http://www.cs.grinnell.edu/~rebelsky/Courses/CS153/2004S/Readings/quicksort.html
.
You may wish to validate this document's HTML ; ; Check with Bobby
Samuel A. Rebelsky, rebelsky@grinnell.edu