Input: A sequence of n numbers a1,a2,,an Output: A reordering a1,a2,,an of the input sequence such that a1a2an. (1) Solve this problem by implementing InsertionSort algorhtm. Display the result for the given input A. - Implement the InsertionSort algorithm using the INSERTION-SORT pseudocode in the lecture slides. - Use the input A generated in the "1. Generate inputs" cell. (2) In this task, we will compare the running times of your InsertionSort implementation for three different types of inputs: random, sorted in ascending order, and sorted in descending order, with the following input sizes: n=[100,1000,2000,3000,4000,5000]. That is, each type of input will have six different sizes. (Refer to the "1. Generate inputs" cell for a reference). - First, measure the running time for all input sets. For example, there will be six running time measurements for the random set. - Then, compare the results by plotting them as a graph. (Refer to the "3. Plot" cell for a reference) (3) Based on the results from (2), analyze and explain the trend of running times for the different types of inputs. - Use asymptotic notations in a Markdown cell to present your explanation. (Refer to the "4. Write equations with Markdown" cell for a reference) 1. Generate inputs 2. Measure a running time start =timer() YourAlgorithm(input_A) end = timer() print(end-start) \# time unit [seconds] 3. Plot \# As an example, Let's assume that 'elapsed_time_random' stores the running time of \# 6 different size inputs, e.g., randomLy generated input elapsed_time_random =[1,10,160,1600,10000,100000] elapsed_time_asc =[1,5,50,500,5000,50000] \# Plot elapsed_time_random plt.plot(size, elapsed_time_random, color="blue', label='Running time for random input') plt.plot(size, elapsed_time_asc, color='green", label="Running time for asc input') plt.title("Running time of algorithms") plt.xlabel("Input size") plt.ylabel("Running time[seconds]") plt.grid(True) plt.legend() plt.show() 4. Write equations with Markdown syntax - Examples: You can type (n2),(n2), and O(n2) - References http:/ftug.ctan.org/info/undergradmath/undergradmath.pdf