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

Question

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)

Please explain in detail what you “do no know”. Do you understand the concept of a median? Do you understand the difference between an index and the value stored at that index? Do you understand that the value in the middle of a list is only guaranteed to be the median if the list is already sorted? — pjs, May 09 '22 at 19:25
This [prior answer](https://stackoverflow.com/a/7560859/3282056) explains for quicksort median of 3, it is better to actually sort the first, middle, and last elements in each partition step, to improve performance for the later recursive calls. — rcgldr, May 09 '22 at 23:23

score 1 · Answer 1 · answered May 09 '22 at 19:54

1

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)

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

1 Answers1