Алгоритм медианы медиан - какой элемент выбрать в качестве медианы для каждой группы

(ПРИМЕЧАНИЕ: в моем примере я делю массив на подмассивы, содержащие 5 элементов)

Я понимаю, что алгоритмы медианы медиан разбивают n-входной массив на группы floor(n/5) с дополнительной группой, содержащей элементы (n)mod5, а затем находят медианный элемент каждой отсортированной группы (3-й элемент в группы по 5 элементов) и так далее.

Мой вопрос: если в одной из групп было 2 или 4 элемента, какой элемент будет выбран в качестве медианы этой группы (при условии, что группа уже отсортирована).


algorithm median-of-medians
person Newbie123    schedule 09.03.2020    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Для группы из 2 элементов будет выбрано ближайшее крайнее левое значение в отсортированной группе.

например для группы

[2,5]

2 будет выбрано в качестве медианы группы.

Для группы из 4 элементов 2-й элемент будет медианой.

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

person Newbie123    schedule 09.03.2020