Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- def bubblesortIterations(arrayLength):
- iterations = 0
- for i in range(arrayLength-1):
- for j in range(i+1, arrayLength):
- iterations += 1
- return iterations
- # MAIN FUNCTION
- print()
- print("When n = 4 in an array = [0, 1, 2, 3] I have 6 checks: (01), (02), (03), (12), (13), (23)")
- print("So there are c(n,2) = c(4,2) = 6 checks here.")
- print("c(n,2) = n! / (2! * (n-2)!) = n*(n-1)/2 = O(n^2)")
- print("It will be proved with the diagram below.")
- print()
- from matplotlib import pyplot as plt
- N = 20
- nList = list(range(1, N + 1))
- iterationsList = list()
- for n in nList:
- iterations = bubblesortIterations(n)
- iterationsList.append(iterations)
- print("n = " + str(n) + " ----> " + str(iterations) + " iterations")
- plt.plot(nList, iterationsList, 'o', label="Iterations when using bubblesort")
- plt.xlabel("n = num of elements")
- plt.ylabel("Iterations = O(n^2)")
- plt.legend()
- plt.show()
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement