Guest User

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[227]:
  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[228]:
  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 = [0]*(n1+1)
  27. #Here I assigne the value of the left list to the number I obtained previously
  28. count =count+1
  29. Right = [0]*(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[229]:
  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[230]:
  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[242]:
  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