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)[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))
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. OK, I Understand
 
Top