Homework 2

CMP 338: Data Structures & Algorithms
Lehman College, City University of New York
Spring 2022

This Homework Is Due By 11:59 PM on Sunday February 27, 2022

Overview

In this assignment you will be implementing and testing all three sort algorithms: Bubble Sort , Selection Sort , and Insertion Sort .

In additions, you will also be writing a driver to test the search algorithms and you will be measuring the test times of each sort.

You will also be using the TestTimes class that you created for Homework 1 .

Finally, you will be analysing and comparing the performance of the three sort algorithms based on the type of array that was being sorted and the run times you computed.

Details

1. TestTimes zyLab

   You will copy the TestTimes class that you created in Homework 1 to the project you are using for this assignment. Please not that you will also have to re-submit TestTimes.java to zyBooks in the TestTimes zyLab

2. BubbleSort zyLab

   You will write the BubbleSort.java class which will implement the Sort Interface using the Bubble Sort algorithm. The interface may be downloaded from here .

3. SelectionSort zyLab

   You will write the SelectionSort.java class which will implement the Sort Interface using the Selection Sort algorithm. The interface may be downloaded from here .

4. InsertionSort zyLab

   You will write the InsertionSort.java class which will implement the Sort Interface using the Insertion Sort algorithm. The interface may be downloaded from here .

5. SortDriver zyLab

   You will write the SortDriver.java class to test your implementations of the above classes. The SortDriver.java class will implement the SortDriverInterface . The interface may be downloaded from here .

   Please note that, in addition to implementing the SortDriverInterface, you are also required to write your own public static main(String[] args) method in SortDriver.java that performs all of the required tests as specified below.

Required Tests

Definitions:

You will test your three sort implementation on different array types and array sizes. You will test all combinations of sort algorithms with all array types of size 1,000 and 10,000. The SortDriverInterface includes the definitions of two enums:

1. SortDriverInterface.ArrayType

   This enum defines all the possible array types that you will use to test your implementation of the three sorts. The array types are:

   Equal

   The elements in the array are all equal to each other.

   Random

   The elements in the array are randomly generated.

   Increasing

   The elements in the array are arranged in increasing order.

   Decreasing

   The elements in the array are arranged in decreasing order.

   IncreasingAndRandom

   The first 90% of the elements in the array are arranged in increasing order and the last 10% of the elements in the array are randomly generated.

2. SortDriverInterface.SortType

   This enum defines all the sort algorithms you will be implementing. The sort algorithms are:

   • BubbleSort
   • SelectionSort
   • InsertionSort

Output From Driver Main Method

For each combination of SortType, ArrayType, and ArraySize (1,000 and 10,000); you will call the runSort(SortType sortType, ArrayType arrayType, int arraySize, int numberOfTimes) with numberOfTimes = 10.

For each call to the runSort() method, you will produce the following output:

      SortType, ArrayType, Array Size
      -------------------------------------------------------------------------------------------------------------------------
      testTime1 testTime2 testTime3 testTime4 testTime5 testTime6 testTime7 testTime8 testTime9 testTime10 --- Average testTime  
    

