In this assignment you will be implementing and testing all three sort algorithms: Merge Sort , Quick Sort , and Heap Sort .
You will also be using the TestTimes class with the expanded functionality from
Homework 4
.
In addition you will also be writing a driver to test the sorting algorithms and you will be measuring the test times of each sort.
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.
You will copy the TestTimes class that you enhanced with added functionality in
Homework 4
to the project you are using for this assignment.
This TestTimes class implements the expanded
TestTimes Interface
.
Please note that you will also have to re-submit TestTimes.java to zyBooks in the
TestTimes zyLab.
You will write the MergeSort.java class which will implement the
SortInterface
using the
Merge Sort
algorithm. The interface may be downloaded from
here
.
You can see the Merge Sort Java Documentation here .
You will write the QuickSort.java class which will implement the
SortInterface
using the
Quick Sort
algorithm. The interface may be downloaded from
here
.
You can see the Quick Sort Java Documentation here .
For your implementation of QuickSort, you must have three different ways of choosing
the pivot as specified by the PivotType enum
which is defined defined in the QuickSort class.
You will write the HeapSort.java class which will implement the
SortInterface
using the
Heap Sort
algorithm. The interface may be downloaded from
here
.
You can see the Heap Sort Java Documentation here .
You will write the SortDriverGeneric.java class which will implement the
SortDriverInterfaceGeneric
. The interface may be downloaded from
here
.
Please note that, in addition to implementing the SortDriverInterfaceGeneric, you are also required to write
your own public static main(String[] args) method in SortDriverGeneric.java that performs all of
the required tests as specified below.
You will test your three sort implementations 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 SortDriverInterfaceGeneric includes the definitions of two enums:
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:
ArrayType,Array Size--------------------- Run 1 Run 2 Run 3 Run 4 Run 5 Run 6 Run 7 Run 8 Run 9 Run 10 Average Micro Micro Micro Micro Micro Micro Micro Micro Micro Micro Micro Seconds Seconds Seconds Seconds Seconds Seconds Seconds Seconds Seconds Seconds Seconds ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- MergeSort QuickSort FirstElement QuickSort RandomElement QuickSort MidOfFirstMidLastElement HeapSort
Run 1 Run 2 Run 3 Run 4 Run 5 Run 6 Run 7 Run 8 Run 9 Run 10 Average
Kilo Bytes Kilo Bytes Kilo Bytes Kilo Bytes Kilo Bytes Kilo Bytes Kilo Bytes Kilo Bytes Kilo Bytes Kilo Bytes Kilo Bytes
---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ----------
MergeSort
QuickSort FirstElement
QuickSort RandomElement
QuickSort MidOfFirstMidLastElement
HeapSort
Array Type = Equal, Array Size = 1,000
----------------------------------------
Run 1 Run 2 Run 3 Run 4 Run 5 Run 6 Run 7 Run 8 Run 9 Run 10 Average
Micro Micro Micro Micro Micro Micro Micro Micro Micro Micro Micro
Seconds Seconds Seconds Seconds Seconds Seconds Seconds Seconds Seconds Seconds Seconds
---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ----------
MergeSort 1225.988 366.247 376.482 181.601 166.690 314.644 295.194 176.940 178.073 166.657 344.852
QuickSortFirstElement 7319.964 4616.756 4542.304 13078.626 12535.789 1175.136 355.081 353.767 353.590 354.676 4468.569
QuickSortRandomElement 8204.218 8124.633 11535.159 7012.840 370.765 369.844 369.987 368.157 368.152 369.137 3709.289
QuickSortMidOfFirstMidLastElement 10620.545 10584.426 10202.558 354.109 350.471 350.101 351.344 350.263 501.290 428.528 3409.364
HeapSort 4019.844 3765.847 2410.563 2367.910 1262.814 790.256 769.116 768.767 768.944 768.674 1769.274
Run 1 Run 2 Run 3 Run 4 Run 5 Run 6 Run 7 Run 8 Run 9 Run 10 Average
Kilo Kilo Kilo Kilo Kilo Kilo Kilo Kilo Kilo Kilo Kilo
Bytes Bytes Bytes Bytes Bytes Bytes Bytes Bytes Bytes Bytes Bytes
---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ----------
MergeSort 2621.477 2621.477 2621.477 2621.477 2621.477 2621.477 2621.477 2621.477 2621.477 2621.477 2621.477
QuickSortFirstElement 2621.477 2621.477 2621.477 2621.477 2621.477 2621.477 2621.477 2621.477 2621.477 2621.477 2621.477
QuickSortRandomElement 2621.477 2621.477 2621.477 3942.820 3942.820 3942.820 3942.820 3942.820 3942.820 3942.820 3546.417
QuickSortMidOfFirstMidLastElement 3942.820 3942.820 3942.820 3942.820 3942.820 3942.820 3942.820 3942.820 3942.820 3942.820 3942.820
HeapSort 3942.820 3942.820 3942.820 3942.820 3942.820 3942.820 3942.820 3942.820 3942.820 3942.820 3942.820
Array Type = Random, Array Size = 1,000
-----------------------------------------
Run 1 Run 2 Run 3 Run 4 Run 5 Run 6 Run 7 Run 8 Run 9 Run 10 Average
Micro Micro Micro Micro Micro Micro Micro Micro Micro Micro Micro
Seconds Seconds Seconds Seconds Seconds Seconds Seconds Seconds Seconds Seconds Seconds
---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ----------
MergeSort 1002.013 680.516 683.747 680.609 674.369 678.985 675.920 679.484 685.805 679.916 712.136
QuickSortFirstElement 672.574 771.807 335.592 228.993 182.921 218.588 206.592 169.633 181.978 190.322 315.900
QuickSortRandomElement 232.937 218.909 227.728 223.013 222.757 215.130 212.293 230.885 216.704 235.638 223.599
QuickSortMidOfFirstMidLastElement 465.545 423.955 345.060 217.772 284.554 248.194 218.631 245.856 217.353 265.592 293.251
HeapSort 11399.998 10362.063 12676.608 29965.280 2005.303 1636.352 1548.178 1548.042 1522.725 1497.961 7416.251
Run 1 Run 2 Run 3 Run 4 Run 5 Run 6 Run 7 Run 8 Run 9 Run 10 Average
Kilo Kilo Kilo Kilo Kilo Kilo Kilo Kilo Kilo Kilo Kilo
Bytes Bytes Bytes Bytes Bytes Bytes Bytes Bytes Bytes Bytes Bytes
---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ----------
MergeSort 3942.820 3942.820 3942.820 3942.820 3942.820 3942.820 3942.820 3942.820 3942.820 3942.820 3942.820
QuickSortFirstElement 3942.820 3942.820 3942.820 3942.820 3942.820 3942.820 3942.820 3942.820 3942.820 5253.539 4073.892
QuickSortRandomElement 5253.539 5253.539 5253.539 5253.539 5253.539 5253.539 5253.539 5253.539 5253.539 5253.539 5253.539
QuickSortMidOfFirstMidLastElement 5253.539 5253.539 5253.539 5253.539 5253.539 5253.539 5253.539 5253.539 5253.539 5253.539 5253.539
HeapSort 5253.539 5253.539 5253.539 5253.539 5253.539 5253.539 5253.539 5253.539 5253.539 5253.539 5253.539
Array Type = Increasing, Array Size = 1,000
---------------------------------------------
Run 1 Run 2 Run 3 Run 4 Run 5 Run 6 Run 7 Run 8 Run 9 Run 10 Average
Micro Micro Micro Micro Micro Micro Micro Micro Micro Micro Micro
Seconds Seconds Seconds Seconds Seconds Seconds Seconds Seconds Seconds Seconds Seconds
---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ----------
MergeSort 778.424 392.068 261.896 269.551 257.774 266.966 272.279 258.286 249.487 265.384 327.212
QuickSortFirstElement 502.359 487.486 532.512 487.463 486.982 486.429 612.212 505.826 803.275 852.698 575.724
QuickSortRandomElement 1033.992 517.350 241.229 248.969 246.429 248.361 254.760 247.912 243.408 243.077 352.549
QuickSortMidOfFirstMidLastElement 193.578 147.711 178.357 175.839 173.639 176.110 176.104 173.417 176.513 177.429 174.870
HeapSort 2772.937 2798.854 2059.498 1749.410 1566.130 1560.114 1576.260 1562.290 1576.785 1568.134 1879.041
Run 1 Run 2 Run 3 Run 4 Run 5 Run 6 Run 7 Run 8 Run 9 Run 10 Average
Kilo Kilo Kilo Kilo Kilo Kilo Kilo Kilo Kilo Kilo Kilo
Bytes Bytes Bytes Bytes Bytes Bytes Bytes Bytes Bytes Bytes Bytes
---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ----------
MergeSort 5253.539 5253.539 5253.539 5253.539 5253.539 5253.539 5253.539 5253.539 5253.539 5253.539 5253.539
QuickSortFirstElement 5253.539 5253.539 5253.539 5253.539 5253.539 5253.539 6568.180 6568.180 6568.180 6568.180 5779.395
QuickSortRandomElement 6568.180 6568.180 6568.180 6568.180 6568.180 6568.180 6568.180 6568.180 6568.180 6568.180 6568.180
QuickSortMidOfFirstMidLastElement 6568.180 6568.180 6568.180 6568.180 6568.180 6568.180 6568.180 6568.180 6568.180 6568.180 6568.180
HeapSort 6568.180 6568.180 6568.180 6568.180 6568.180 6568.180 6568.180 6568.180 6568.180 6568.180 6568.180
Array Type = Decreasing, Array Size = 1,000
---------------------------------------------
Run 1 Run 2 Run 3 Run 4 Run 5 Run 6 Run 7 Run 8 Run 9 Run 10 Average
Micro Micro Micro Micro Micro Micro Micro Micro Micro Micro Micro
Seconds Seconds Seconds Seconds Seconds Seconds Seconds Seconds Seconds Seconds Seconds
---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ----------
MergeSort 302.722 286.811 248.437 258.089 256.336 257.298 256.903 264.806 260.541 258.486 265.043
QuickSortFirstElement 9347.140 6372.894 1351.808 1136.354 1135.421 1136.525 1134.928 1135.840 1136.340 1051.745 2493.900
QuickSortRandomElement 69.611 57.068 58.256 55.471 57.308 61.131 57.153 55.244 59.261 60.229 59.073
QuickSortMidOfFirstMidLastElement 535.774 395.658 394.883 394.399 394.587 442.467 394.317 393.458 393.266 394.892 413.370
HeapSort 1571.012 1585.387 1555.207 1537.302 1543.621 1549.632 1650.162 1542.169 1472.531 1519.874 1552.690
Run 1 Run 2 Run 3 Run 4 Run 5 Run 6 Run 7 Run 8 Run 9 Run 10 Average
Kilo Kilo Kilo Kilo Kilo Kilo Kilo Kilo Kilo Kilo Kilo
Bytes Bytes Bytes Bytes Bytes Bytes Bytes Bytes Bytes Bytes Bytes
---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ----------
MergeSort 6568.180 6568.180 6568.180 6568.180 6568.180 6568.180 6568.180 6568.180 6568.180 6568.180 6568.180
QuickSortFirstElement 6568.180 6568.180 7878.914 7878.914 7878.914 7878.914 7878.914 7878.914 7878.914 7878.914 7616.767
QuickSortRandomElement 7878.914 7878.914 7878.914 7878.914 7878.914 7878.914 7878.914 7878.914 7878.914 7878.914 7878.914
QuickSortMidOfFirstMidLastElement 7878.914 7878.914 7878.914 7878.914 7878.914 7878.914 7878.914 7878.914 7878.914 7878.914 7878.914
HeapSort 7878.914 7878.914 7878.914 7878.914 7878.914 7878.914 7878.914 7878.914 7878.914 7878.914 7878.914
Array Type = IncreasingAndRandom, Array Size = 1,000
------------------------------------------------------
Run 1 Run 2 Run 3 Run 4 Run 5 Run 6 Run 7 Run 8 Run 9 Run 10 Average
Micro Micro Micro Micro Micro Micro Micro Micro Micro Micro Micro
Seconds Seconds Seconds Seconds Seconds Seconds Seconds Seconds Seconds Seconds Seconds
---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ----------
MergeSort 447.550 265.523 275.538 261.604 269.220 278.255 263.490 262.646 268.534 262.287 285.465
QuickSortFirstElement 106.217 102.844 106.369 111.738 105.775 105.917 112.264 114.842 106.145 115.167 108.728
QuickSortRandomElement 64.438 64.685 63.951 63.668 63.373 59.160 62.299 61.688 59.639 62.232 62.513
QuickSortMidOfFirstMidLastElement 244.394 184.680 182.756 187.546 187.065 183.675 187.696 187.409 183.483 183.573 191.228
HeapSort 1575.360 1564.316 1565.788 2674.877 2658.861 1611.340 1570.999 1566.801 1567.760 1572.675 1792.878
Run 1 Run 2 Run 3 Run 4 Run 5 Run 6 Run 7 Run 8 Run 9 Run 10 Average
Kilo Kilo Kilo Kilo Kilo Kilo Kilo Kilo Kilo Kilo Kilo
Bytes Bytes Bytes Bytes Bytes Bytes Bytes Bytes Bytes Bytes Bytes
---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ----------
MergeSort 7878.914 7878.914 7878.914 7878.914 7878.914 7878.914 7878.914 7878.914 9193.555 9193.555 8141.842
QuickSortFirstElement 9193.555 9193.555 9193.555 9193.555 9193.555 9193.555 9193.555 9193.555 9193.555 9193.555 9193.555
QuickSortRandomElement 9193.555 9193.555 9193.555 9193.555 9193.555 9193.555 9193.555 9193.555 9193.555 9193.555 9193.555
QuickSortMidOfFirstMidLastElement 9193.555 9193.555 9193.555 9193.555 9193.555 9193.555 9193.555 9193.555 9193.555 9193.555 9193.555
HeapSort 9193.555 9193.555 9193.555 9193.555 9193.555 9193.555 9193.555 9193.555 9193.555 9193.555 9193.555
Array Type = Equal, Array Size = 10,000
-----------------------------------------
Run 1 Run 2 Run 3 Run 4 Run 5 Run 6 Run 7 Run 8 Run 9 Run 10 Average
Micro Micro Micro Micro Micro Micro Micro Micro Micro Micro Micro
Seconds Seconds Seconds Seconds Seconds Seconds Seconds Seconds Seconds Seconds Seconds
---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ----------
MergeSort 2091.885 2079.208 2048.097 2035.151 2054.812 2079.515 2035.197 2039.680 2068.819 2034.266 2056.663
QuickSortFirstElement 55318.415 52896.495 55999.942 56703.106 52703.577 55806.136 60200.505 58342.500 53318.605 57109.010 55839.829
QuickSortRandomElement 56921.940 56580.601 56704.463 57564.721 57401.527 58437.018 59242.092 56541.825 57440.322 56831.314 57366.582
QuickSortMidOfFirstMidLastElement 55896.008 54627.022 58790.051 53765.479 55193.947 58089.231 58612.749 58552.544 55242.860 58190.740 56696.063
HeapSort 139726.138 138414.206 137710.981 137681.194 139610.029 138836.751 139959.541 137516.403 128743.152 137492.566 137569.096
Run 1 Run 2 Run 3 Run 4 Run 5 Run 6 Run 7 Run 8 Run 9 Run 10 Average
Kilo Kilo Kilo Kilo Kilo Kilo Kilo Kilo Kilo Kilo Kilo
Bytes Bytes Bytes Bytes Bytes Bytes Bytes Bytes Bytes Bytes Bytes
---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ----------
MergeSort 10504.289 10504.289 10504.289 10504.289 10582.445 11971.336 11971.336 11971.336 11971.336 13282.070 11376.702
QuickSortFirstElement 13282.070 13282.070 13282.070 13282.070 14631.883 14631.883 14631.883 14631.883 14631.883 15981.695 14226.939
QuickSortRandomElement 15981.695 15981.695 15981.695 15981.695 17331.492 17331.492 17331.492 17331.492 17331.492 18720.383 16930.463
QuickSortMidOfFirstMidLastElement 18720.383 18720.383 18720.383 18720.383 20070.180 20070.180 20070.180 20070.180 20070.180 21459.070 19669.150
HeapSort 21459.070 21459.070 21459.070 21459.070 22808.867 22808.867 22808.867 22808.867 22808.867 24197.758 22407.838
Array Type = Random, Array Size = 10,000
------------------------------------------
Run 1 Run 2 Run 3 Run 4 Run 5 Run 6 Run 7 Run 8 Run 9 Run 10 Average
Micro Micro Micro Micro Micro Micro Micro Micro Micro Micro Micro
Seconds Seconds Seconds Seconds Seconds Seconds Seconds Seconds Seconds Seconds Seconds
---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ----------
MergeSort 1274.205 1263.109 1254.625 1256.863 1265.246 1255.359 1254.789 1278.698 1267.516 1267.148 1263.756
QuickSortFirstElement 860.607 834.360 869.664 876.201 896.949 897.332 854.159 868.879 880.824 838.278 867.725
QuickSortRandomElement 992.870 991.819 1006.233 1026.069 1007.764 1192.863 1051.091 981.119 983.884 1075.697 1030.941
QuickSortMidOfFirstMidLastElement 1246.202 977.245 910.790 874.718 889.985 908.722 892.095 911.134 905.000 923.693 943.958
HeapSort 156054.315 154937.296 153331.749 158088.041 154260.143 152621.344 157939.416 155569.196 152101.744 155377.448 155028.069
Run 1 Run 2 Run 3 Run 4 Run 5 Run 6 Run 7 Run 8 Run 9 Run 10 Average
Kilo Kilo Kilo Kilo Kilo Kilo Kilo Kilo Kilo Kilo Kilo
Bytes Bytes Bytes Bytes Bytes Bytes Bytes Bytes Bytes Bytes Bytes
---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ----------
MergeSort 24197.758 24197.758 24197.758 25508.492 25508.492 25508.492 25508.492 25586.648 26975.539 26975.539 25416.497
QuickSortFirstElement 26975.539 26975.539 28325.336 28325.336 28325.336 28325.336 28325.336 29636.070 29636.070 29636.070 28448.597
QuickSortRandomElement 29636.070 29636.070 30946.805 30946.805 30946.805 30946.805 30946.805 32257.539 32257.539 32257.539 31077.878
QuickSortMidOfFirstMidLastElement 32257.539 32257.539 33607.336 33607.336 33607.336 33607.336 33607.336 34996.227 34996.227 34996.227 33754.044
HeapSort 34996.227 34996.227 36346.023 36346.023 36346.023 36346.023 36346.023 37734.914 37734.914 37734.914 36492.731
Array Type = Increasing, Array Size = 10,000
----------------------------------------------
Run 1 Run 2 Run 3 Run 4 Run 5 Run 6 Run 7 Run 8 Run 9 Run 10 Average
Micro Micro Micro Micro Micro Micro Micro Micro Micro Micro Micro
Seconds Seconds Seconds Seconds Seconds Seconds Seconds Seconds Seconds Seconds Seconds
---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ----------
MergeSort 602.611 602.984 620.824 626.878 602.756 603.503 602.905 602.369 649.921 637.630 615.238
QuickSortFirstElement 54626.999 54778.936 55147.731 53053.964 53611.412 53124.092 52813.478 54537.492 58146.919 58140.412 54798.144
QuickSortRandomElement 620.904 611.237 645.080 644.272 600.096 589.079 599.535 620.848 573.407 767.621 627.208
QuickSortMidOfFirstMidLastElement 323.519 321.096 320.818 321.766 322.168 320.631 321.156 321.421 320.838 320.817 321.423
HeapSort 151356.332 147321.180 150120.966 150241.505 147768.999 148965.853 147219.194 147848.003 149852.003 146292.041 148698.608
Run 1 Run 2 Run 3 Run 4 Run 5 Run 6 Run 7 Run 8 Run 9 Run 10 Average
Kilo Kilo Kilo Kilo Kilo Kilo Kilo Kilo Kilo Kilo Kilo
Bytes Bytes Bytes Bytes Bytes Bytes Bytes Bytes Bytes Bytes Bytes
---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ----------
MergeSort 37734.914 39084.711 39084.711 39084.711 39084.711 39084.711 40434.523 40434.523 40434.523 40434.523 39489.656
QuickSortFirstElement 41745.258 41745.258 41745.258 41745.258 41745.258 43055.992 43055.992 43055.992 43055.992 43055.992 42400.625
QuickSortRandomElement 44405.789 44405.789 44405.789 44405.789 44405.789 45794.680 45794.680 45794.680 45794.680 45794.680 45100.234
QuickSortMidOfFirstMidLastElement 47144.477 47144.477 47144.477 47144.477 47144.477 48533.367 48533.367 48533.367 48533.367 48533.367 47838.922
HeapSort 49883.164 49883.164 49883.164 49883.164 49883.164 51272.055 51272.055 51272.055 51272.055 51272.055 50577.609
Array Type = Decreasing, Array Size = 10,000
----------------------------------------------
Run 1 Run 2 Run 3 Run 4 Run 5 Run 6 Run 7 Run 8 Run 9 Run 10 Average
Micro Micro Micro Micro Micro Micro Micro Micro Micro Micro Micro
Seconds Seconds Seconds Seconds Seconds Seconds Seconds Seconds Seconds Seconds Seconds
---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ----------
MergeSort 624.857 623.805 621.391 621.366 621.113 618.259 620.840 621.801 615.983 614.810 620.423
QuickSortFirstElement 101214.588 98629.835 98255.507 98904.303 99507.818 102608.419 99992.725 96522.689 97684.166 97318.837 99063.889
QuickSortRandomElement 671.796 652.900 655.895 666.836 634.494 735.145 740.316 675.150 696.038 652.273 678.084
QuickSortMidOfFirstMidLastElement 25736.919 27480.931 26172.345 26195.341 26957.436 26624.902 25969.047 25761.990 25950.284 26384.260 26323.346
HeapSort 146021.400 149824.893 149935.927 144959.169 145821.992 148962.189 145696.259 145895.437 150507.410 145608.773 147323.345
Run 1 Run 2 Run 3 Run 4 Run 5 Run 6 Run 7 Run 8 Run 9 Run 10 Average
Kilo Kilo Kilo Kilo Kilo Kilo Kilo Kilo Kilo Kilo Kilo
Bytes Bytes Bytes Bytes Bytes Bytes Bytes Bytes Bytes Bytes Bytes
---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ----------
MergeSort 52621.852 52621.852 52621.852 52621.852 53932.586 53932.586 53932.586 53932.586 55243.320 55243.320 53670.439
QuickSortFirstElement 55243.320 55243.320 55243.320 56593.133 56593.133 56593.133 56593.133 56593.133 57942.930 57942.930 56458.148
QuickSortRandomElement 57942.930 57942.930 57942.930 59331.820 59331.820 59331.820 59331.820 59331.820 60681.617 60681.617 59185.113
QuickSortMidOfFirstMidLastElement 60681.617 60681.617 60681.617 62070.508 62070.508 62070.508 62070.508 62070.508 63420.305 63420.305 61923.800
HeapSort 63420.305 63420.305 63420.305 64809.195 64809.195 64809.195 64809.195 64809.195 65536.000 65536.000 64537.889
Array Type = IncreasingAndRandom, Array Size = 10,000
-------------------------------------------------------
Run 1 Run 2 Run 3 Run 4 Run 5 Run 6 Run 7 Run 8 Run 9 Run 10 Average
Micro Micro Micro Micro Micro Micro Micro Micro Micro Micro Micro
Seconds Seconds Seconds Seconds Seconds Seconds Seconds Seconds Seconds Seconds Seconds
---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ----------
MergeSort 667.531 639.388 639.702 652.957 649.716 651.178 653.015 650.573 653.624 637.721 649.541
QuickSortFirstElement 7127.606 6797.316 7200.304 6954.867 6978.125 6924.512 7015.163 7029.001 6784.881 6924.482 6973.626
QuickSortRandomElement 688.467 714.553 664.870 659.154 664.134 691.519 667.335 683.189 656.585 660.890 675.070
QuickSortMidOfFirstMidLastElement 3384.053 3465.464 3738.428 3258.727 3532.566 3557.014 3397.902 3483.107 3518.972 3407.553 3474.379
HeapSort 146672.175 154517.461 148703.433 149433.321 150709.825 154691.033 147423.128 151997.549 149884.044 150496.771 150452.874
Run 1 Run 2 Run 3 Run 4 Run 5 Run 6 Run 7 Run 8 Run 9 Run 10 Average
Kilo Kilo Kilo Kilo Kilo Kilo Kilo Kilo Kilo Kilo Kilo
Bytes Bytes Bytes Bytes Bytes Bytes Bytes Bytes Bytes Bytes Bytes
---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ----------
MergeSort 1928.164 1928.164 1928.164 1928.164 2006.320 3381.531 3381.531 3381.531 3381.531 4678.586 2792.369
QuickSortFirstElement 4678.586 4678.586 4678.586 4678.586 6014.703 6014.703 6014.703 6014.703 6014.703 7350.820 5613.868
QuickSortRandomElement 7350.820 7350.820 7350.820 8686.938 8686.938 8686.938 8686.938 8686.938 9983.992 9983.992 8545.513
QuickSortMidOfFirstMidLastElement 9983.992 9983.992 9983.992 11281.047 11281.047 11281.047 11281.047 11281.047 12617.180 12617.180 11159.157
HeapSort 12617.180 12617.180 12617.180 13992.391 13992.391 13992.391 13992.391 13992.391 15367.602 15367.602 13854.870
Using the test time tables you created by running SortDriver.main(), copy your results into a Microsoft Word document and answer the following questions using 1-3 complete sentences for each question:
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.