[SOLVED] Comp 3270 assignment 1 – asymptotic analysis of sorting algorithms

To empirically evaluate 4 sorting algorithms and verify their theoretical upper
bound. The sorting algorithms we will evaluate are: merge sort, quick sort,
insertion sort, and selection sort.A starter code with helper functions and
implementations of 2 algorithms (selection sort and merge sort) has been
provided. Your task is to implement the remaining two sorting algorithms
(quick sort and insertion sort) and perform the following empirical analyses.You will run a specific algorithm on three different types of arrays – sorted,
random, or constant array of a given size n. The provided starter code will
generate the input arrays for your analysis. The starter code will take as input
three command line arguments in the following order:1. Type of input array. You have three choices: ‘r’, ‘c’, and ‘s’ that
correspond to random, constant and sorted arrays, respectively. If
invalid values are given, it will default to a random input array.2. Size of the array to generate and analyze. It must be a positive number
greater than zero. It will default to 10 if an invalid value is provided.3. Sorting algorithm to use. You have four choices: ‘m’, ‘i’, ‘s’, and ‘q’ that
correspond to merge sort, insertion sort, selection sort, and quick sort,
respectively. If an invalid value is given, it will default to quick sort.If an incorrect number of arguments are given or if an integer is not provided
for the second command line argument, it will default to running quick sort
on a random input array of size 10. For stable computation of timing, the
starter code will run each algorithm three times and provides the median of
the three runs. For accurate timing, ensure that there are no other processes
running on the machine while you conduct your analysis. The output timing
will be in nanoseconds.2. Deliverables:
There are two deliverables for this programming project: (i) the completed
code with the two sorting algorithms completed in the functions marked with
“TODO”, and (ii) a report with your analysis clearly marked with two sections
– “Results” and “Analysis.” More details about what is expected to be
presented in each section are provided below.2.1 Results
Run each of the four sorting algorithms on constant, sorted, and random
arrays that are powers of 10. For each of the twelve cases, you should record
the following:• Nmin: the smallest power of 10 array size that takes 20 milliseconds or
more per run to sort.• Nmax: the largest power of 10 array size that takes 10 minutes or less
per run to sort (30 mins for all 3 runs), or the largest input size you can
successfully sort if no input took more than 30 minutes total.
• Tmin: the time to sort an array of size Nmin.
• Tmax: the time to sort an array of size Nmax.You should report your results in a table. Your table should have 12 rows and
5 columns. Each row must have a label with 2 letters, where the first
corresponds to the algorithm (Merge, Quick, Insertion, or Selection) and the
second corresponds to the array type (Sorted, Random, or Constant). For
example, SS corresponds to Selection sort run on a Sorted array. An
example table is shown below.Note that the goal of this project is to find a Nmin and Nmax that are sufficiently
far apart that the growth rate of the time complexity can be approximated
using the timing and input size ratios. The descriptions of Nmin and Nmax given
above are just to give you a reasonable idea of how to find good array sizes;
finding the exact value of Nmin that takes 20 milliseconds to run, for instance,
is not critical. You may have to check values of up to 1 billion to find Nmax.2.2 Analysis
In this section, you will estimate the complexity of the four algorithms by
comparing the ratio between Tmin and Tmax to ratios representing the
complexity of the algorithm. Specically, you should compute f(Nmax) = f(Nmin)
for f1(n) = n, f2(n) = n ln(n), and f3(n) = n2
.You should round to the nearest
integer when computing these ratios. Finally, you should label each
experiment according to the ratio Tmax=Tmin most resembles.For example, if you get Nmin= 10 and Nmax = 100, your ratios would be:
• f1(Nmax)/f1(Nmin) = 100/10
• f2(Nmax)/f2(Nmin) = (100*ln(100))/
(10*ln(10))
• f3(Nmax)/f3(Nmin) = 1002
/102You should then label the algorithm based on which of these three ratios Tmax
= Tmin is closest to. As part of your report, you should create a table that
includes the computed ratios as well as the behavior of the algorithm (Linear,
n lg n, or Quadratic), across all 12 experiments.An example is given below:
Your report should contain a summary of (1) how your results compare
to the theoretical analysis for all four algorithms, and (2) why your
results make sense or are surprising. You should spend more time
explaining your results when they are unusual or unexpected.