This assignment requires me to modify the quickSort code. can you please help me

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.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

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