Guest User

Untitled

a guest
Feb 16th, 2019
82
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.51 KB | None | 0 0
  1. import time
  2. import random
  3.  
  4. def fib(n):
  5. start = time.time()
  6. if n <= 0:
  7. end = time.time()
  8. return 0, end-start
  9. if n == 1:
  10. end = time.time()
  11. return 1, end-start
  12. return fib(n-1)[0] + fib(n-2)[0], time.time()-start
  13.  
  14.  
  15. def quicksort(A,p,r):
  16. start = time.time()
  17. if p < r:
  18. # partitioning the list in 2, so we can quicksort both sides
  19. # one partition has only lower values than the pivot
  20. # the other one has only higher values
  21. q = partition(A,p,r)
  22. quicksort(A,p,q-1)[0]
  23. quicksort(A,q+1,r)[0]
  24. return A, time.time()-start
  25.  
  26. def partition(A,p,r):
  27. # x <- gets the pivot
  28. x = A[r]
  29. i = p-1
  30. j = p
  31. for a in range(j,r):
  32. # looping through all the numbers to organize them in higher
  33. # and lower than the pivot
  34. if A[a]<=x:
  35. i += 1
  36. A[i], A[a] = A[a], A[i]
  37. A[i+1], A[r] = A[r], A[i+1]
  38. # returning the index of where the pivot was inserted so we can sort
  39. # its left and right side again
  40. return i+1
  41.  
  42. print(quicksort([8,7,6,5,4,3,2,1],0,7))
  43.  
  44. def randomList(b):
  45. random.seed(123)
  46. tt = []
  47. for _ in range(b):
  48. lst1 = [random.random() for a in range(100000)]
  49. tt.append(quicksort(lst1, 0,len(lst1)-1)[1])
  50. return (sum(tt))/b
  51.  
  52. def orderedList():
  53. print('asd')
  54. lst2 = [a for a in range(100000)]
  55. print(lst2)
  56. print('asd')
  57. return quicksort(lst2, 0,len(lst2)-1)[1]
  58.  
  59. # both lists and fib(100) wasnt able to run in my computer
  60. print(randomList(30))
Add Comment
Please, Sign In to add comment