 # Untitled

a guest
Jan 21st, 2019
60
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #!/usr/bin/env python
2. # coding: utf-8
3.
4. # In:
5.
6.
7. #Luis Gonzalez 21/01/2019 Code Session 2.1 - Mergesort and recurrences
8. import random
9. # Here I imported the relevant python dependencies that I used for this algorithm. I only imported random from the standard Python Libarary in this case
10.
11.
12. # In:
13.
14.
15. #I first declar the function "merge" and pass the values of start,middle,length rather than p,q,r respectivly as the readings mentioned. I did this change becuase it was easier for me to conceptualize the code in this form rather than with the way the book had it written
16. def Merge(A,start,middle,length):
17. global count
18. #I created a global variable this time rather than appending the counter in list form. This enables me to retrive the counter in other places in the code
19. n1 = int(middle-start+1)
20. #I created the length of the first list by subratinc the start of the list minus the middle
21. count =count+1
22. #After each line code I increase the counter by one
23. n2 = int(length-middle)
24. #I then created the length of the second list by subtrating the total lenght of the list minus the middle
25. count =count+1
26. Left = *(n1+1)
27. #Here I assigne the value of the left list to the number I obtained previously
28. count =count+1
29. Right = *(n2+1)
30. # I do the same things as in the left assignation
31. count =count+1
32. for i in range(0,n1):
33. count =count+1
34. Left[i] = A[start+i]
35. #Here I basically assign the values of the array to the new Left list
36. count =count+1
37. for j in range(0,n2):
38. count =count+1
39. Right[j] = A[middle+1+j]
40. #Here I assign the values of the array to the new Right list
41. count =count+1
42. Left[n1] = 9999999
43. #I then make the last number of the list extreamly large in order to identify when the code should stop
44. count =count+1
45. Right[n2] = 9999999
46. #I do the same as the previous step
47. count =count+1
48. i = 0
49. count =count+1
50. j = 0
51. #Here I made the counters 0 again in order to use them in he next loop
52. count =count+1
53. for k in range(int(start),int(length)+1):
54. count =count+1
55. if Left[i]<= Right[j]:
56. #Here I compare the values of each lists and "append" the smalles value to the original list
57. count =count+1
58. A[k] = Left[i]
59. count =count+1
60. i=i+1
61. #Increase i by 1
62. count =count+1
63. else:
64. count =count+1
65. A[k] = Right[j]
66. count =count+1
67. j=j+1
68. #Increase j by 1
69. count =count+1
70. return count
71. # I finally returned the value of count in order to use it outside of the function
72.
73.
74. # In:
75.
76.
77. #I created a new function called MergeSort
78. def MergeSort(A,start, length):
79. global count
80. # I once again assigne the value of count as a global variable
81. count =count+1
82. if start < length:
83. #This part checks that the array is not a single sigit as that would make this if statement false and then return the count only
84. count =count+1
85. middle = (int(start+length)//2)
86. #I assigned the value of middle of the array simply dividing the length of the array plus the start.
87. #I used the "//" division rather than "/" because in Python 3, this bring a float and I needed an integer
88. count =count+1
89. MergeSort(A,start,middle)
90. #I call the function on the new list to further divide it
91. count =count+1
92. MergeSort(A,middle+1,length)
93. #I call the function on the other new list to further divide it
94. count =count+1
95. Merge(A,start,middle,length)
96. #I finally start merging once I have the start middle and length
97. count =count+1
98. return count
99.
100.
101. # In:
102.
103.
104. count = 0
105. #I initialize the counter
106. array = []
107. # I create an empty array
108. count =count+1
109. for x in range(6):
110. #I made a simply loop to append 6 randomly generated numbers
111. count =count+1
112. array.append(random.randint(1,99))
113. count =count+1
114.
115. print("Initial Array of 6 numbers")
116. print(array)
117. #I print the initial array
118. MergeSort(array,0, len(array)-1)
119. # I call the function on the array and relevant values
120. count =count+1
121. print("Sorted Array of six numbers")
122. print(array)
123. print("Total count")
124. print(count)
125. # Finally I printed the values generated at the end.
126.
127.
128. # In:
129.
130.
131. import matplotlib.pyplot as plt
132. #I first Imported the relevant libarary to use which in this case is matplotlib
133.
134. # Here I called the function with 5 different array lengths in order to create a graph of the relationship between numbers in an array and time steps.
135. array1 = []
136. array2 = []
137. array3 = []
138. array4 = []
139. array5 = []
140.
141. # I looped and appended random values to the lists while looping 2x more numbers in each list
142.
143. for x in range(4):
144. count =count+1
145. array1.append(random.randint(1,99))
146. count =count+1
147.
148. for x in range(8):
149. count =count+1
150. array2.append(random.randint(1,99))
151. count =count+1
152.
153. for x in range(16):
154. count =count+1
155. array3.append(random.randint(1,99))
156. count =count+1
157.
158. for x in range(32):
159. count =count+1
160. array4.append(random.randint(1,99))
161. count =count+1
162.
163. for x in range(64):
164. count =count+1
165. array5.append(random.randint(1,99))
166. count =count+1
167.
168. # I then initialized the counting for each particulat algorithm given n amount of numbers
169.
170. count=0
171. count1=0
172. count2=0
173. count3=0
174. count4=0
175. count5=0
176. count= 0
177.
178. # I call the fucntion with the specific array and print the counter for each sort
179. MergeSort(array1,0, len(array1)-1)
180. count1 = count
181. print(count1)
182. MergeSort(array2,0, len(array2)-1)
183. count2 = count
184. print(count2)
185. MergeSort(array3,0, len(array3)-1)
186. count3 = count
187. print(count3)
188. MergeSort(array4,0, len(array4)-1)
189. count4 = count
190. print(count4)
191. MergeSort(array5,0, len(array5)-1)
192. count5 = count
193. print(count5)
194.
195. # I then used the values from the steps and plotted them on this graph based on the number of numbers used on the x
196.
197. y_vals = [count1,count2,count3,count4,count5,count6]
198. x_vals = [4,8,16,32,64,128]
199. plt.scatter(y_vals,x_vals)
200. plt.title("Merge Sort Visualized")
201. plt.xlabel("N integers in a list")
202. plt.ylabel("yNumber of steps counted")
203. plt.show()
204.
205.
206. # In[ ]:
RAW Paste Data