Please Complete the following code to plot the required graphs in python . Read
ID: 3747547 • Letter: P
Question
Please Complete the following code to plot the required graphs in python. Read the details below.
Consider the Mergesort and Insertion Sorting Algorithms. Implement these algorithms in Python. Given an input n each code should return the number of comparisons (nc) performed. Run the codes for three dierent cases: a sorted array, a reversed array and a randomly created array. Run the Insert and Mergesort codes for n = 10, 30, 100, 300, 103, 3×103, 104, 105. Create two plots using a graphing tool you have used. The rst plot should show the results of Insertion Sort and Mergesort using a log×log scale (on the x-axis log(n), on the y-axis log(nc)). You can verify the theoretical behaviour of Insertion Sort and Mergesort from this plot. The second plot should show the results of Mergesort using log scale on the x-axis only. The y-axis should show the values of nc/n.Again show the curves for random, sorted and reversed inputs that you create as described above. In both plots, explain the shape of the graphs you observe.
Insertion sort code
def insertion_sort(a):
"""insertion_sort(a) -- sorts a by insertion sort
Returns number of comparisons"""
n_comparisons = 0
for i in range(1,len(a)):
j = i-1
n_comparisons = n_comparisons + 1
while a[j] > a[j+1]:
n_comparisons = n_comparisons + 1
# swap a[j] and a[j+1]
temp = a[j]
a[j] = a[j+1]
a[j+1] = temp
j = j-1
if j < 0:
break
return n_comparisons
if __name__ == '__main__':
a = [3,8,2,0,1,6,5,8,4,12,7,9]
a_old = a.copy()
print('Number of comparisons =',insertion_sort(a))
print('a =',a_old)
print('sorted a =',a)
------------------------------------------------------------------------------------------------
def mergesort1(a):
"""mergesort1(a) -- returns sorted list of a's elements
Uses mergesort algorithm applied to lists using append
Returns pair of sorted list and number of comparisions"""
n = len(a)
if n <= 1:
return a,0
else:
m = n // 2
a1 = a[0:m]
a2 = a[m:n]
b1,nc1 = mergesort1(a1)
b2,nc2 = mergesort1(a2)
b, nc3 = merge1(b1,b2)
return b,(nc1+nc2+nc3)
def merge1(l1,l2):
"""merge1(l1,l2) -- returns merged list containing entries of lists l1
& l2
Returns pair of the merged list and the number of comparisons between
items"""
l = []
n1 = len(l1)
n2 = len(l2)
i1 = 0
i2 = 0
n_comparisons = 0
while i1 < n1 and i2 < n2:
n_comparisons = n_comparisons + 1
if l1[i1] <= l2[i2]:
l.append(l1[i1])
i1 = i1 + 1
else:
l.append(l2[i2])
i2 = i2 + 1
while i1 < n1:
l.append(l1[i1])
i1 = i1 + 1
while i2 < n2:
l.append(l2[i2])
i2 = i2 + 1
return l,n_comparisons
if __name__ == '__main__':
a = [3,8,2,0,1,6,5,8,4,12,7,9]
a_old = a.copy()
a,nc = mergesort1(a)
print('Number of comparisons =',nc)
print('a =',a_old)
print('sorted a =',a)
------------------------------------------------------------------------------------------------------------
import matplotlib.pyplot as plt
import math
def FirstPlot(x,y,c):
logx = []
logy = []
for i in x:
logx.append(math.log10(i))
for i in y:
logy.append(math.log10(i))
print('Plotting now!')
plt.plot(logx,logy,label=c)
plt.legend()
print('Done plotting!')
if __name__=='__main__':
#First Plot
plt.figure("First Plot")
nlist = [10,30,100,300]
nc_sorted_MergeSort = [30,258,2538,23386]
FirstPlot(nlist,nc_sorted_MergeSort,'Sorted Array-MergeSort')
plt.show()
print('done')
Explanation / Answer
The Merge Sort
We currently direct our concentration toward utilizing a gap and overcome procedure as an approach to enhance the execution of arranging calculations. The primary calculation we will think about is the consolidation sort. Union sort is a recursive calculation that persistently parts a rundown into equal parts. In the event that the rundown is unfilled or has one thing, it is arranged by definition (the base case). On the off chance that the rundown has in excess of one thing, we split the rundown and recursively conjure a union sort on the two parts. Once the two parts are arranged, the basic activity, called a consolidation, is performed. Blending is the way toward taking two littler arranged records and joining them together into a solitary, arranged, new rundown. Figure 10 demonstrates our commonplace illustration list as it is being part by mergeSort. Figure 11 demonstrates the straightforward records, now arranged, as they are converged back together.
The mergeSort work appeared in ActiveCode 1 starts by asking the base case question. On the off chance that the length of the rundown is not exactly or equivalent to one, at that point we as of now have an arranged rundown and no all the more preparing is important. On the off chance that, then again, the length is more prominent than one, at that point we utilize the Python cut activity to extricate the left and right parts. Note that the rundown might not have a much number of things. That does not make a difference, as the lengths will vary by at generally one.
def merge_sort(a_list):
print("Splitting ",a_list)
if len(a_list)>1:
mid = len(a_list)//2
left_half = a_list[:mid]
right_half = a_list[mid:]
merge_sort(left_half)
merge_sort(right_half)
i=0
j=0
k=0
while i < len(left_half) and j < len(right_half):
if left_half[i] < right_half[j]:
a_list[k]=left_half[i]
i=i+1
else:
a_list[k]=right_half[j]
j=j+1
k=k+1
while i < len(left_half):
a_list[k]=left_half[i]
i=i+1
k=k+1
while j < len(right_half):
a_list[k]=right_half[j]
j=j+1
k=k+1
print("Merging ",a_list)
a_list = [54,26,93,17,77,31,44,55,20]
merge_sort(a_list)
print(a_list)
The Insertion Sort
The inclusion sort, albeit still O(n2), works in a somewhat extraordinary manner. It generally keeps up an arranged sublist in the lower places of the rundown. Each new thing is then "embedded" once again into the past sublist to such an extent that the arranged sublist is one thing bigger. Figure 4 demonstrates the addition arranging process. The shaded things speak to the arranged sublists as the calculation makes each pass.
../_images/insertionsort.png
We start by expecting that a rundown with one thing (position 0) is now arranged. On each pass, one for every thing 1 through n1, the present thing is checked against those in the officially arranged sublist. As we think once again into the effectively arranged sublist, we move those things that are more noteworthy to one side. When we achieve a littler thing or the finish of the sublist, the present thing can be embedded.
Figure 5 demonstrates the fifth go in detail. Now in the calculation, an arranged sublist of five things comprising of 17, 26, 54, 77, and 93 exists. We need to embed 31 once again into the officially arranged things. The principal correlation against 93 causes 93 to be moved to one side. 77 and 54 are likewise moved. At the point when the thing 26 is experienced, the moving procedure stops and 31 is put in the vacant position. Presently we have an arranged sublist of six things.
../_images/insertionpass.png
The usage of insertionSort (ActiveCode 1) demonstrates that there are again n1 goes to sort n things. The cycle begins at position 1 and travels through position n1, as these are the things that should be embedded again into the arranged sublists. Line 8 plays out the move activity that moves an incentive up one position in the rundown, making room behind it for the addition. Keep in mind this is anything but an entire trade as was performed in the past calculations.
The most extreme number of examinations for an addition sort is the total of the main n1 whole numbers. Once more, this is O(n2). Be that as it may, in the best case, just a single correlation should be done on each pass. This would be the situation for an effectively arranged rundown.
One note about moving as opposed to trading is likewise imperative. When all is said in done, a move task requires roughly 33% of the preparing work of a trade since just a single task is performed. In benchmark examines, inclusion sort will indicate great execution.
def insertion_sort(a_list):
for indx in range(1,len(a_list)):
current_value = a_list[indx]
position = indx
while position>0 and a_list[position-1]>current_value:
a_list[position]=a_list[position-1]
position = position-1
a_list[position]=current_value
a_list = [54,26,93,17,77,31,44,55,20]
insertion_sort(a_list)
print(a_list)