Using the code below I need to implement the median-of-three method for selectin
ID: 3758243 • Letter: U
Question
Using the code below I need to implement the median-of-three method for selecting a pivot. I can't seem to get it to work. I added a median() function and messed with the partition a bit but I haven't made it work correctly using the median like I need to. If I understand it correctly, taking the numbers in the alist into account the first, middle and last numbers are 54,77 and 20, making the median 54, but how do I get the program to see that and then make the pivot the median discovered.
If there is a way to do it in the code, please show me, I appreciate the help!
The starting code is below:
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
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
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)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.