CSE017 Summer 2020                                                                       

Project 3: Sorting Analysis              

Objectives:

1. The student will implement a generic Heap class.
2. The student will implement the generic version of all sorting algorithms discussed in this course.
3. The student will compare the performance of the sorting algorithms for different data sets.

The same rules for extra credit for early submissions apply as in Projects 1&2.

NO LATE SUBMISSIONS ARE ALLOWED!

1)       Create a generic class Heap to implement the heap data structure discussed in this course.

2)       Create a class Sort that contains SIX static methods for each of the sorting algorithms discussed in this course:

a)       Selection Sort

b)       Insertion Sort

c)       Bubble Sort

d)       Merge Sort

e)       Quick Sort

f)        Heap Sort

3)       Write a test program, TestSorting.  In it, write the following six methods that return a data array according to the described criteria.  The six methods MUST use the same array returned by randomized() as the input parameter.  In other words, randomized() will return an array of randomly shuffled Integers; you must use this as input to the other methods (b)-(f).

a)       randomized(): Randomly generated integers in the range 0 to 1000

b)       fullySorted(): Sort the random data array in ascending order

c)       fourthShuffled(): Sort partially the random data array (sort followed by

                   shuffling the 25% first elements)

d)       halfShuffled(): Sort partially the random data array (sort followed by

                   shuffling the 50% first elements)

e)       threeQuartershuffled(): Sort partially the random data array (sort

                   followed by shuffling the 75% first elements)

f)        inverted(): Invert the sorted random data array (sorted in descending order)

4)       Call each of the generic sorting methods using the different data sets generated in (3)

5)       For each of (a)-(f), and using a table, record the number of iterations for each sorting algorithm.  This table should be printed to an output txt file (name this file results.txt) and should be similar to the following sample output:

6)       In a separate txt file that you create yourself (e.g., this is not created by your program), briefly discuss your results: Discuss first the performance of each sorting algorithm on the different data sets. Then compare the performance of the sorting algorithms to each other.

CAUTION: Be very careful about *how* you copy arrays and/or make changes to them.  Remember that arrays are passed by reference.