Homework 5

CMP 338: Data Structures & Algorithms
Lehman College, City University of New York
Fall 2015

This Homework Is Due By 11:59 PM on Wednesday December 2, 2015

1. Implementation:
   

   Implement both the MergeSort and QuickSort classes. These classes must be named MergeSort and QuickSort respectively. The classes in the text book use arrays, your implementations should work with Vector's instead. Also, please note that some of the methods have changed names from the way they were in the text book.

   For your implementation of QuickSort, you must have three different ways of choosing the pivot as specified by the PivotType enum which will be defined in QuickSort.



2. Test Cases:
   

   Your driver program should sort the following types of Vectors using both sort algorithms. In the case of QuickSort you should sort the Vectors with all three methods of selecting the pivot.

   1. A Vector of 10,000 identical Integers.
   2. A Vector of 10,000 random Integers.
   3. A Vector of 10,000 increasing Integers.
   4. A Vector of 10,000 decreasing Integers.
   5. A Vector of 9,000 increasing Integers followed by 1,000 random Integers.



3. Driver Class:
   
   Your driver must be in a class named Driver. Your Driver class must implement the following:
   
   
   1. VectorType enum
   2. All the methods specified in the Driver documentation



4. Statistics Class:
   
   In addition to printing the run times for each test case, you will have to also display the average time and the standard deviation. You will have a class named Statistics. and it must implement all the methods specified in the Statistics documentation.

Please make sure that all your Java programs are in the default package.

Please compress the Java programs as a zip file containing:

1. MergeSort.java
2. QuickSort.java
3. Driver.java
4. Statistics.java

Please submit your zip file at the Mimir Platform Website .