MATH2920 COMPUTATIONAL MATHEMATICS, EXERCISES 8, 2023/24
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
MATH2920 COMPUTATIONAL MATHEMATICS, EXERCISES 8, 2023/24
|
Instructions . The template le xxyyzz_8.py and the mergesort code mergesort.py are available on Minerva. . When you submit your work, submit only the completed template le, which will contain your code and any answers written as comments. Your program should generate all necessary graphs when it is run. . Your submitted work should import only the functions which are included in the template le already (namely shuffle, perf_counter, and the module pyplot). Do not use any other imported functions. . Do not change the function names. . Your le should take at most 10 seconds to complete running. . Before submitting your work, you are advised restart the Python kernel on your computer, and then check that your script runs without crashing. . Upload your submission to Assessment 8 on Minerva by 9am Monday 27 November. This workshop counts as 20% towards your nal grade. |
8.1. Sorting experiments. Testing. In this workshop we will compare the performance of
di erent sorting algorithms. We will be sorting very long lists in this workshop, so be sure to print your tests only on short lists!
First we need to generate some shu ed lists to sort. The shuffle method from the random module is used to randomise a list. For example the code
from random import shuffle
mylist = list(range(1, n+1))
random.shuffle(mylist)
will produce a randomly shu ed list of all the integers from 1 to n inclusive.
The following code provides away to generate list of di erent lengths (in this case of length 2i for di erent i) with the time it takes to sort each:
listlengths = []
sorttimelist = []
for i in range(1, 5):
listlengths.append(2**i)
mylist = list(range(2**i))
shuffle(mylist)
# here define sorttime (how long it takes to sort the list)
sorttimelist.append(sorttime)
To test how long a sorting algorithm takes to sort a large list of numbers we will import and use the perf_counter() function from the time module. This function returns the number of seconds since some reference time. For example, the code
time_start = time.perf_counter()
selectionsort(mylist)
time_end = time.perf_counter()
sorttime = time_end - time_start
will store the time needed for selection sort to sort mylist. You are only timing the sorting process so be careful not to include the time to create the unsorted list in your timing!
8.2. Labelling lines. Of course, whenever we plot a graph we should label the axes. But also
when we have multiple sets of data on a single set of axes, the reader needs to be able to tell what is what. This is easily done using matplotlib's labels and legends:
x, data1, data2 = [0,1,2], [1,2,3], [1.5, 2.5, 4]
plt.plot(x, data1, label= 'First Set Of Data' )
plt.plot(x, data2, label= 'Second Set Of Data' )
plt.legend(loc= 'upper left' )
|
Assessed Coursework 2, Week 8 Part A: Sorting The code in section 8.3 below (also available on Minerva) implements the merge sort algorithm, you may use this in your work. (1) Use perf_count and the other ideas from 8.1 above to generate a list of data, where the ith entry is the time tm (i) necessary for merge-sort to sort lists of randomly chosen elements of length 2i for i = 1, . . . , 10. (2) Plottm (i) against 2i on a loglog plot. Brie y explain (as a comment) what the graph says about merge-sort's speed, using big-O notation. (3) Write a function insertionsort(somelist) that applies the insertion sort algorithm described in lectures to sort a list. (You should use the pop and insert commands as described in the lecture notes.) (4) Use this to nd the times tI (i) for lists of the same length as in (1). Add tI (i) to your graph (on the same axes as above), and write a comment on-what this says about the speed of insertion sort, in big O notation. (5) Write a function countingsort(mylist) which implements counting sort for lists of non-negative integers, using the algorithm described in lectures. (6) How e cient is countingsort compared to the other algorithms you have investigated? Can you provide one example each of lists of non-negative integers where counting sort would be (a) very e cient (b) very ine cient? Write your answer as a comment. |
8.3. Merge sort code. One implementation of merge sort is the following.
def interleave(list1 , list2):
''' this interleaves two already sorted lists '''
newlist = []
while len(list1)+len(list2)>0:
if len(list1)==0:
newlist. extend(list2)
list2 = []
elif len(list2)==0:
newlist. extend(list1)
list1 = []
else:
if list1[0]
newlist. append(list1. pop(0))
else:
newlist. append(list2. pop(0))
return newlist
def mergesort(mylist):
if len(mylist)<=1:
return(mylist)
else:
midpoint = len(mylist)//2
firstpart = mylist[:midpoint]
secondpart = mylist[midpoint:]
sortedfirst = mergesort(firstpart)
sortedsecond = mergesort(secondpart)
full_list = interleave(sortedfirst , sortedsecond) return(full_list)
|
Part B: Shu ing (7) Write a function triple_riffle(mylist) which takes as input a list (which for convenience we will always take with length a multiple of 3) and outputs the result of a 3-way ri e shu e as described i the lecture notes. For example: an input of range(9) should output [6,3,0,7,4,1,8,5,2].
(8) Write a function triple_riffle_repeat(mylist,n) which takes as input a list (again with length a multiple of 3) and outputs the result of doing a 3-way ri e shu e n times.
(9) Write a function period(m) which takes as input a number m (which we will always take as a multiple of 3) and outputs the smallest positive integer n so that triple_riffle_repeat(list(range(m)),n) == list(range(m)).
(10) Discuss, with evidence, the outputs of your function period for di erent values of m, writing your answer as a comment. |
Non-assessed Work. This section is not for submission.
. Extend your analysis of sorting algorithms to include bubblesort, selectionsort, and Timsort (Python's inbuilt method). Add these to your plots and compare their speeds.
. Write a function multiway_shuffle(mylist,m) which takes a list (whose length is a multiple of m), splits it into m equal piles, and then ri es them together. What can you say about the periods of these shu es?
2023-11-21