Homework 2

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

This Homework Is Due By 11:55 PM on September 30, 2015

1. Implementation:
   
   In lecture, we reviewed three sorting algorithms: Bubble Sort , Selection Sort , and Insertion Sort . Write a Java program that implements all three sort algorithms. Your implementation must be in a class named Sort. Your Sort class must implement the following methods:
   
   
   1. public static long bubbleSort(Comparable<Integer>[] listOfObjects);
      
      This method will sort the specified listOfObjects using the Bubble Sort algorithm.
      
      Input Parameter: Comparable<Integer>[] listOfObjects - An array of Objects to be sorted. These Objects must implement the Comparable interface, which is implemented by the Integer class.
      
      Method Returns: a long value containing the number of nano-seconds it took to sort the specified listOfObjects. This value must be a positive long number.
   
   
   
   2. public static long selectionSort(Comparable<Integer>[] listOfObjects);
      
      This method will sort the specified listOfObjects using the Selection Sort algorithm.
      
      Input Parameter: Comparable<Integer>[] listOfObjects - An array of Objects to be sorted. These Objects must implement the Comparable interface, which is implemented by the Integer class.
      
      Method Returns: a long value containing the number of nano-seconds it took to sort the specified listOfObjects. This value must be a positive long number.
   
   
   
   3. public static long insertionSort(Comparable<Integer>[] listOfObjects);
      
      This method will sort the specified listOfObjects using the Insertion Sort algorithm.
      
      Input Parameter: Comparable<Integer>[] listOfObjects - An array of Objects to be sorted. These Objects must implement the Comparable interface, which is implemented by the Integer class.
      
      Method Returns: a long value containing the number of nano-seconds it took to sort the specified listOfObjects. This value must be a positive long number.


2. Test Cases:
   
   You must also write a driver program that demonstrates that all three sort programs work. Your driver should use the following test cases, please note that all the numbers must be instances of the Integer class in Java:
   
   
   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.
   
   Your driver must be in a class named Driver. Your Driver class must implement the following definitions:
   
   
   1. public static enum ArrayType {Identical, Random, Increasing, Decreasing, IncreasingAndRandom};
   
   
   
   2. public static enum SortType {BubbleSort, SelectionSort, InsertionSort};
   
   
   Your Driver class must implement the following methods:
   
   
   1. public static Comparable<Integer>[] getArrayOfIdenticalNumbers(int count);
      
      This method will create and return an array of Integer objects, all representing the same integer value. The size of the array is specified by the count parameter.
      
      Input Parameter: int count - The number of entries in the resulting array of Integers.
      
      Method Returns: The created array of Integers as an array of Objects that implement the Comparable interface, which is implemented by the Integer class.
   
   
   
   2. public static Comparable<Integer>[] getArrayOfRandomNumbers(int count);
      
      This method will create and return an array of Integer objects, each representing a random integer value. The size of the array is specified by the count parameter.
      
      Input Parameter: int count - The number of entries in the resulting array of Integers.
      
      Method Returns: The created array of Integers as an array of Objects that implement the Comparable interface, which is implemented by the Integer class.
   
   
   
   3. public static Comparable<Integer>[] getArrayOfIncreasingNumbers(int count);
      
      This method will create and return an array of Integer objects. The Integer objects will be arranged in increasing order (ex. 2, 4, 6, ...) in the resulting array. The size of the array is specified by the count parameter.
      
      Input Parameter: int count - The number of entries in the resulting array of Integers.
      
      Method Returns: The created array of Integers as an array of Objects that implement the Comparable interface, which is implemented by the Integer class.
   
   
   
   4. public static Comparable<Integer>[] getArrayOfDecreasingNumbers(int count);
      
      This method will create and return an array of Integer objects. The Integer objects will be arranged in decreasing order (ex. 100, 98, 96, ...) in the resulting array. The size of the array is specified by the count parameter.
      
      Input Parameter: int count - The number of entries in the resulting array of Integers.
      
      Method Returns: The created array of Integers as an array of Objects that implement the Comparable interface, which is implemented by the Integer class.
   
   
   
   5. public static Comparable<Integer>[] getArrayOfIncreasingAndRandomNumbers(int countIncreasing, int countRandom);
      
      This method will create and return an array of Integer objects. The first countIncreasing Integer objects will be arranged in increasing order (ex. 2, 4, 6, ...) and the last countRandom Integer objects will be arranged in random order in the resulting array. The size of the array is specified by the sum of the countIncreasing and countRandom parameters.
      
      Input Parameter: int countIncreasing - The number of entries that are arranged in increasing order.
      Input Parameter: int countRandom - The number of entries that are arranged in random order.
      
      Method Returns: The created array of Integers as an array of Objects that implement the Comparable interface, which is implemented by the Integer class.
   
   
   
   6. public static Comparable<Integer>[] runSort(SortType sortType, ArrayType arrayType, int numberOfElements);
      
      This method with call the appropriate sort specified by the sortType parameter a total of 10 times. Before each sort, the method will generate the appropriate type of array specified by the arrayType and the array will contain the the number of elements specified by numberOfElements. The method will also save the run time of each call into a static, private array variable that can be obtained by the getRunTimes() method specified below.
      
      Input Parameter: SortType sortType - The desired sort, selected from the Sort.SortType enum.
      Input Parameter: ArrayType arrayType - The desired type of array, selected from the Sort.ArrayType enum.
      Input Parameter: int numberOfElements - The number of elements that should be in the array to be sorted.
      
      Method Returns: The sorted array of Integers as an array of Objects that implement the Comparable interface, which is implemented by the Integer class.
   
   
   
   7. public static long[] getRunTimes();
      
      Method Returns: The array of long values containing the run times from the previous test case.
   
   
   
   8. public static void clearRunTimes();
      
      This method will clear the run times to all zero.
   
   
   
   9. public static void main(String[] args);
      
      This method will be where you run all three sorts on all the possible arrays specified above. This method should also print out the run times for each sort in a table format, you must include this table in your analysis (See below).


3. Analysis:
   
   Using the tables you created by running Driver.main(), copy your results into a Microsoft Work document and answer the following questions using complete sentences:
   
   
   1. Which sort worked best on data in constant or increasing order (ie already sorted data)? Why do you think this sort worked best?
   2. Did the same sort do well on the case of mostly sorted data? Why or why not?
   3. In general, did the ordering of the incoming data affect the performance of the sorting algorithms? Please answer this question by referencing specific data from your table to support your answer.
   4. Which sort did best on the shorter (ie n=1,000) data sets? Did the same one do better on the longer (ie n=10,000) data sets? Why or why not? Please use specific data from your table to support your answer.
   5. In general, which sort did better? Give a hypothesis as to why the difference in performance exists.
   6. Where there results in your table that seem to be inconsistent? (ex. If I get run times for a sort that look like this {1.3, 1.5, 1.6, 7.0, 1.2, 1.6, 1.4, 1.8, 2.0, 1.5] the 7.0 entry is not consistent with the rest). Why do you think this happened?

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

Please submit the completed Java programs as a zip file containing only the classes specified above to the Mimir Platform Website .

Please submit your analysis on Blackboard as a typed Microsoft Word file (.doc or .docx). No other forms of submission will be accepted.