Homework 2

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

This Homework Is Due By 11:59 PM on February 15, 2015

1. Implementation: (15 Points)
   
   In lecture, we reviewed three sorting algorithms: Bubble Sort , Selection Sort , and Insertion Sort . Write a Java program that implements all three sort algorithms.


2. Test Cases: (20 Points)
   
   You must also write a driver program that demonstrates that all three sort programs work. Your driver should use the following test cases:
   
   
   1. A list of 1,000 identical numbers
   2. A list of 1,000 numbers in random order
   3. A list of 1,000 numbers in increasing order
   4. A list of 1,000 numbers in decreasing order
   5. A list of 900 nunbers in increasing order followed by 100 numbers in random order.
   6. A list of 10,000 identical numbers
   7. A list of 10,000 numbers in random order
   8. A list of 10,000 numbers in increasing order
   9. A list of 10,000 numbers in decreasing order
   10. A list of 9,900 nunbers in increasing order followed by 100 numbers in random order.
   
   Run each test 10 times and make a table with the running time for each run, as well as the average and the standard deviation for each algorithm.


3. Analysis: (15 Points)
   
   Using the tables you created, answer the following questions using complete sentences:
   
   
   1. Which sort worked best on data in constant or increasing order (ie already sorted data)? Did the same sort do well on the case of mostly sorted data?
   2. In general, did the ordering of the incoming data affect the performance of the sorting algorithms? Using the data from your table, support your answer.
   3. Which sort did best on the shorter (ie n=10,000) data sets? Did the same one do better on the longer (ie n=100,000) data sets?
   4. In general, which sort did better? Give a hypothesis as to why the difference in performance exists.

Please submit the completed assignment on Blackboard. You must submit your Java programs as a zip file of your Eclipse project. The analysis must be a typed Microsoft Word file. No other forms of submission will be accepted.