This assignment requires me to modify the quickSort code. can you please help me
ID: 3567080 • Letter: T
Question
This assignment requires me to modify the quickSort code. can you please help me implement the median-of-three methods for selecting a pivot.
Here is the CODE:
def quickSort(alist):
quickSortHelper(alist,0,len(alist)-1)
def quickSortHelper(alist,first,last):
if first
splitpoint = partition(alist,first,last)
quickSortHelper(alist,first,splitpoint-1)
quickSortHelper(alist,splitpoint+1,last)
def partition(alist,first,last):
pivotvalue = alist[first]
leftmark = first+1
rightmark = last
done = False
while not done:
while leftmark <= rightmark and
alist[leftmark] <= pivotvalue:
leftmark = leftmark + 1
print(alist)
while alist[rightmark] >= pivotvalue and
rightmark >= leftmark:
rightmark = rightmark -1
print(alist)
if rightmark < leftmark:
done = True
else:
temp = alist[leftmark]
alist[leftmark] = alist[rightmark]
alist[rightmark] = temp
print(alist)
temp = alist[first]
alist[first] = alist[rightmark]
alist[rightmark] = temp
return rightmark
alist = [54,26,93,17,77,31,44,55,20]
quickSort(alist)
print(alist)
Explanation / Answer
The changed code by adding the MedianOfThree method is as shown below:
def quickSort(alist):
quickSortHelper(alist,0,len(alist)-1)
def quickSortHelper(alist,first,last):
if first
pivot = MedianOfThree (alist,first,last)
quickSortHelper(alist,first, pivot -1)
quickSortHelper(alist, pivot +1,last)
//the medianofThree method to find the pivot element position
def MedianOfThree(alist, first, last):
midean = (first + last)/2
if alist[last] < alist [first]:
Swap(alist, first, last)
if alist [midean] < alist [first]:
Swap(alist, midean, first)
if alist [last] < alist [midean]:
Swap(alist, last, midean)
return midean
//Generic Swap for manipulating list data.
def Swap(alist, first, last):
temp = alist [first]
alist [first] = alist [last]
alist [last] = temp
alist = [54,26,93,17,77,31,44,55,20]
quickSort(alist)
print(alist)
Note: pPease the check the above code that is in bold letters. The bold statements specify the changed code.