Медиана из трех, сводная

ProgramBox

Медиана из трех, сводная

Post author:admin
Запись опубликована:20 августа, 2022
Post category:Вопросы по программированию

#python #quicksort

#python #быстрая сортировка

Вопрос:

Я ищу медиану из трех, используя это для сводки в быстрой сортировке. Я бы не хотел импортировать какую-либо библиотеку статистики, потому что считаю, что это создает небольшие накладные расходы, которые я хотел бы максимально сократить.

 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]

кажется, что это каждый раз возвращает последнее утверждение else, я в тупике…

1. Я думаю, вы не охватываете все возможные упорядочения значений. Первым элементом может быть медиана, если middle> first> last (и я думаю, что ваш код получает это правильно), но также если last> first> middle (не думаю, что это работает тогда). Вы можете выписать все шесть возможных вариантов расположения значений 1,2,3, написать код, который правильно их выполняет (даже если он подробный), а затем упростить оттуда (например, если есть an if cond1 and cond2 и an if cond2 and cond3 , вы можете преобразовать в an if cond2 с двумя ifs под ним).

2. (И вам не обязательно выполнять часть упрощения, хотя вашему учителю и вашему внутреннему перфекционисту это может понравиться! Вы должны быть в состоянии правильно настроить код для доставки полезных вещей; остальное необязательно, или вы можете создать его со временем.)

3. Спасибо Twotwotwo, это то, что я в итоге сделал.

Ответ №1:

В быстрой сортировке вы обычно не хотите просто знать медиану из трех, вы хотите расположить три значения так, чтобы наименьшее было в одном месте, медиана — в другом, а максимальное — в еще одном. Но если вы действительно просто хотите медиану из трех, вот два способа, плюс еще один, который перестраивается.

Вот короткий способ найти медиану a , b , и c .

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

Если вы хотите только сравнения и хотите получить, возможно, самый быстрый код, поймите, что может потребоваться выполнить три сравнения, но вы хотите попробовать только два. (Два сравнения могут обрабатывать четыре случая, но существует шесть компоновок из трех объектов.) Попробуйте

 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

Если вы хотите изменить значения таким образом 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

Ответ №2:

Пусть Python сделает всю работу за вас. Отсортируйте три элемента, затем верните средний.

 def median(num_list):
    return sorted([num_list[0], num_list[len(num_list) // 2], num_list[-1]])[1]

1. Ммм, выглядит неплохо, но я постараюсь запустить все вызываемые функции самостоятельно. Спасибо тебе, Киндалл.

2. @FloSuess, что ты имеешь в виду run all called functions on my own ?

3. Ну, извините, это было немного странно, я имею в виду, что в этом конкретном задании я разрабатывал алгоритм быстрой сортировки. Использование функции сортировки было бы в некотором смысле мошенничеством.

Ответ №3:

Используя min и max :

 >>> numlist = [21, 12, 16]
>>> a, b, c = numlist
>>> max(min(a,b), min(b,c), min(a,c))
16
>>>

Выход на пределе — у меня есть функциональная полоса, поэтому вот эквивалент itertools, хотя это означает импорт модуля

 >>> import itertools
>>> numlist = [21, 12, 16]
>>> z = itertools.combinations(numlist, 2)
>>> y = itertools.imap(min, z)
>>> max(y)
16

1. Мне это нравится, поскольку оно в некотором смысле короче, чем мое выражение с использованием max and min . Однако в конечном итоге используется пять сравнений по сравнению с моими четырьмя.

Метки: Медиана из трех, сводная