Sample Output

    BubbleSort, Equal, 1,000
    --------------------------------------------------------------------------------------------------------------------
    191112    105869    32156     31878     31782     59693     33915     42761     31835     28588         58958.9  
    
    
    SelectionSort, Equal, 1,000
    --------------------------------------------------------------------------------------------------------------------
    6178978   1077160   4346520   203510    169876    169370    169031    189110    168926    168830        1284131.1
    
    
    InsertionSort, Equal, 1,000
    --------------------------------------------------------------------------------------------------------------------
    54990     49565     47539     47891     54455     47858     47396     47412     47388     47761         49225.5  
    
    
    BubbleSort, Random, 1,000
    --------------------------------------------------------------------------------------------------------------------
    8838428   2501037   5466853   991840    1002020   974357    1034771   901121    1033604   968611        2371264.2
    
    
    SelectionSort, Random, 1,000
    --------------------------------------------------------------------------------------------------------------------
    4957374   1917113   1970590   1848484   1785022   1869207   1804157   1788345   1849464   1830821       2162057.7
    
    
    InsertionSort, Random, 1,000
    --------------------------------------------------------------------------------------------------------------------
    5172407   2603500   2689329   225980    228721    297706    250314    235043    311123    276796        1229091.9
    
    
    BubbleSort, Increasing, 1,000
    --------------------------------------------------------------------------------------------------------------------
    1476      1145      1079      1131      1104      1121      1130      1013      1015      1035          1124.9   
    
    
    SelectionSort, Increasing, 1,000
    --------------------------------------------------------------------------------------------------------------------
    2039647   2009135   1850353   1886047   1843365   1792060   1772120   1772111   1772035   1944492       1868136.5
    
    
    InsertionSort, Increasing, 1,000
    --------------------------------------------------------------------------------------------------------------------
    1798      1510      1462      1504      1459      1461      1533      1560      1437      1483          1520.7   
    
    
    BubbleSort, Decreasing, 1,000
    --------------------------------------------------------------------------------------------------------------------
    774127    780207    777420    776562    800886    775011    774859    774635    774748    794453        780290.8 
    
    
    SelectionSort, Decreasing, 1,000
    --------------------------------------------------------------------------------------------------------------------
    1776708   1775741   1775165   1775232   1816181   1777162   1775683   1775201   1819986   1775779       1784283.8
    
    
    InsertionSort, Decreasing, 1,000
    --------------------------------------------------------------------------------------------------------------------
    395047    394130    395717    393112    392769    392448    392135    393422    393295    392983        393505.8 
    
    
    BubbleSort, IncreasingAndRandom, 1,000
    --------------------------------------------------------------------------------------------------------------------
    433834    410587    427825    417589    416083    414399    413556    411225    410420    409206        416472.4 
    
    
    SelectionSort, IncreasingAndRandom, 1,000
    --------------------------------------------------------------------------------------------------------------------
    1805148   1822855   1779231   1780510   1780017   1822514   1779334   1779271   1778849   2009777       1813750.6
    
    
    InsertionSort, IncreasingAndRandom, 1,000
    --------------------------------------------------------------------------------------------------------------------
    48600     44373     38483     41166     44329     52977     48359     42039     40763     37750         43883.9  
    
    
    BubbleSort, Equal, 10,000
    --------------------------------------------------------------------------------------------------------------------
    10058     9393      9488      9542      9534      9392      9428      10059     9480      9417          9579.1   
    
    
    SelectionSort, Equal, 10,000
    --------------------------------------------------------------------------------------------------------------------
    191366354 187554985 188603531 184341418 186428128 185860130 185716015 186340036 187208580 187737316     187115649.3
    
    
    InsertionSort, Equal, 10,000
    --------------------------------------------------------------------------------------------------------------------
    14861     14367     14410     14398     14384     14567     14738     14416     14413     14353         14490.7  
    
    
    BubbleSort, Random, 10,000
    --------------------------------------------------------------------------------------------------------------------
    186418604 183675397 189853059 199857508 200631540 200654263 201833244 195045570 198094593 200647356     195671113.4
    
    
    SelectionSort, Random, 10,000
    --------------------------------------------------------------------------------------------------------------------
    200169472 199737694 199449103 199443166 203046084 198645391 199054934 198118050 184194160 186720044     196857809.8
    
    
    InsertionSort, Random, 10,000
    --------------------------------------------------------------------------------------------------------------------
    25105923  22648155  22922924  23478437  25129211  23074360  25667139  24458487  24205973  23509254      24019986.3
    
    
    BubbleSort, Increasing, 10,000
    --------------------------------------------------------------------------------------------------------------------
    8982      8756      8811      8735      9406      12465     8592      8516      8653      8538          9145.4   
    
    
    SelectionSort, Increasing, 10,000
    --------------------------------------------------------------------------------------------------------------------
    204013259 201744523 194572506 195642828 195749549 197695840 199005343 196029675 195982435 196820062     197725602.0
    
    
    InsertionSort, Increasing, 10,000
    --------------------------------------------------------------------------------------------------------------------
    18139     16910     20397     19720     27087     16012     16413     16786     15941     15874         18327.9  
    
    
    BubbleSort, Decreasing, 10,000
    --------------------------------------------------------------------------------------------------------------------
    93032696  96034085  87551333  88123959  87183100  88661984  87835992  87152855  88224176  87307900      89110808.0
    
    
    SelectionSort, Decreasing, 10,000
    --------------------------------------------------------------------------------------------------------------------
    201607878 200061596 196748291 206039299 208471119 208447962 209103309 204952725 205117767 202873459     204342340.5
    
    
    InsertionSort, Decreasing, 10,000
    --------------------------------------------------------------------------------------------------------------------
    53908443  47481274  50561418  50572387  49996934  47557035  50806159  48784234  47897893  48063884      49562966.1
    
    
    BubbleSort, IncreasingAndRandom, 10,000
    --------------------------------------------------------------------------------------------------------------------
    51884652  50479094  51374672  52624514  62330382  50190966  50267878  50128180  47477963  51394383      51815268.4
    
    
    SelectionSort, IncreasingAndRandom, 10,000
    --------------------------------------------------------------------------------------------------------------------
    204142153 202736222 201443547 203024404 202335240 203071435 194312589 201748151 199246740 194467577     200652805.8
    
    
    InsertionSort, IncreasingAndRandom, 10,000
    --------------------------------------------------------------------------------------------------------------------
    4520635   4357003   4237677   4243873   4861083   4215219   3927815   4576842   4273242   4363618       4357700.7
  

Analysis:

Using the test time tables you created by running Driver.main(), copy your results into a Microsoft Word document and answer the following questions using 1-3 complete sentences for each question:

1. Create graphs from the test times you measured.
2. Which sort worked best on data in constant or increasing order (ie already sorted data)? Why do you think t his sort worked best?
3. Did the same sort do well on the case of mostly sorted data? Why or why not?
4. In general, did the ordering of the incoming data affect the performance of the sorting algorithms? Please answer this question by referencing specific data from your table to support your answer.
5. Which sort did best on the shorter (ie n=1,000) data sets? Did the same one do better on the longer (ie n=10,000) data sets? Why or why not? Please use specific data from your table to support your answer.
6. In general, which sort did better? Give a hypothesis as to why the difference in performance exists.
7. Are there results in your table that seem to be inconsistent? (ex. If I get run times for a sort that look like this {1.3, 1.5, 1.6, 7.0, 1.2, 1.6, 1.4, 1.8, 2.0, 1.5] the 7.0 entry is not consistent with the rest). Why do you think this happened?

Please submit the completed assignment in your zyBooks , in the Homework 2 Chapter.

Please submit your analysis on Blackboard as a typed Microsoft Word file (.docx). No other forms of submission will be accepted. Please include your graphs in the same file as your analysis.