Flo Suess Flo Suess - 1 month ago 35
Python Question

Median of three, pivot

I'm looking for the median of three, using this for a pivot in a QuickSort. I would not like to import any statistics library because I believe it creates a bit of overhead which I would like to reduce as much as possible.

def median(num_list):

if (num_list[0] > num_list[len(num_list) - 1]) and (num_list[0] < num_list[int(len(num_list)//2)]):
return num_list[0]
elif (num_list[int(len(num_list)//2)] > num_list[len(num_list) - 1]) and (num_list[0] > num_list[int(len(num_list)//2)]):
return num_list[int(len(num_list)//2)]
else:
return num_list[len(num_list) - 1]


this seems to be returning the last else statement every time, I'm stumped...

Answer

In Quicksort you do not usually want just to know the median of three, you want to arrange the three values so the smallest is in one spot, the median in another, and the maximum in yet another. But if you really just want the median of three, here are two ways, plus another that rearranges.

Here's a short way to find the median of a, b, and c.

return a + b + c - min(a, b, c) - max(a, b, c)

If you want only comparisons, and to get what may be the quickest code, realize that three comparisons may need to be executed but you want to try for only two. (Two comparisons can handle four cases, but there are six arrangements of three objects.) Try

if a < b:
    if b < c:
        return b
    elif a < c:
        return c
    else:
        return a
else:
    if a < c:
        return a
    elif b < c:
        return c
    else:
        return b

If you want to rearrange the values so a <= b <= c,

if a > b:
    a, b = b, a
if b > c:
    b, c = c, b
if a > b
    a, b = b, a
return b