This is a python programming question, the code below was submitted to answer th

Question

This is a python programming question, the code below was submitted to answer this question:

Please implement the median-of-three method for selecting a pivot into the quicksort code.

The response I received said that "the code had not used the Median-of-Three to get the Pivot value! The Pivot value is the first one in the list."

Any assistance in looking at the below code and correcting it to properly utilize the Median-of-Three to get the Pivot value would be much appreciated.

Code:

def quickSort(alist):
quickSortHelper(alist,0,len(alist)-1)

def quickSortHelper(alist,first,last):
if first<last:

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

while alist[rightmark] >= pivotvalue and rightmark >= leftmark:
rightmark = rightmark -1

if rightmark < leftmark:
done = True
else:
temp = alist[leftmark]
alist[leftmark] = alist[rightmark]
alist[rightmark] = temp

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

def quickSort(alist):
quickSortHelper(alist,0,len(alist)-1)
def quickSortHelper(alist,first,last):
if first<last:
splitpoint = partition(alist,first,last)
quickSortHelper(alist,first,splitpoint-1)
quickSortHelper(alist,splitpoint+1,last)

def partition(alist,first,last):
#take middle value as pivot value
pivotvalue = alist[first + (last-first) / 2]
leftmark = first+1
rightmark = last
done = False
while not done:
while leftmark <= rightmark and alist[leftmark] <= pivotvalue:
leftmark = leftmark + 1
while alist[rightmark] >= pivotvalue and rightmark >= leftmark:
rightmark = rightmark -1
if rightmark < leftmark:
done = True
else:
temp = alist[leftmark]
alist[leftmark] = alist[rightmark]
alist[rightmark] = temp
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)

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

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