Project: CS$/$CE$/$SE $3345$: Data Structures and Algorithm Analysis $\backslash$table$[[$Experimental Results,ArraySize,$50$K$,],[$Input List: Random,Comparisons,Movements,Total Time$],[$Insertion Sort,,,$],[$Quick Sort,,,$],[$Merge Sort,,,$],[$Heap Sort,,,$],[,,,],[$Experimental Results,ArraySize,$50$ K$,],[$Input List: Ascending Order,Comparisons,Movements,Total Time$],[$Insertion Sort,,,$],[$Quick Sort,,,$],[$Merge Sort,,,$],[$Heap Sort,,,$]]$

Purpose: Analysis of Sorting Techniques

Overview: One of the most important ADTs is the Dictionary and one of the most studied problem is

sorting. In this assignment, you will analyze multiple implementations of sorting algorithms.

Write a program to perform analysis on various sorting algorithms utilizing $2$ different data types.

insertionSort.java, quicksort.java, HeapSort.java, and MergeSort.java files are provided with this

assignment.

Create and submit a report discussing the analysis at each iteration. Clearly define your approach,

challenges, and assessment.

Questions:

$1.$ Student $1$: The quick sort that is provided will run into an infinite loop around $14$k

elements. So$,$ can we just rewrite the quick sort?

$2.$ Student $2$: Did you get Stack Overflow? If you did, then it's because the default $1$mb of

memory storage isn't enough to process more than $14$k elements. I had the same

problem, and I fixed it by changing the memory storage in my IDE to $3$mb under VM

argument using the command $-$Xss$3$m$.$

$3.$ Student $3$: it only has issues during In Order and Reverse Order. I would imagine this is

because the pivot selection for this implementation is resulting in there being one side

that is very small and one that is very large when the list is sorted.

$4.$ Student $4$: I changed the pivot to $($front $+$ back$)/2$ instead of front. This is the best for our

project in my opinion because it is easy to calculate and solves the issues we are

having.

$5.$ Student $5$: Are you sure it's the sorting algorithm? Me and my buddy found that it was

the limits of our printing functions preventing us from checking sort. Once I switched to

making my check a for loop of println's, it was able to sort and print at least a billion

elements.

Primitive vs Generic Type: Box primitive int to Integer object for algorithms requiring

generic

T A S K L IST

You are required to complete the following activities by the deadlines specified and submit the

appropriate deliverables through eLearning.

ACTIVITY

$1.$ Implement all $4$ sorting algorithms to produce the output for each data type applied to

each sorting algorithm. The $2$ data types $($InOrder$,$ and ReverseOrder$)$ will be used as

input to each algorithm capturing the experimental results.

$2.$ For each data type, determine the best and the worst algorithm based on comparisons,

movements, and the time it took to sort the list or any additional criteria you can come

up with.

$3.$ Prepare a report discussing $1)$ how each sorting algorithm works, the best, average and

worst$-$case times for each algorithm. $2)$ all experimental results and how each data type

determined the best and the worst algorithm for that data type

Zip all the Java Files, not the class files, and submit on eLearning under Assignment Section.

G U I D E L I N E S

You will be graded according to the following guidelines:

$$ You are required to submit files through eLearning by the specified deadline. You can earn a

maximum of $100$ points.

$$ If the files do not compile, you will receive a $0$ for the program.

$$ You are graded primarily on the design of your class and the adequate testing of your class.

Poor design or inadequate testing will result in loss of points.

$$ Your files should be adequately commented. Up to $-15$ points will be deducted for poor

indentation and documentation.

Please follow these steps for Project $1$:

$1.$ Implement all four provided pseudocodes in either Java or C$++.$

$2.$ Test each implementation with a small list of numbers to verify that the sorting works correctly.

$3.$ Generate a list of $50,000$ random numbers and store them in an array.

$4.$ Test your implementations using this $50,000-$element list to confirm that the sorting is accurate.

$5.$ Ensure that you use the same randomly generated list for each algorithm.

$6.$ Add probing code to count the number of comparisons and movements:

$-$ Comparison refers to comparing two elements in the list.

$-$ Movement refers to swapping two elements using a temporary variable.

$7.$ Note that loop counters $($in $`$for$`$ or $`$while$`$ loops$)$ do not count as comparisons or movements.

$8.$ In your report:

$-$ Include the number of comparisons made by each algorithm, ranked from best to worst.

$-$ Include the number of movements made by each algorithm, ranked from best to worst.

$-$ Include the time taken by each algorithm $($in nanoseconds$),$ ranked from best to worst.

After completing the above steps, repeat the process with the same algorithms, but this time use a pre$-$sorted $($ReverseOrder$)$ list in ascending order as the input.