Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #!/usr/bin/env python
- # coding: utf-8
- # In[227]:
- #Luis Gonzalez 21/01/2019 Code Session 2.1 - Mergesort and recurrences
- import random
- # 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
- # In[228]:
- #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
- def Merge(A,start,middle,length):
- global count
- #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
- n1 = int(middle-start+1)
- #I created the length of the first list by subratinc the start of the list minus the middle
- count =count+1
- #After each line code I increase the counter by one
- n2 = int(length-middle)
- #I then created the length of the second list by subtrating the total lenght of the list minus the middle
- count =count+1
- Left = [0]*(n1+1)
- #Here I assigne the value of the left list to the number I obtained previously
- count =count+1
- Right = [0]*(n2+1)
- # I do the same things as in the left assignation
- count =count+1
- for i in range(0,n1):
- count =count+1
- Left[i] = A[start+i]
- #Here I basically assign the values of the array to the new Left list
- count =count+1
- for j in range(0,n2):
- count =count+1
- Right[j] = A[middle+1+j]
- #Here I assign the values of the array to the new Right list
- count =count+1
- Left[n1] = 9999999
- #I then make the last number of the list extreamly large in order to identify when the code should stop
- count =count+1
- Right[n2] = 9999999
- #I do the same as the previous step
- count =count+1
- i = 0
- count =count+1
- j = 0
- #Here I made the counters 0 again in order to use them in he next loop
- count =count+1
- for k in range(int(start),int(length)+1):
- count =count+1
- if Left[i]<= Right[j]:
- #Here I compare the values of each lists and "append" the smalles value to the original list
- count =count+1
- A[k] = Left[i]
- count =count+1
- i=i+1
- #Increase i by 1
- count =count+1
- else:
- count =count+1
- A[k] = Right[j]
- count =count+1
- j=j+1
- #Increase j by 1
- count =count+1
- return count
- # I finally returned the value of count in order to use it outside of the function
- # In[229]:
- #I created a new function called MergeSort
- def MergeSort(A,start, length):
- global count
- # I once again assigne the value of count as a global variable
- count =count+1
- if start < length:
- #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
- count =count+1
- middle = (int(start+length)//2)
- #I assigned the value of middle of the array simply dividing the length of the array plus the start.
- #I used the "//" division rather than "/" because in Python 3, this bring a float and I needed an integer
- count =count+1
- MergeSort(A,start,middle)
- #I call the function on the new list to further divide it
- count =count+1
- MergeSort(A,middle+1,length)
- #I call the function on the other new list to further divide it
- count =count+1
- Merge(A,start,middle,length)
- #I finally start merging once I have the start middle and length
- count =count+1
- return count
- # In[230]:
- count = 0
- #I initialize the counter
- array = []
- # I create an empty array
- count =count+1
- for x in range(6):
- #I made a simply loop to append 6 randomly generated numbers
- count =count+1
- array.append(random.randint(1,99))
- count =count+1
- print("Initial Array of 6 numbers")
- print(array)
- #I print the initial array
- MergeSort(array,0, len(array)-1)
- # I call the function on the array and relevant values
- count =count+1
- print("Sorted Array of six numbers")
- print(array)
- print("Total count")
- print(count)
- # Finally I printed the values generated at the end.
- # In[242]:
- import matplotlib.pyplot as plt
- #I first Imported the relevant libarary to use which in this case is matplotlib
- # 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.
- array1 = []
- array2 = []
- array3 = []
- array4 = []
- array5 = []
- # I looped and appended random values to the lists while looping 2x more numbers in each list
- for x in range(4):
- count =count+1
- array1.append(random.randint(1,99))
- count =count+1
- for x in range(8):
- count =count+1
- array2.append(random.randint(1,99))
- count =count+1
- for x in range(16):
- count =count+1
- array3.append(random.randint(1,99))
- count =count+1
- for x in range(32):
- count =count+1
- array4.append(random.randint(1,99))
- count =count+1
- for x in range(64):
- count =count+1
- array5.append(random.randint(1,99))
- count =count+1
- # I then initialized the counting for each particulat algorithm given n amount of numbers
- count=0
- count1=0
- count2=0
- count3=0
- count4=0
- count5=0
- count= 0
- # I call the fucntion with the specific array and print the counter for each sort
- MergeSort(array1,0, len(array1)-1)
- count1 = count
- print(count1)
- MergeSort(array2,0, len(array2)-1)
- count2 = count
- print(count2)
- MergeSort(array3,0, len(array3)-1)
- count3 = count
- print(count3)
- MergeSort(array4,0, len(array4)-1)
- count4 = count
- print(count4)
- MergeSort(array5,0, len(array5)-1)
- count5 = count
- print(count5)
- # I then used the values from the steps and plotted them on this graph based on the number of numbers used on the x
- y_vals = [count1,count2,count3,count4,count5,count6]
- x_vals = [4,8,16,32,64,128]
- plt.scatter(y_vals,x_vals)
- plt.title("Merge Sort Visualized")
- plt.xlabel("N integers in a list")
- plt.ylabel("yNumber of steps counted")
- plt.show()
- # In[ ]:
Add Comment
Please, Sign In to add comment