Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import time
- import random
- def fib(n):
- start = time.time()
- if n <= 0:
- end = time.time()
- return 0, end-start
- if n == 1:
- end = time.time()
- return 1, end-start
- return fib(n-1)[0] + fib(n-2)[0], time.time()-start
- def quicksort(A,p,r):
- start = time.time()
- if p < r:
- # partitioning the list in 2, so we can quicksort both sides
- # one partition has only lower values than the pivot
- # the other one has only higher values
- q = partition(A,p,r)
- quicksort(A,p,q-1)[0]
- quicksort(A,q+1,r)[0]
- return A, time.time()-start
- def partition(A,p,r):
- # x <- gets the pivot
- x = A[r]
- i = p-1
- j = p
- for a in range(j,r):
- # looping through all the numbers to organize them in higher
- # and lower than the pivot
- if A[a]<=x:
- i += 1
- A[i], A[a] = A[a], A[i]
- A[i+1], A[r] = A[r], A[i+1]
- # returning the index of where the pivot was inserted so we can sort
- # its left and right side again
- return i+1
- print(quicksort([8,7,6,5,4,3,2,1],0,7))
- def randomList(b):
- random.seed(123)
- tt = []
- for _ in range(b):
- lst1 = [random.random() for a in range(100000)]
- tt.append(quicksort(lst1, 0,len(lst1)-1)[1])
- return (sum(tt))/b
- def orderedList():
- print('asd')
- lst2 = [a for a in range(100000)]
- print(lst2)
- print('asd')
- return quicksort(lst2, 0,len(lst2)-1)[1]
- # both lists and fib(100) wasnt able to run in my computer
- print(randomList(30))
Add Comment
Please, Sign In to add comment