python3

Part 2a Searching & Sorting In this part of the tutorial you will be writing searching and sorting functions, and evaluating the amount of clock-time that they require to run. You are free to use any code provided in lecture in your answers, however, you should take this opportunity to understand any code that you use. In a single python file, implement the following searching and sorting functions as taught in class. A linear search that finds the smallest element in a given input list. A binary search that returns the index of the key in the list if its found. A bubble sort that takes a list and sorts it in place. You will also need to make a function that takes in an integer, n, and generates a list of n random numbers. Write a main() function to test your algorithms and make sure they work. Part 2b Clock time To evaluate the actual run time (so-called clock-time) of a piece of code youll need to import the timeit module. Inside the timeit module is a function called default_timer() that returns the number of seconds that have elapsed since "the epoch" (12:00am Jan 1st 1970). While the epoch itself is an arbitrary number, we can use this function to determine how long our code runs by taking two samples: one before our code, and one after, and then calculating the difference. before = timeit.default_timer() #some code to run after = timeit.default_timer() elapsedTime = after - before Use this pattern to time the execution of each of the algorithms you wrote in Part 1 to answer the following questions: If the size of the input list doubles how much longer does Linear Search take? If the size of the input list increased by 10x, how much longer does Linear Search take? If the size of the input list doubles how much longer does Bubble Sort take? If the size of the input list increased by 10x, how much longer does Bubble Sort take? Do these changes in values match the O(n) and O(n2 ) expected costs of these algorithms? Note: the amount of clock-time it takes to run a given algorithm will differ from computer-tocomputer and even from run-to-run. So your answers to the questions above will be estimates of the time change. For example: If you run algorithmX() on a list of size 1000 and it takes 0.12 seconds. Then you run the algorithm on a list of size 10000 and it takes 1.3 seconds. The input size changed by a factor of 10x. The run-time changed by a factor of: 1.3/0.12 = 10.833333, so roughly (also) 10x longer. The time it takes to run your algorithm is affected by other things running on your computer, including background processes. So, run your code a few times to make sure your answers seem consistent. (Also, be sure not to time the function that generates your random lists, as that may skew your results) Sample program output: Linear search on a list of size 1000: _______________ seconds Linear search on a list of size 2000: _______________ seconds Linear search on a list of size 10000: _______________ seconds Bubble Sort on a list of size 1000: __________________ seconds Bubble Sort on a list of size 2000: __________________ seconds Bubble Sort on a list of size 10000: _________________ seconds Additional challenge: what do you think is the BigO class of your searchGrid() function? Make several random grids of different sizes and time them to verify your prediction. Additional challenge: time several runs of the binarySearch()algorithm, and explain why there is only a small increase in clock-time each time the input size is doubled.