daily pastebin goal
20%
SHARE
TWEET

Untitled

a guest Jan 21st, 2019 56 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
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top