(Average time complexity) the Time Complexity (TC) considered is generally referred to as the worst-case (WS) TC.
(Average time complexity) the Time Complexity (TC) considered is generally
referred to as the worst-case (WS) TC. Note that WS-TC reflects only the performance of an
in the worst case, as the name suggests, which does not necessarily capture its practical performance.1 In
contrast to WS-TC, another related concept, called Average Time Complexity (AV-TC), captures the average
performance of an algorithm over a large number of pre-set random instances. A typical way to evaluate
the AV-TC of a given algorithm is to first identify a class of instances and then output the average running
time over them. In the context of sorting algorithms when input size is n, we can get testing instances by
generating a given number of random permutations over [n] = {1,2,3,...,n}.
Please implement the following algorithms, namely, (1) Cocktail Sort (CS), (2) the complementary reversion
of CS (CS-R), (3) Merge Sort parameterized with an integer k = 2 (MS(k = 2)), (4) Merge Sort parameterized
with an integer k = 3 (MS(k = 3)), (5) Merge Sort parameterized with p = 2/5 (MS(p = 2/5)), (6) Quick
Sort (QS, the basic version), and (7) Randomized Quick Sort (R-QS). For each given n ∈ {102,103,104,105},
please run each algorithm ALG on K = 1000 randomly generated permutations over [n] and then output
the average as the empirical performance on an input of size n, denoted by τ(ALG,n). Please plot all values
τ(ALG,n) and see how the average running time of the seven sorting algorithms increases as the input size
n. You are encouraged to test larger values of n and K (as large as possible), as long as the total running
time is acceptable to you based on your own PCs. Note that the average running time should be measured
in milliseconds or seconds.
Trending now
This is a popular solution!
Step by step
Solved in 2 steps
