Assignment due in less than 12 hours, need it completed.
ACIT 1515 Assignment 4 Due Apr 07, 2019 – 11:59 PM Orchestrate Sorting Part I (1% mark). Write a program that based on the size of your input list pick a sorting algorithm of the following options. 1- Selection sort 2- Insertion sort 3- Quick Sort 4- Random sort (that we did in class) Random sort: import random int_list = input('Enter a list of integers separated by a space: ') int_list = int_list.split() int_list = list(map(int, int_list)) print(int_list) def randomsort(numbers): # while list is not sorted while sorted(numbers) != numbers: # choose 2 random elements in list i = random.choice(numbers) j = random.choice(numbers) # retrieve indexes of 2 elements and switch them a, b = numbers.index(i), numbers.index(j) numbers[a], numbers[b] = numbers[b], numbers[a] print(numbers) randomsort(int_list) For picking the right choice, you should think of computation time complexity and big O notation that we discussed in class. For example, think of the small lists, which one of the above sorting algorithms are better, and for the bigger ones which one could be the right candidate, for medium sized lists which one….and so on. You can also think of coming up with a method that figures out what percentage of a list needs sorting and apply the right algorithm accordingly. Think about it. Have some discussions with your fellow friends about your design. You can read this article to get some ideas: https://pmihaylov.com/sorting-algorithms/ Or this one: http://www.cscjournals.org/download/issuearchive/IJCSS/Volume7/IJCSS_V7_I3.pdf#page=35 Part II (3% mark). Performance measurement: Automate your code such that it measures the lists of following element sizes. You should measure time that it took the particular sort algorithm to sort the following list with elements as described below. For every row and column you should run the code 1000 times and take the average time of 1000 runs for every box in the following table. For example, for quick sorting, run the code 1000 times for when the number of elements are 100 and record the average time. Element(s) Selection sort Insertion sort Quick sort Random sort 1 10 100 1,000 10,000 100,000 1 million 10 million 100 million 1 billion 10 billion You must create the table above by automating your Python code (2% mark of part II is specified for correct and scalable automation effort). In essence, your code should work with a push button. All of the above should happen by automation. At the end of the program the above Table must be created. If your sorting effort in any of the boxes above is taking more than 30 minutes, you should quit and record >30min in the box. For example, I am 120% sure that your program would have hard time sorting with random sort that we implemented in class for elements of a list bigger than 100. So you’d have to record >30min if it is taking longer than 30 min for every epoch. You’d need to report the speed of your computer CPU and the RAM memory space of your computer. For example, you should report that your computer is running at 3.2 GHz, Duo core, with RAM 32 GB, running Windows 10. Scientifically it is important to report your computer specifics so that if someone wants to reproduce your results with the same exact computer, they should be able to do so. You can measure the run-time of a code snippet using the following link: https://pythonhow.com/measure-execution-time-python-code/ Use the above link as an example. I am ok if you have a library that captures timing in a more efficient way. Part III (1%). Write code to draw the table above. Use legend and different colors for showing different searching algorithms. Use x axis for number of elements in logarithmic scale, and y axis for the time scale. Page 2 of 3