The xSortLab Applet
SORTING a list of items -- that is, arranging the items into increasing or decreasing order -- is a common operation. It is also the most common example in the "analysis of algorithms," which is the study of computational procedures and of the amount of time and memory that they require. The xSortLab applet knows five different sorting methods. It has a visual sorting mode, where you can watch as sixteen bars are sorted into increasing order. And it has a timed mode, where you can measure the time it takes to sort a large number of items. The applet is easy to use (but you probably won't quite get the point of it unless you already know something about sorting). More information about the applet can be found below.
This applet was originally written by David Eck for use with his introductory computer science textbook The Most Complex Machine. However, it can also be used on its own.
For a list of other applets and for lab worksheets that use the applets, see the index page.
Visual Sort Mode
The xSortLab applet can display three different panels: a panel for "Visual Sort," a panel for "Timed Sort," and a "Log" panel. There is a pop-up menu at the top of the applet that can be used to switch among the three panels. (Note: Changing panels while a sort is in progress will abort the sort.)
The applet starts in "Visual Sort" mode, in which 16 bars are sorted step-by-step using one of the sorting algorithms Bubble Sort, Selection Sort, Insertion Sort, Merge Sort, or QuickSort. Below the area where the bars are displayed are two message areas, which display a running commentary when a sort is in progress. The lower message area displays a detailed comment on each step in the sort. The upper area displays more general messages about major phases in the sort. (The lower message area is not used when the sort is being run at "Fast" speed.)
To the right of the bars is a column of controls. The first of these is a pop-up menu, that can be used to select the sorting method. (Again, doing this in the middle of a sort will abort the current sort.) Next comes a checkbox that can be used to determine whether or not the sort is done at "Fast" speed. When this box is not checked, you get to see a cute animation of moving bars; also, a longer delay is inserted between steps when you run the sort with the "Go" button. The "Go" and "Step" buttons are used for executing a sort. The "Start Again" button gives you a new, randomized list of 16 bars.
Two basic operations are used in sorting: comparing two items to see which is bigger and copying an item from one place to another. The number of comparisons and the number of copies used in the current sort are displayed below the controls.
Timed Sort Mode
If you switch to the "Timed Sort" panel, you'll see a large message area, with some instructions. This panel is used to obtain statistics about the running times of various running algorithms. The interesting question is how the running time depends on the number of items being sorted. There is a text-input box at the top of the panel where you can specify the size of the array that is to be sorted. You can also specify the number of arrays to be sorted. The point is that a small array takes so little time to sort that the time cannot be measured accurately. So, you should sort a number of arrays, all of the same size. You can measure the total time it takes to sort them all. The time required to sort one array can be obtained by dividing the total time by the number of arrays. You probably want to adjust the number of arrays so that the total time is at least a couple of seconds.
Note: Your computer must have enough memory to store all the numbers you want to sort. (If you are running the applet at all, you probably have enough memory to work with at least one million items.) If you ask for more numbers than you have room for, you should just a message telling you that you don't have enough memory. However, most systems that I have tried this on have crashed. This is a bug. You are warned. Stick to a reasonable number of items.
At the bottom of the panel are a pop-up menu that you can use to choose the sort method and a "Go" button that you can click to start the sort. (This changes to "Abort" while a sort is in progress.)
When you begin a sort, the first thing the computer does is to fill up the arrays with random numbers. If there are a lot of numbers, this will take a noticeable amount of time. Then, the computer begins to sort. As the sorting operation proceeds, statistics are displayed about twice per second. The statistics include the number of comparison and copy operations that have been performed, the number of arrays that have been sorted so far, the elapsed time since the computer began sorting, and the approximate compute time that the computer has devoted to sorting. The compute time is not the same as the elapsed time, since the applet is doing other things besides sorting (such as redrawing the screen). The applet tries to use 80% of the time for sorting, and to leave 20% for other tasks. The applet can measure the 20% of its time that it gives away voluntarily, but if other things are going on in your computer, it might lose some other time that it can't measure. This is why the measured compute time is approximate. So, you should not try to run a timed sort in the background! Just sit and watch -- or go get a coffee.
The Log
Every time a sort completes successfully, statistics about that sort are written to a log. For a visual sort, the number of copies and the number of comparisons are recorded. For a timed sort, all the statistics that are displayed in the "Timed Sort" panel are written to the log. You can view this log by selecting the "Log" option from the pop-up menu at the top of the applet.
The Log panel has buttons for clearing the log and for saving it to a file. However, it is likely that your browser will not permit you to save the log. Unfortunately, the applet has no provision for printing the log at this time. You might try using copy-and-paste to copy the data from the log to another program from which you can copy or print it.
David Eck (eck@hws.edu), August 1997