Homework 7

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

This Homework Is Due By 11:59 PM on Wednesday April 29, 2015

1. Implementation: (35 Points)
   

   Implement both the MergeSort and QuickSort algorithms. However, instead of using Arrays, your implementation should work with Vectors instead.

   For your implementation of QuickSort, you must have two different ways of choosing the pivot element:

   1. Choose the first element as the pivot.
   2. Choose the midde value of first, last and ((first + last)/2).


2. Test Cases: (15 Points)
   

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

   • Create 10,000 contacts, with name and phoneNumber data items. The name items should be generated in aphabetical order. All your contacts should be stored in a Vector<Person>.
   • Create 10,000 contacts, with name and phoneNumber data items. The name items should be generated randomly. All your contacts should be stored in a Vector<Person>.
   • Create 10,000 contacts, with name and phoneNumber data items. The name items should be generated in reverse aphabetical order. All your contacts should be stored in a Vector<Person>.

   Run all test cases 10 times and make a table with the running time for each run, as well as the average and the standard deviation for each test case. Make sure that you re-create your 10,000 contacts for each test case.

Please submit the completed assignment on Blackboard. You must submit your Java programs as a zip file of your Eclipse project.