CPRG 311 assignment 2 sorting out sorting

ASSIGNMENT TWO: SORTING OUT SORTING

Description

You will be required to implement and perform experimental analysis on six sorting algorithms:

bubble, insertion, selection, merge, quick and a sort of your choice. The sort you choose needs to be researched and will be significantly different than the five that were assigned. The sixth sort selected should include a detailed description of the sort’s algorithm and a complexity analysis.

Specifications

  1. Create an abstract class in Java that will represent a three-dimensional geometrical shape. Using the

Strategy pattern discussed in class, 

  1. Implement the compareTo() method of the Comparable interface to compare two shapes by their height, and the compare() method of the Comparator interface to compare two shapes by their base area and their volume.
  2. The compare type will be provided as input from the command line to your program - h for height, v for volume, and a for base area via the -t option.
  1. Write a testing program that will read a text file (entered at the command line via the -f option) of random shapes that adds them to an array (not ArrayList). All shapes must be manipulated as elements of the corresponding collection. The first value in the data file contains the number of shapes in that file. A shape in the file is represented as follows (all values are separated by spaces):
    1. One of: Cylinder, Cone, Prism, Pyramid
    2. Cylinders and cones are followed by a double value representing the height and another double value representing radius.

e.g. Cylinder 9431.453 4450.123 or Cone 674.2435 652.1534

  1. c) Pyramids are followed by a double value representing the height and another double value representing edge length.

e.g. Pyramid 6247.53 2923.456

  1. d) Prisms are specified by the type of base polygon (SquarePrism, TrianglarPrism, PentagonalPrism, OctagonalPrism), a double value representing the height and another double value representing edge length. g. SquarePrism 8945.234 3745.334
  1. The testing application will then invoke the utility methods to re-arrange the figures according to the compare type from the largest to smallest (descending order).
  2. The testing program should print the time it took to sort the collection of objects for each sorting algorithm. It should also print the first and last value and every thousandth value in between.
  3. Implement the sorting algorithms as part of a utility class. It must sort a collection ofComparables. Make sure it is not dependent on the testing application and that it can be re-used in the future. (Your sorting methods should be invoked like the Arrays.sort() method.)
  4. File name F, the compare type and the sort type are provided as parameters (-f –t –s or -F –T –S) via command line. The program must be order and case insensitive. For example, all examples below are valid inputs:

java -jar sort.jar –fpolyfor1.txt –Tv –Sb java -jar sort.jar –ta –sQ –fpolyfor3.txt java -jar sort.jar –tH –Fpolyfor5.txt –sB

where v is volume, h is height, a is base area, b is bubble, s is selection, i is insertion, m is merge, q is quick, and your choice of sorting algorithm is z.

The assignment zip file will include the following:

  1. An executable Java Archive file (.jar) for your sort application called jar.
  2. A readMe.txt file with instructions on how to install and use the sort program.
  3. The project should have completed javadoc using “-private” option when generated, with output placed in the doc directory of the project.
  4. A folder containing the complete Eclipse project directory. At the root of the project directory, include a readMe.txt to describe the completeness of the assignment (as a percentage) and a list of known deficiencies and/or missing functionalities. Do NOT include the big data file in your upload.
  5. A file called mySort.txt that provides a detailed description of the sorting algorithm of your choice along with its complexity analysis. Make sure this is written in your own words and NOT copied or rephrased from another source.

Criteria for Marking Assignment

Command line works properly & abstract class generates shape objects

  

2

Comparable/Comparator Implementation

  

2

Five required sorts implemented in utility class

    

Bubble sort

  

1

Selection sort

  

1

Insertion sort

  

1

Merge sort

  

2

Quick sort

  

2

Implementation of student’s choice of sorting algorithm

  

2

Description and complexity analysis

  

2

Sort Output

  

2

Proper timing of sorts shown

  

1

Readmes/Instructions and javadoc documentation

  

2

     
 

Total:

 

/

20