need to correct this i want to use quick sort median pivot emelent my professor is asking me this statement

Your function partition_median () does not use the median of the first middle and last element, but only takes the middle element.

but i do no know

def partition_median(req_list,start_index,end_index):
    """Function get Pivot at meadian."""
    pivot = req_list[(end_index start_index)//2]
    i, j = start_index - 1, end_index   1
    while True:
        i  = 1
        j -= 1
        while req_list[i] < pivot:
            i  = 1
        while req_list[j] > pivot:
            j -= 1

        if i >= j:
            return j

        req_list[i], req_list[j] = req_list[j], req_list[i]
def qsort_median(req_list, start_index, end_index):
    """Function to sort by median."""
    if start_index < end_index:
        pivot = partition_median(req_list, start_index, end_index)
        qsort_median(req_list, start_index, pivot)
        qsort_median(req_list, pivot   1, end_index)


def quicksort_pivot_median(list_re):
    """Function sorting by median."""
    qsort_median(list_re, 0, len(list_re) - 1)

CodePudding user response：

Indeed, as your teacher is saying, you are taking the middle element as pivot:

pivot = req_list[(end_index start_index)//2]

Apparently you were asked to "use the median of the first, middle and last element". So at least you need to inspect those three values:

a = req_list[start_index]
b = req_list[(end_index start_index)//2]
c = req_list[end_index]
# The median of 3 values can be got by taking them all, 
#    but then subtracting the two extremes from it:
pivot = a   b   c - max(a, b, c) - min(a, b, c)

See also Wikipedia on median.

CodePudding user response：

The simplest method is to sort the 3 values at req_list[start_index], req_list[(start_index end_index)//2], req_list[end_index-1], then use req_list[(start_index end_index)//2] for the pivot. This will need 3 if | swap sequences.