# A has a random order of integers from 0 to 100 inclusive. A = random.sample(range(0, 101), random.randint(1,100)) print(A) # A is made of entirely identical entries (all 1s). A = [int(1)]*random.randint(1,100) print(A) Conduct doubling experiments to compare the run time of merge sort vs. quick sort (for both C and D ). Plot the results (both case of array) for array sizes n = 2, 4, ... 1024. merge and quick sort are provided below ### Merge Sort ### def merge (front, back): pos_f, pos_b = 0,0 merged = np.zeros(len(front)+len(back)) for i in range (len(merged)): if pos_f == len(front): merged[i] = back[pos_b] pos_b += 1 elif pos_b == len(back): merged[i] = front[pos_f] pos_f += 1 elif front[pos_f] < back[pos_b]: merged[i] = front[pos_f] pos_f += 1 else: merged[i] = back[pos_b] pos_b += 1 return merged def merge_sort(A): n = len(A) if n <= 1: return A mid = int(n/2) front = merge_sort(A[0:mid]) back = merge_sort(A[mid:]) return merge(front, back) ### Quick Sort ### def partition(A, lo, hi): pivotvalue = A[lo] i = lo+1 j = hi done = False while not done: while i <= j and A[i] <= pivotvalue: i = i + 1 while A[j] >= pivotvalue and j >= i: j = j - 1 if j < i: done = True else: A[i], A[j] = A[j], A[i] A[lo], A[j] = A[j], A[lo] return j, A def quick_sort(A, lo, hi): if lo < hi: splitpoint, A = partition(A, lo, hi) A = quick_sort(A, lo, splitpoint - 1) A = quick_sort(A, splitpoint + 1, hi) return A def quick_sort_helper_rand(A): np.random.shuffle(A) return quick_sort(A, 0, len(A)-1) def quick_sort_helper_nonrand(A): return quick_sort(A, 0, len(A)-1) provide code and resul
# A has a random order of integers from 0 to 100 inclusive.
A = random.sample(range(0, 101), random.randint(1,100))
print(A)
# A is made of entirely identical entries (all 1s).
A = [int(1)]*random.randint(1,100)
print(A)
Conduct doubling experiments to compare the run time of merge sort vs. quick sort (for both C and D ). Plot the results (both
case of array) for array sizes n = 2, 4, ... 1024. merge and quick sort are provided below
### Merge Sort ###
def merge (front, back):
pos_f, pos_b = 0,0
merged = np.zeros(len(front)+len(back))
for i in range (len(merged)):
if pos_f == len(front):
merged[i] = back[pos_b]
pos_b += 1
elif pos_b == len(back):
merged[i] = front[pos_f]
pos_f += 1
elif front[pos_f] < back[pos_b]:
merged[i] = front[pos_f]
pos_f += 1
else:
merged[i] = back[pos_b]
pos_b += 1
return merged
def merge_sort(A):
n = len(A)
if n <= 1:
return A
mid = int(n/2)
front = merge_sort(A[0:mid])
back = merge_sort(A[mid:])
return merge(front, back)
### Quick Sort ###
def partition(A, lo, hi):
pivotvalue = A[lo]
i = lo+1
j = hi
done = False
while not done:
while i <= j and A[i] <= pivotvalue:
i = i + 1
while A[j] >= pivotvalue and j >= i:
j = j - 1
if j < i:
done = True
else:
A[i], A[j] = A[j], A[i]
A[lo], A[j] = A[j], A[lo]
return j, A
def quick_sort(A, lo, hi):
if lo < hi:
splitpoint, A = partition(A, lo, hi)
A = quick_sort(A, lo, splitpoint - 1)
A = quick_sort(A, splitpoint + 1, hi)
return A
def quick_sort_helper_rand(A):
np.random.shuffle(A)
return quick_sort(A, 0, len(A)-1)
def quick_sort_helper_nonrand(A):
return quick_sort(A, 0, len(A)-1)
provide code and result
Step by step
Solved in 4 steps with 5 images
