CMSC-341 Data Structures
Fall 1998 Project 2
The purpose of this project is to introduce you to programming with templates, the use of a facilitator class, to formatted output and to analyzing the performance properties of different algorithms.
The basic idea of the project is to modify three sorting functions (selection, insert and quick) to use a comparator class for comparison and swap management.
To show that the same sorting function can be used to sort Arrays of various types, we use them to sort small Arrays of int, double and complex. Output of the sorts will be Arrays in ascending order.
Secondly, we perform measurements on the number of swaps and the number of comparisons used by each sorting function for int Arrays of various sizes. We use only Arrays of int for these measurements. We compare the actual performance on randomly generated data to O (n2) by computing K1 = C / n2 and K1 = S / n2, where C and S are the number of compares and swaps respectively.
Finally, we compare the actual performance on randomly generated data to O(n lg(n)) by computing K1 = C / n lg(n) and K2 = S / n lg(n) where C and S are the number of compares and s waps respectively.
Computational Note: In the expression above, lg(n) means log of n, base 2. The C++ math library provides the function "log (x)" which returns the log of x, base 10. To convert from log10 x to log2 x, note the following :log2x = log10x / log102.
The project grade will be divided 60% program execution, 20% programming style and 20% for the project report.
A grading sheet will be provided as with project-1.
The project is due dates are
Sunday Oct. 25 1998 for section 101
Tuesday Oct 27 1998 for section 201
Projects submitted at least 24-hours prior to midnight of the
due date will receive a 5-point bonus. Projects less than 24 hours
late will be assessed a 5-point penalty. Projects between 24 and 48
hours late will be assessed a 10-point penalty. No project will be
accepted more than 48 hours late
The files Makefile, project2.C, project2_util.C, complex.h, complex.C and misc.C are to be copied from /afs/umbc.edu/users/d/e/dennis/pub/cs341/proj2.
You will produce the following files:
The files project2.C (which contains the main function) and the Makefile are to be used without changes. project2_util.C (which contains miscellaneous utility functions may be changed at your own risk). The file misc.C contains a template version an d a non-template (Complex) version of RandomizeArray. Instructions are in misc.C. Note that misc.C is not part of the project, it just provides you with the RandomizeArray functions to use.
Data for the sorting routines is to be pseudo-randomly generated. An overloaded pseudo-random generator function RandomizeArray is provided in misc.C. For the "Demonstrate" section the seed value should be 1 (so we all get the same data). For the "Measure" section, the seed should be derived from the time of day. See misc.C for more on this.
Results are to be submitted in a file names project2.results. To produce the results file, execute your program by typing project2 > project2.results.
NOTE : the "DemonstrateSorts" results should be produced very quickly. After that, there can be a long wait (1-2 minutes) for the first results from MeasureSorts. That's normal. However, there should not be much time between section (1) and sections (2) and (3) of the "Measurement Results". You should keep an array of the results from section (1) for use in section (2) and (3) to avoid recomputing the data.
A sample results file is attached. It is not necessary to exactly duplicate the format, but it must be reasonably close. In particular, there must be data for every size shown, the K values must be in scientific notation, etc.
You should submit your project using the "submit" procedure, in the
same manner as project1. (It should be working).
Please try to avoid multiple submissions as much as possible. If you do make multiple submissions, each su
bmission will overwrite the earlier submissions. The last submission will be graded. Also use "submit" for your project report by the due date. The project is complete when both the code and the report have been submitted.
A Makefile has been provided to help you in compiling your project and in cleaning up your directory. In order for the Makefile to work, you must name your files precisely as shown in section 4.
Note also, that compiling your project will result in the creation of a temporary directory called ii_files, which will contain files with the extension "ii". These are used by the compiler to handle templates.
Write a one- three page project report that discusses the project and the results of your measurements. The report should be submitted in the file named "project2.report". At a minimum, your report should answer these questions --
Methodology
Conclusions:
11 Sample Results File
Your output for the Demonstration should match this exactly
Your output for the number of comparisons for the Measurement
should also match exactly
before sorting, Array = 41 454 834 335 565 1 187 990 750 366 351 573 132 64 950 153 584 216 806 140 after selectionSort, array = 1 41 64 132 140 153 187 216 335 351 366 454 565 573 584 750 806 834 950 990 after insertionSort, array = 1 41 64 132 140 153 187 216 335 351 366 454 565 573 584 750 806 834 950 990 after quickSort, array = 1 41 64 132 140 153 187 216 335 351 366 454 565 573 584 750 806 834 950 990Demonstration that sorting routines work for Array<double>
before sorting, Array = 41.6303 454.492 834.817 335.986 565.489 1.76691 187.59 990.434 750.497 366.274 after selectionSort, array = 1.76691 41.6303 187.59 335.986 366.274 454.492 565.489 750.497 834.817 990.434 after insertionSort, array = 1.76691 41.6303 187.59 335.986 366.274 454.492 565.489 750.497 834.817 990.434 after quickSort, array = 1.76691 41.6303 187.59 335.986 366.274 454.492 565.489 750.497 834.817 990.434Demonstration that sorting routines work for Array<Complex>
before sorting, Array = (41.6303 + 454.492i) (834.817 + 335.986i) (565.489 + 1.76691i . . . fter selectionSort, array = 41.6303 + 454.492i) (565.489 + 1.76691i) (750.497 + 366.274i) . . . fter insertionSort, array = 41.6303 + 454.492i) (565.489 + 1.76691i) (750.497 + 366.274i). . . after quickSort, array = 41.6303 + 454.492i) (565.489 + 1.76691i) (750.497 + 366.274i) . . . --------------------------------------------- Measurement Results --------------------------------------------- (1) Each entry is number of (compares, swaps) Size selectionSort insertionSort quickSort 10 ( 45, 4) ( 28, 19) ( 40, 11) 510 ( 129795, 502) ( 68561, 68052) ( 9295, 1269) 1010 ( 509545, 998) ( 252070, 251061) ( 21356, 2752) 1510 ( ) ( ) ( ) 2010 ( ) ( ) ( ) 2510 ( ) ( ) ( ) 3010 ( etc. ) ( etc. ) ( etc, ) 3510 ( ) ( ) ( ) 4010 ( ) ( ) ( ) 4510 ( ) ( ) ( ) 5010 ( ) ( ) ( ) (2) Each entry is K for (compares, swaps) assuming number of compares or swaps = K * (size * size) Size selectionSort insertionSort quickSort 10 (4.50e-01,4.00e-02) (2.80e-01,1.90e-01) (4.00e-01,1.10e-01) 510 (4.99e-01,1.93e-03) (2.64e-01,2.62e-01) (3.57e-02,4.88e-03) 1010 (5.00e-01,9.78e-04) (2.47e-01,2.46e-01) (2.09e-02,2.70e-03) 1510 ( ) ( ) ( ) 2010 ( ) ( ) ( ) 2510 ( ) ( ) ( ) 3010 ( etc. ) ( etc. ) ( etc, ) 3510 ( ) ( ) ( ) 4010 ( ) ( ) ( ) 4510 ( ) ( ) ( ) 5010 ( ) ( ) ( ) (3) Each entry is K for (compares, swaps) ssuming number of compares or swaps = K * (size * lg(size)) Size selectionSort insertionSort quickSort 10 (1.35e+00,1.20e-01) (8.43e-01, 5.72e-01) (1.20e+00,3.31e-01) 510 (2.83e+01,1.09e-01) (1.49e+01,1.48e+01) (2.03e+00,2.77e-01) 1010 (5.06e+01,9.90e-02) (2.50e+01,2.49e+01) (2.12e+00,2.73e-01) 1510 ( ) ( ) ( ) 2010 ( ) ( ) ( ) 2510 ( ) ( ) ( ) 3010 ( etc. ) ( etc. ) ( etc, ) 3510 ( ) ( ) ( ) 4010 ( ) ( ) ( ) 4510 ( ) ( ) ( ) 5010 ( ) ( ) ( )
Sorting functions for integer Arrays. Note that these functions have been written for clarity and are not necessarily the most efficient versions available. Each sorting function sorts Array instances, in place. Recall that Array instance A indexes the data 1...A.Size(), not 0...A.Size() - 1. void selectionSort (Array& A) int temp; unsigned int largeposition; for (unsigned int top = A.Size(); top > 1; top--) { largeposition = 1; for (unsigned int j = 2; j <= top; j++) { if (A[largeposition] < A[j]) largeposition = j; } if (top != largeposition) { temp = A[top]; A[top] = A[largeposition]; A[largepositon] = temp; } } }
void insertSort (Array& A) { A[0] = -100000; // a really small number for (int P = 2; P <= A.Size(); P++) { for (int j = P; (A[j] < A[j - 1]); j--) { int temp = A[j]; A[j] = A[j -1]; A[j - 1] = temp; } } }
void quickSort (Array& A) { int N = A.Size(); if (N > 1) quicksort (A, 1, N); } void quickSort (Array & A, int low, int high) { if (low >= high) return; int pivotIndex = (low + high) / 2; pivotIndex = partition (A, low, high, pivotIndex); if (low < pivotIndex) quickSort (A, low, pivotIndex - 1); if (pivotIndex < high) quickSort (A, pivotIndex + 1, high); } int partition (Array & A, int low, int high, int pivotIndex) { int temp; if (pivotIndex != low) { temp = A[low]; A[low] ]= A[pivotIndex]; A[pivotIndex] = temp; } piovotIndex = low; low ++; while (low <= high) { if (A[low] <= A[pivotIndex]) ++low; else if (A[high] > A[pivotIndex]) --high; else { temp = A[low]; A[low] = A[high]; A[high] = temp; } } if (high != pivotIndex) { temp = A[pivotIndex]; A[pivotIndex] = A[high]; A[high] = temp; } return high; }