Complexity lab assignment

Purpose:

The purpose of this lab is to investigate the properties of various sorting algorthms, and to determine how efficiency of algorithms is measured. We will be using an applet called xSort to run some experiments. Some notes by the author of xSort are available here. They provide some very useful information about the various kinds of sorts we will do.

You will also probably want a spreadsheet such as Excel for doing some charting and simple computations.

Timing sorts (from online notes, Exk, The Most Complex Machine)

Now that you understand how some sorting algorithms work, the next step is to investigate how efficiently lists of items can be sorted. In this part of the lab, you will use the "Timed Sort" mode of the xSortLab applet. Select this mode from the pop-up menu at the very top of the applet (which you launched above). In the Timed Sort mode, the computer works behind the scene to sort arrays of randomly generated numbers. An array is just a numbered list of items; the size of the array refers to the number of items in the list. As the computer sorts the arrays, it displays various statistics in the large green area in the center of the applet. The statistics are updated about twice every second.

At the top of the applet, there is a text-input box where you can type the size of the arrays to be sorted. There is also a box where you can type the number of arrays to sort. The computer will create the number of arrays that you specify. Each array will have the size that you specify. The computer fills all the arrays with random numbers. Then it sorts each array, one after the other. The reason for using more than one array is that for small arrays, the time it takes to sort a single array is a tiny fraction of a second. Since xSortLab can't measure very small time intervals accurately, the only way to get an accurate idea of the sorting time for small arrays is to sort a lot of arrays, measure the time it takes to sort them all, and divide the total time by the number of arrays. For larger array sizes, using more than one array is not so important (but it might still give you a more accurate measurement).

At the bottom of the applet, you will see a pop-up menu that can be used to select the sorting algorithm that is to be applied to the arrays. There is a also a "Start Sorting" button. Once you have selected the sorting method and set up the size of the arrays and the number of arrays, click on the "Start Sorting" button to begin. (If you are dealing with a large number of items, there will be a noticeable time interval before the computer starts sorting. The pause occurs while the computer is filling the arrays with random numbers.) When you click the "Start Sorting" button, the name of the button will change to "Abort." Use the "Abort" button if you want to terminate the sorting operation before the computer finishes.

The xSortLab applet displays several different statistics about the sorts its does. For this lab, you will only need the "Approximate Compute Time." This is different from the "Elapsed Time" because as it is computing the applet allows some time -- about 20% of the time available -- for other --> -- activities, such as redrawing the screen. It is only the time actually devoted to sorting that you are interested in. The compute time is approximate because it is possible for your browser or other programs on your computer to steal time from the applet. The applet might incorrectly include this time in the compute time it reports. However, if you are not doing anything else with your computer at the same time that the applet is sorting, then the reported time should be reasonably accurate. The computer measures time in units of 1/1000 of a second, and this also limits the accuracy of measurements. In particular, you should not try to use measurements that are less than, say, 0.1 seconds. Ideally, you should adjust the number of arrays so that the compute time is at least a couple of seconds.

Your task in this part of the lab is to gather timing statistics about each of the five available sorting methods. You want to measure how long it takes each method to sort arrays of various sizes. You will need this data for the exercises at the end of the lab, so you should record the data as you work. For each experiment that you do, record the array size, the number of arrays, and the compute time that is reported by the applet.

You should apply each method to arrays of at least the following sizes: 5, 10, 100, and 10000. In addition, you should apply Merge Sort and QuickSort to arrays of size 100000. For the largest array sizes, it will be good enough to sort a single array. For the smaller array sizes, you will have to set the number of arrays to be rather large to get a decent measurement. Don't be afraid to sort 10000, or even 100000, arrays of size 5. Use your judgement. (If the arrays require more memory than your computer has available, you should just get an error message. However, this has crashed many systems that I tried it on.)

Your mission:

Answer the following questions:

© Andy Harris
Indiana University / Purdue University, Indianapolis
email: aharris@cs.iupui.edu
homepage: http://www.cs.iupui.edu/~aharris