Advertisement
makispaiktis

Number of iterations in bubblesort with diagram

Aug 21st, 2020 (edited)
897
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 0.93 KB | None | 0 0
  1. def bubblesortIterations(arrayLength):
  2.     iterations = 0
  3.     for i in range(arrayLength-1):
  4.         for j in range(i+1, arrayLength):
  5.             iterations += 1
  6.     return iterations
  7.  
  8. # MAIN FUNCTION
  9. print()
  10. print("When n = 4 in an array = [0, 1, 2, 3] I have 6 checks: (01), (02), (03), (12), (13), (23)")
  11. print("So there are c(n,2) = c(4,2) = 6 checks here.")
  12. print("c(n,2) = n! / (2! * (n-2)!) = n*(n-1)/2 = O(n^2)")
  13. print("It will be proved with the diagram below.")
  14. print()
  15.  
  16. from matplotlib import pyplot as plt
  17. N = 20
  18. nList = list(range(1, N + 1))
  19. iterationsList = list()
  20. for n in nList:
  21.     iterations = bubblesortIterations(n)
  22.     iterationsList.append(iterations)
  23.     print("n = " + str(n) + " ----> " + str(iterations) + " iterations")
  24.  
  25. plt.plot(nList, iterationsList, 'o', label="Iterations when using bubblesort")
  26. plt.xlabel("n = num of elements")
  27. plt.ylabel("Iterations = O(n^2)")
  28. plt.legend()
  29. plt.show()
  30.  
  31.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement