4005-800-70 Theory of Computer Algorithms
Sorting Algorithm Running Times

Introduction
Source Code
Test01
Measure
Fit

These programs measure various sorting algorithms' running times as a function of the input array length. The sorting algorithm is specified on the command line. The manner in which data is arranged in the input array is also specified on the command line. The programs print out and plot the experimental data. The plots can be stored in image files (PostScript or PNG) using the "File-Save" menu option. The programs are available in the Computer Science Course Library.

The programs use one critical class, class edu.rit.util.CpuStopwatch, to measure the sorting algorithm's running time. This class uses native methods written in C. Consequently, you have to do some extra setup when you run these programs. See the Computer Science Course Library for further information.

Package edu.rit.thcompalg.sort	Package edu.rit.numeric.stat	Package edu.rit.util
Interface IntFill Interface IntSort   Class AscendingFill Class DescendingFill Class RandomFill   Class InsertionSort Class NullSort Class QuickSort   Class Test01 Class Measure Class Fit	Class CurveFit Class AsymptoticCurveFit Class IncompleteGamma	Class CpuStopwatch

Class Test01 is a main program that measures the running time of a sorting algorithm on input arrays of varying lengths. The sorting algorithm is specified on the command line. The algorithm for filling the arrays with data is specified on the command line.

Usage: java edu.rit.thcompalg.sort.Test01 sortclass fillclass minx maxx div miny maxy na rt seed
sortclass = Fully-qualified name of the array sorting class
fillclass = Fully-qualified name of the array filling class
minx = Smallest array length to plot (exponent of 10)
maxx = Largest array length to plot (exponent of 10)
div = Array length divisions per decade
miny = Smallest time to plot (exponent of 10)
maxy = Largest time to plot (exponent of 10)
na = Number of arrays measured for each array length
rt = Running time for each array (seconds)
seed = Random seed

The sortclass argument must be the fully-qualified name of a class that implements interface IntSort, such as:
edu.rit.thcompalg.sort.InsertionSort
edu.rit.thcompalg.sort.QuickSort

The fillclass argument must be the fully-qualified name of a class that implements interface IntFill, such as:
edu.rit.thcompalg.sort.AscendingFill
edu.rit.thcompalg.sort.DescendingFill
edu.rit.thcompalg.sort.RandomFill

Insertion sort, input data in ascending order:

java edu.rit.thcompalg.sort.Test01 edu.rit.thcompalg.sort.InsertionSort edu.rit.thcompalg.sort.AscendingFill 1 3 10 -7 -2 1 5 142857

Insertion sort, input data in descending order:

java edu.rit.thcompalg.sort.Test01 edu.rit.thcompalg.sort.InsertionSort edu.rit.thcompalg.sort.DescendingFill 1 3 10 -7 -2 1 5 142857

Insertion sort, input data in random order:

java edu.rit.thcompalg.sort.Test01 edu.rit.thcompalg.sort.InsertionSort edu.rit.thcompalg.sort.RandomFill 1 3 10 -7 -2 3 5 142857

Quicksort, input data in ascending order:

java edu.rit.thcompalg.sort.Test01 edu.rit.thcompalg.sort.QuickSort edu.rit.thcompalg.sort.AscendingFill 1 3 10 -7 -2 1 5 142857

Quicksort, input data in descending order:

java edu.rit.thcompalg.sort.Test01 edu.rit.thcompalg.sort.QuickSort edu.rit.thcompalg.sort.DescendingFill 1 3 10 -7 -2 1 5 142857

Quicksort, input data in random order:

java edu.rit.thcompalg.sort.Test01 edu.rit.thcompalg.sort.QuickSort edu.rit.thcompalg.sort.RandomFill 1 3 10 -7 -2 3 5 142857

Class Measure is a main program that measures the running time of a sorting algorithm on input arrays of varying lengths. The sorting algorithm is specified on the command line. The algorithm for filling the arrays with data is specified on the command line. The measurements are recorded in an instance of class edu.rit.numeric.ListXYZSeries, with the X value being the input array size, the Y value being the sorting algorithm's measured running time in seconds, and the Z value being the standard deviation of the measurement error. The object containing the series of measurements is stored in a file specified on the command line using object serialization.

Usage: java edu.rit.thcompalg.sort.Test02 sortclass fillclass minx maxx div na tt seed file
sortclass = Fully-qualified name of the array sorting class
fillclass = Fully-qualified name of the array filling class
minx = Smallest array length to measure (exponent of 10)
maxx = Largest array length to measure (exponent of 10)
div = Array length divisions per decade
na = Number of arrays measured for each array length
tt = Total time for each measurement (seconds)
seed = Random seed
file = File name in which to store measurements

The command line argument tt gives the total time over which to perform each measurement. Each input array is filled in and sorted repeatedly until the measured total time for all the repetitions is tt or greater. Then the time to sort the array once is the measured total time divided by the number of repetitions.

Insertion sort, input data in random order:

java edu.rit.thcompalg.sort.Measure edu.rit.thcompalg.sort.InsertionSort edu.rit.thcompalg.sort.RandomFill 1 3 10 3 2 142857 isrf.ser

Quicksort, input data in random order:

java edu.rit.thcompalg.sort.Measure edu.rit.thcompalg.sort.QuickSort edu.rit.thcompalg.sort.RandomFill 1 3 10 3 2 142857 qsrf.ser

Class Fit is a main program that fits the measured running time of a sorting algorithm to a theoretical model. The measurements are recorded in an instance of class edu.rit.numeric.ListXYZSeries, with the X value being the input array size, the Y value being the sorting algorithm's measured running time in seconds, and the Z value being the standard deviation of the measurement error. The object containing the series of measurements is read from a file specified on the command line using object serialization. The program fits the measured running times to an asymptotic function specified on the command line. The asymptotic function is specified using the syntax defined in class edu.rit.thcompalg.asymptotic.AsymptoticFunction (see "Asymptotic Behavior of Functions" for further information). The program prints out the least squares curve fit of the measurements to the asymptotic function, as well as the goodness of fit using the chi-square statistic. The program also plots the measured data points and the fitted curve. The program can plot more than one set of measurements on the same plot.

Usage: java edu.rit.thcompalg.sort.Fit file functionspec [ file functionspec . . . ]
file = File name from which to read measurements
functionspec = Asymptotic function specification

For further information, see "A Brief Introduction to Curve Fitting" (PDF, 80,602 bytes).

Example: Fit the insertion sort measurements in file "isrf.ser" to a model of the form O(n²), fit the quicksort measurements in file "qsrf.ser" to a model of the form O(n lg n), and plot the results on the same graph (red = insertion sort, orange = quicksort).

java edu.rit.thcompalg.sort.Fit isrf.ser "n ^ 2" qsrf.ser "n lg n"

Data Communications and Networks II 4003-541-70/4005-741-70 Spring Quarter 2006

Course Page

Alan Kaminsky • Department of Computer Science • Rochester Institute of Technology • 4486 + 2220 = 6706

Home Page

Copyright © 2004 Alan Kaminsky. All rights reserved. Last updated 14-Jan-2004. Please send comments to ark­@­cs.rit.edu.