Create a Python program that will measure the execution time of your Bubble Sort code for varying problem sizes, and then plots the performance results using Python's matplotlib.pyplot module. Your code must contain two new Python Functions: (1) contains your Bubble Sort code from example #3, and (2) tests if a Python List is sorted in ascending order and returns True if so or False otherwise. Use Python's time module to obtain time values for the purposes of computing elapsed time.

Use Example #3 code as the starting point

Create Python functions that:

1. Verify if a list is sorted in ascending order, and return True if so, False otherwise. This function takes a single input argument, the list to be checked. Your main() code should invoke this function to test whether or not the List is sorted before and after the sorting process. We are using this function to verify that your sort is correct, as opposed to doing visual inspection of the entire list, as we did in Example #3.

2. Perform sorting of a Python List into ascending order. Your Bubble Sort routine should be transplanted now to a function. It takes a single input argument, the list to be sorted. Your main() code should invoke this function to sort the List. This function must contain a return statement, but does not return a value to the main() code.

Problem sizes:

For development and testing, please use N=[128, 256, 512, 1024, 2048, 4096] for your problem sizes.

For the "actual homework runs", please use N=[128, 256, 512, 1024, 2048, 4096, 8192, 16384] as your problem sizes. (The 8K run could take 6-10 seconds, and the 16K run could take 30-60 seconds.)

You will need to modify your Example #3 code to iterate over these different problem sizes.

Creating Lists to be Sorted:

Use the Python random module and a hard-coded seed value to generate random numbers in the range [0..9999]. You can use your source from Example #3, with modifications as needed for varying problem sizes and new random number ranges.

Measuring Runtime Performance

Use the Python time module to "look at the clock" immediately before calling your Bubble Sort function, and again immediately afterwards. Accumulate the elapsed time, measured as the difference of these two clock readings, into a separate Python List.

Visualization of Runtime Performance

Use Python's matplotlib.pyplot module to generate a plot showing problem size on the x-axis and runtime in milliseconds on the y-axis. Your chart should have a meaningful text title as part of the chart. The plot should include x-axis and y-axis labels that indicate what we're looking at, and use custom x-axis tick marks and labels, along with log scaling.

This is the Example #3 code provided as reference:

from datetime import datetime import random # bubble sort method which sort the lst in ascending order def bubbleSort(lst): s = len(lst) for i in range(s-1): for j in range(0,s-i-1): if(lst[j] > lst[j+1]): lst[j],lst[j+1] = lst[j+1],lst[j] # display method to show the content of list # 10 numbers per line def display(lst): i = 0 while(i=N): break print() # print your name print("your name") # print todays date and time date = datetime.now().strftime("%d-%m-%Y %H:%M:%S") print(date) # take input for N N = int(input("Enter N: ")) # take input for S S = int(input("Enter S: ")) # seed random with S random.seed(S) # make a empty list lst=[] # append list with random number for i in range(N): lst.append(int(random.random()*100)) # print unsorted array print("Unsorted array: ") display(lst) # sort the list bubbleSort(lst) # print unsorted array print(" Sorted array: ") display(lst)