CSC 8310 Linguistics of Programming Languages
Dr. David Matuszek,
david.l.matuszek@lmco.com
Fall 1998, Villanova University
Scheme Assignment
Your assignment is to write a Quicksort program in Scheme. Write your
program to sort an arbitrarily long list of integers.
When you test your program, be sure to include some duplicate
integers; not every number in the list should be unique.
In case you are not familiar with the Quicksort algorithm:
Quicksort:
 Remove the first element from the list. Call it the "pivot."
 Separate the remaining elements into two new lists: one
containing those elements smaller than the pivot,
and one containing elements larger than or equal to
the pivot.
 Quicksort each of these two new lists.
 Append the two lists, with the pivot in between, to create
the final result list.

For example, suppose the list is
(4 2 7 1 8 3 9 6 8 4 2).
 Remove the first element, 4, from the list and call
it the pivot.
 Separate the remainder of the list into the two lists
(2 1 3 2) and
(7 8 9 6 8 4).
 Quicksort the two lists to get (1 2 2 3)
and (4 6 7 8 8 9).
 Combine the list and the pivot in the order
(1 2 2 3), 4, (4 6 7 8 8 9)
to get the final list
(1 2 2 3 4 4 6 7 8 8 9).
This algorithm translates fairly directly into Scheme.
There are a few details left out from the above description, the most
important of which is that you don't recursively call Quicksort if
the list is empty or has only one element (because such lists are
already sorted).