Homework 8

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

This Homework Is Due By 11:59 PM on Wednesday May 6, 2015

1. Implementation: (35 Points)
   

   In Homework 7 you implemented both the MergeSort and QuickSort algorithms. For your QuickSort implementation, you also chose the pivot element in two different manners.

   For this assignment, you will extend Homework 7 by adding the following:

   1. Add another method of choosing the pivot element for your QuickSort implementation. You could, for example, randomly pick the pivot element.
   2. Implement the HeapSort algorithm.


2. Test Cases: (15 Points)
   

   Your driver program should sort the following 3 Vectors using all three algorithms. In the case of QuickSort you should sort the Vector with the three 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.