• API
• FAQ
• Tools
• Archive
SHARE
TWEET Untitled a guest Jan 21st, 2019 59 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
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.
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!

Top