easy coding c hw

ProgrammingAssignment.pdf

Design and Analysis of Algorithms Nov. 2, 2020

Programming Assignment

Email the source code of your program, along with the PDF document

containing your running time analysis (see below), to [email protected]

by Nov 11, 2020 at 11:59PM.

Implement a computer program (in either Python, Java, or C/C++) that allows the

user to run the three sorting algorithms presented in class: Bubble Sort, Mergesort

and either Quicksort or Heapsort. Allow the user to choose the size of the input

array. Your program should fill out the array with random numbers and then run the

three algorithms on such an array.

(a) Your program should be able to check whether the sorted (output) arrays

obtained by each algorithm are equal.

(b) If the output arrays are not the same, that will signal the errors in your

implementation. Otherwise, print out the first 20 elements of the output

sorted array.

comparisons performed by each algorithm.

(d) Report the CPU time for each algorithm side by side using clock() (or JAVA’s

System.currentTimeMillis())

(e) Repeat the above process for arrays of sizes i * 1,000 where i =1, 5, 10, 15, 20,

25, 30 (you are also free to choose your own test sample sizes, if you want).

Create a separate PDF document that summarizes the output of your

algorithm in the table below.

1,000 5,000 … 30,000

Bubble Sort # comps: time:

# comps: time:

… # comps: time:

Mergesort # comps: time:

# comps: time:

… # comps: time:

Quicksort (or Heapsort)

# comps: time:

… # comps: time:

(f) Include in the same document any observations regarding the running times

of your three programs. For instance, explain how the results of your analysis

relate to the asymptotic running times of the three algorithms.

Your source code should be readable, properly formatted and spaced with sufficient

documentation (at least 25% of lines should be documented). Follow the best

programming practices in object oriented design and naming of methods and

variables.