June 1, 1995


David Eck
Department of Mathematics and Computer Science
Hobart and William Smith Colleges
Geneva, NY 14456   USA
E-mail:  eck@hws.edu
WWW:     http://hws3.hws.edu:9000/eck/index.html

xSortLab is a program for learning about and experimenting with five
sorting algorithms:  bubble sort, selection sort, insertion sort,
merge sort and quicksort.  The program has two modes of operation,
visual and timed.  In visual mode, sixteen bars are sorted,
step-by-step, according to size.  In timed mode, lists of numbers
are sorted and the computer reports how long the sort took.

The program is easy to use; instructions are given below.

I wrote this program, and several others, for use with my
introductory computer science textbook:  _The Most Complex Machine:
A Survey of Computers and Computing_ (AK Peters Ltd, Wellesley, MA,
ISBN number  1-56881-054-7), to be published in July of 1995.  You
should find an order form for this book in the folder containing
the program (just in case you are interested).  You can find
information about the book and other programs on the World Wide Web
at this URL:
                  http://math.hws.edu/TMCM.html

COPYRIGHT RESTRICTIONS:  xSortLab  can be freely distributed for
private, non-commercial use.  I stipulate, however, that this
material should not be adopted for use in a course unless the book
_The Most Complex Machine_ is also adopted.  This material can be
included on inexpensive CD-ROM shareware collections.  It can be
made available for downloading from FTP sites and on-line services,
provided that no charge is made beyond such basic charges as
connect time and membership fee.

------------------------------------------------------------------------

Using xSortLab:
--------------

xSortLab has two windows.  The "Sort Window" is used, along with the
menus, for overall control of the program.  The Sort Window is visible
when the program first starts up.  The "Log Window" displays statistics
on sorts done by the program.  It is initially behind the Sort Window.
There are commands in the File Menu for printing the data in the Log
Window to a file and for saving the data to a file.

My recommended method for using xSortLab is to

    1) Start it up, and choose a sorting method from the Method
       Menu.  You will see 16 bars lined up in random order, waiting
       to be sorted.

    2) Click repeatedly on the Next button (or press Command-;) to
       work through the sort one step at a time.  A message describing
       each step will be displayed at the bottom of the window.  The
       object here is to understand exactly how the sort works.  The
       New Sort button can be used to randomize the order of the bars
       and start over.

    3) Then, try the Go button to let the computer do the sort
       automatically, while you watch.  The object here is to get
       a better overall view of the process.  This automatic sorting
       can be done at two speeds.  You can control the speed by
       selecting either "Visual/Fast" or "Visual/Slow" from the
       Speed Menu.

    4) Use the other two entries in the Speed Menu -- Timed/Uninterruptable
       and Timed/Interruptable -- to gather statistics about the sort.
       The statistics are reported in the Log Window.  The Timed/Interruptable
       speed is useful for counting comparison and copy operations; it
       also reports how long the sorting took, but most of this time is
       overhead, so it should not be taken too seriously.  The
       Timed/Uniterruptable sort reports only how long the process took.
       This is the actual processing time required by your computer to
       do the sorting.  A Timed/Uniterruptable sort is, in fact,
       uninterruptable, except by aborting the program with Command-
       Option-Escape or by restarting the computer.

Notes: 

   -- Time is measured in "ticks".  Each tick is equal to 1/60 second.
      At computer speeds, this is a lot of time, and you will find that
      the time reported for sorting a single small array is zero.  To get
      a more accurate time, you should sort a large number of arrays of
      the same size, and divide by the number of arrays.  When you use
      the Timed/Interruptable or Timed/Uninterruptable sorting procedure,
      two input boxes appear where you can type in the number of
      arrays as well as the size of each array.  (Keeping track of
      multiple arrays does add a certain amount of overhead to the
      processing time, but except for very large numbers of small
      arrays, it is negligible.  If you really want to be accurate,
      you could try measuring the overhead by "sorting" a large number
      of arrays of size 1.)

   -- The Method Menu is used to select one of five sorting methods.
      If you select a new method while a "visual" sort is in progress,
      the sort in progress will continue using the old method.  The 
      new method will come into effect the next time you start a 
      new sort.  The sort method that is actually in use at any given time
      is displayed in the title bar of the Sort Window.

   -- The Control Menu contains commands that duplicate the functions of
      the buttons in the Sort Window.  It also has commands for bringing
      the Sort Window and the Log Window to the front and for clearing
      the Log Window.

   -- The program's default memory allocation is set so that it can operate
      on up to 200,000 items.  However, it can actually operate on up to
      1,000,000 items if you increase the memory allocation.