In an effort to balance the distribution (length) of partitions created in the Q

Question

In an effort to balance the distribution (length) of partitions created in the Quicksort algorithm so that worst case performance can be avoided, one can employ randomization, rather than selecting the element at a certain position as the pivot. Use your favorite programming language to implement the randomized Quicksort algorithm. You will need to use the following algorithms to implement it: You may use any random function to implement RANDOM(p,r) in line 1 of the RANDOMIZED- PARTITION algorithm. Please specify in your solution what sort of randomization you use for the RANDOM(p,r) function.

A. Randomly generate arrays of size 100, 1000, 10000 elements and measure runtime of your program for each array. Plot a runtime vs. array size chart to show the runtime results. Please comment on your chart. Include a screenshot of the execution of your program on 3 different array sizes.

B.) What will be the best case for the Quicksort algorithm? Create an array of 100 elements that you expect will yield the best case runtime and run your program on this array and measure and record this time.

C. What will be the worst case for the Quicksort algorithm? Create an array of 100 elements that you expect will yield the worst case runtime and run your program on this array and measure and record this time.

D. Compare your results from B and C and comment on them. Does employing a randomized version of Quicksort affect your results in B and C? Please explain.

Explanation / Answer

#Run the code and see the result files created during runtime

import random,time

def Partition(array,left,right):

pivot=random.randint(left,right)

array[right],array[left] = array[left],array[right]

piIndex=left-1

for i in range(left,right):

if(array[i]<array[right]):

piIndex+=1

array[piIndex] ,array[i] = array[i],array[piIndex]

array[piIndex+1],array[right] = array[right],array[piIndex+1]

return piIndex+1

def QuickSort(array,left,right):

if(left<right):

pivot=random.randint(left,right)

array[right],array[pivot] = array[pivot],array[right]

pivot=Partition(array,left,right)

QuickSort(array,left,pivot-1)

QuickSort(array,pivot+1,right)

'''

#Answer for Question A:

array = []

f = open("res.txt","w")

for i in range(2,4):

array.clear()

start_time = time.clock()

for j in range(pow(10,i)):

array.append(random.randint(1,100))

l = pow(10,i)

QuickSort(array,0,l-1)

end_time = time.clock()

f.write("Elapsed time for:"+str(pow(10,i))+"= "+str(end_time-start_time)+" ")

print("Elapsed time for:",pow(10,i),"= ",end_time-start_time)

print("sorted array",array)

f.close()

'''

'''

#answer for B:-

arrays = []

array = []

f = open("resB.txt","w")

min_time = 99999

pos = -1

l = 100

for i in range(10):

array.clear()

for j in range(l):

array.append(random.randint(1,100))

arrays.append(array.copy())

start_time = time.clock()

QuickSort(array,0,l-1)

end_time = time.clock()

diff = end_time-start_time

if(diff<min_time):

min_time = diff

pos = i

f.write("Elapsed time for:"+str(l)+"= "+str(diff)+" ")

print("Elapsed time for:",l,"= ",diff)

f.close()

print(arrays[pos])

print("Minimum Elapsed time for:",l,"= ",min_time)

'''

# answer for C:-

arrays = []

array = []

f = open("resC.txt","w")

min_time = -99999

pos = -1

l = 100

for i in range(10):

array.clear()

for j in range(l):

array.append(random.randint(1,100))

arrays.append(array.copy())

start_time = time.clock()

QuickSort(array,0,l-1)

end_time = time.clock()

diff = end_time-start_time

if(diff>min_time):

min_time = diff

pos = i

f.write("Elapsed time for:"+str(l)+"= "+str(diff)+" ")

print("Elapsed time for:",l,"= ",diff)

f.close()

print(arrays[pos])

print("Maximum Elapsed time for:",l,"= ",min_time)

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.