CMSC-341 Data Structures

Fall 1998 Project 2

 

  1. Introduction
  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.

  3. Project Grading
  4. 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

     

  5. The Project
  6. 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:

    1. array.h -- definition of the Array class template
    2. array.C -- the implementation of the Array class template
    3. comparator.h -- definition of the Comparator class template.
    4. comparator.C -- implementation of the Comparator class template
    5. demonstrate.h - definition and of the function template DemonstrateSorting()
    6. demonstrate.C -- implementation of DemonstrateSorting()
    7. measure.h -- declaration of MeasureSorts()
    8. measure.C -- implementation of MeasureSorts()
    9. sorting.h -- function template definitions the sorting functions
    10. sorting.C -- sorting function implementations
    11. project2.results -- the output file

    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.

  7. Summary of Tasks
  8. Input Data
  9. 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.

     

  10. Results
  11. 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.

     

  12. Submitting Results
  13. 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.

     

  14. Compiling the Project
  15. 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.

  16. Project Report
  17. 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


    Demonstration that sorting routines work for Array<int>
    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 990 
    
    
    Demonstration 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.434 
    
    
    Demonstration 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; }