• API
• FAQ
• Tools
• Archive
SHARE
TWEET # Untitled a guest Feb 16th, 2019 55 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
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) + fib(n-2), 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)
23.         quicksort(A,q+1,r)
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))
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)
58.
59. # both lists and fib(100) wasnt able to run in my computer
60. print(randomList(30))
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.

Top