Question

Python Programming Question

1. Implement the median-of-three method for selecting a pivot value as a modification to quickSort (name this function

mo3_quickSort). Prepare test cases for your mo3_quickSort .function

QuickSort function:

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

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)

2. Prepare and run an experiment to verify the following hypothesis.

Canonic quickSort is as fast as mo3_quickSort when processing large lists of unsorted integers.

Answer 1

"""
Python Program
Quick sort with median of three numbers
"""

def quickSort(L):
quicksorthelp(L, 0, len(L))


def quicksorthelp(L, first, last):
if first < last:
pivot_location = Partition(L, first, last)
quicksorthelp(L, first, pivot_location)
quicksorthelp(L, pivot_location + 1, last)


def medianOfThree(L, first, last):
mid = (first+last-1)//2
a = L[first]
b = L[mid]
c = L[last-1]
if a <= b <= c:
return b, mid
if c <= b <= a:
return b, mid
if a <= c <= b:
return c, last-1
if b <= c <= a:
return c, last-1
return a, first

def Partition(L, first, last):
pivot, pidx = medianOfThree(L, first, last)
L[first], L[pidx] = L[pidx], L[first]
i = first + 1

for j in range(first+1, last, 1):
if (L[j] < pivot):
L[i], L[j] = L[j], L[i]
i += 1

L[first], L[i-1] = L[i-1], L[first]
return i - 1

alist = [54,26,93,17,77,31,44,55,20]
print("Before: ", alist)
quickSort(alist)
print("After: ", alist)