daily pastebin goal
18%
SHARE
TWEET

Untitled

a guest Jan 22nd, 2019 68 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. ## TRIAL 1
  2. import math
  3. def MERGE (A,p,q,r):
  4.     steps=0
  5.     n1 = q-p+1
  6.     n2 = r-q
  7.     L = np.array
  8.     R = np.array
  9.     for i in range(1,n1+1):
  10.         L[i] = A[p+i-1]
  11.     for j in range(1,n2+1):
  12.         R[j] = A[q+j]
  13.     steps +=1     #dividing the initial array into 2
  14.     L[n1+1] = math.inf
  15.     R[n2+1] = math.inf
  16.     steps +=1     #adding sentinels
  17.     i=1
  18.     j=1
  19.     for k in range(p,r+1):
  20.         if L[i]<=R[j]:
  21.             A[k]=L[i]
  22.             i = i+1
  23.             steps +=1     #placing the smallest number
  24.         else:
  25.             A[k]=R[j]
  26.             j=j+1
  27.             steps +=1
  28.         steps +=k+1 #adding k+1 steps for checking every time the smallest value
  29.     #adding the plot for efficiency
  30.     A_eff[r] = (r,steps) #building an array of "efficiency for each r"
  31.                          #we'll need to multiply by the cost of each step later
  32.  
  33.     return (A, steps, A_eff[r])
  34.    
  35. def MERGE_SORT(A,p,r):
  36.     q = (p+r)//2    
  37.     steps +=1     #finding the right q
  38.     MERGE_SORT(A,p,q)
  39.     steps +=1     #dividing the initial array into two
  40.     MERGE_SORT(A,q+1,r)
  41.     steps +=1
  42.     MERGE(A,p,q,r)
  43.     steps +=1     #merging the two part of each subsection
  44. return(A,steps)
  45.  
  46. list = [1,3,4,7,2,10,5,9,8,6]
  47. MERGE_SORT (list,0,9)
  48.  
  49. ##TRIAL 2
  50. import math
  51. def MERGE_SORT (A,p,r):
  52.     steps=0
  53.    
  54.     q = (p+r)//2    
  55.     steps +=1     #finding the right q
  56.     MERGE_SORT(A,p,q)
  57.     steps +=1     #dividing the initial array into two
  58.     MERGE_SORT(A,q+1,r)
  59.     steps +=1
  60.     #MERGE(A,p,q,r)
  61.     #steps +=1  
  62.    
  63.     n1 = q-p+1
  64.     n2 = r-q
  65.     L = np.array
  66.     R = np.array
  67.     for i in range(1,n1+1):
  68.         L[i] = A[p+i-1]
  69.     for j in range(1,n2+1):
  70.         R[j] = A[q+j]
  71.     steps +=1     #dividing the initial array into 2
  72.     L[n1+1] = math.inf
  73.     R[n2+1] = math.inf
  74.     steps +=1     #adding sentinels
  75.     i=1
  76.     j=1
  77.     for k in range(p,r+1):
  78.         if L[i]<=R[j]:
  79.             A[k]=L[i]
  80.             i = i+1
  81.             steps +=1     #placing the smallest number
  82.         else:
  83.             A[k]=R[j]
  84.             j=j+1
  85.             steps +=1
  86.         steps +=k+1 #adding k+1 steps for checking every time the smallest value
  87.    
  88.    #adding the plot for efficiency
  89.     A_eff[r] = (r,steps) #building an array of "efficiency for each r"
  90.                          #we'll need to multiply by the cost of each step later
  91.  
  92.     return (A, steps, A_eff[r])
  93.  
  94. list = [1,3,4,7,2,10,5,9,8,6]
  95. MERGE_SORT (list,0,9)
  96. print(list)
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