Функция возвращающая медиану

Question

Есть задача, в котором необходимо вернуть медиану. Я решил её, но уверен, что можно было бы написать более красивый и лаконичный код. Помогите пожалуйста.

Написать функцию median(x1, x2, ...), принимающую на вход несколько чисел и возвращающую их медиану (для чётного числа элементов возьмите среднее арифметическое между двумя серединными элементами). Пользоваться библиотечными функциями нельзя!

Для проверки:

from random import shuffle, seed
seed(0)
def shuffle_test(f, inp, outp, n=10):
for i in range(n):
    shuffle(inp)
    assert abs(f(*inp)-outp)<1E-15
def test(inp,outp, n=10):
return shuffle_test(median, inp, outp)

test([1,2],1.5)
test([1,2,3], 2)
test([10,20,30],20)
test([10,20,30,40], 25)
test([1, 2, 4, 8, 16], 4)
test([4],4)
test([4]*100+[1000],4)

del shuffle, seed, shuffle_test, test

Мой код:

def median(*args):

x = []

for i in args:
    if type(i) is list:
        for y in i:
            x.append(y)

    elif type(i) is int or float:
        x.append(round(i, 2))

x.sort()
ind_one = int((len(x)/2-1))
ind_two = int(len(x)/2)
ind_odd = int(len(x)/2 - 0.5)

if len(x) % 2 == 0:
    med = (x[ind_one] + x[ind_two]) / 2

elif len(x) % 2 != 0:
    med = round(float(x[ind_odd]), 2)

return med

Благодарю!

Answer 1

Полная сортировка для нахождения медианы не обязательна. Вместо этого можно использовать алгоритм QuickSelect, основанный на той же процедуре разбиения, как и QuickSort, с аргументом длина пополам.

Код с индогиков (partition не лучший, по схеме Ломуто):

def partition(arr, l, r): 

    x = arr[r] 
    i = l 
    for j in range(l, r): 

        if arr[j] <= x: 
            arr[i], arr[j] = arr[j], arr[i] 
            i += 1

    arr[i], arr[r] = arr[r], arr[i] 
    return i 

def kthSmallest(arr, l, r, k): 

    # if k is smaller than number of 
    # elements in array 
    if (k > 0 and k <= r - l + 1): 

        # Partition the array around last 
        # element and get position of pivot 
        # element in sorted array 
        index = partition(arr, l, r) 

        # if position is same as k 
        if (index - l == k - 1): 
            return arr[index] 

        # If position is more, recur  
        # for left subarray  
        if (index - l > k - 1): 
            return kthSmallest(arr, l, index - 1, k) 

        # Else recur for right subarray  
        return kthSmallest(arr, index + 1, r,  
                            k - index + l - 1) 
    return INT_MAX 

# Driver Code 
arr = [ 10, 4, 5, 8, 6, 11, 26 ] 
n = len(arr) 
k = 3
print("K-th smallest element is ", end = "") 
print(kthSmallest(arr, 0, n - 1, k))

БЛОГ НА HUSL

Функция возвращающая медиану

Ответы (1 шт):