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:
  1. Remove the first element from the list. Call it the "pivot."
  2. 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.
  3. Quicksort each of these two new lists.
  4. 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).

  1. Remove the first element, 4, from the list and call it the pivot.
  2. Separate the remainder of the list into the two lists (2 1 3 2) and (7 8 9 6 8 4).
  3. Quicksort the two lists to get (1 2 2 3) and (4 6 7 8 8 9).
  4. 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).