This assignment requires us to modify the quickSort code. We need to implement t
ID: 3729116 • Letter: T
Question
This assignment requires us to modify the quickSort code. We need to implement the median-of-three method for selecting a pivot.(PYTHON)
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)
Explanation / Answer
Quick sort
def quickSort(data_list):
quickSortHlp(data_list,0,len(data_list)-1)
def quickSortHlp(data_list,first,last):
if first < last:
splitpoint = partition(data_list,first,last)
quickSortHlp(data_list,first,splitpoint-1)
quickSortHlp(data_list,splitpoint+1,last)
def partition(data_list,first,last):
pivotvalue = data_list[first]
leftmark = first+1
rightmark = last
done = False
while not done:
while leftmark <= rightmark and data_list[leftmark] <= pivotvalue:
leftmark = leftmark + 1
while data_list[rightmark] >= pivotvalue and rightmark >= leftmark:
rightmark = rightmark -1
if rightmark < leftmark:
done = True
else:
temp = data_list[leftmark]
data_list[leftmark] = data_list[rightmark]
data_list[rightmark] = temp
temp = data_list[first]
data_list[first] = data_list[rightmark]
data_list[rightmark] = temp
return rightmark
data_list = [54,26,93,17,77,31,44,55,20]
quickSort(data_list)
print(data_list)