# 3. Массив размером 2m + 1, где m – натуральное число, заполнен случайным образом.
# Найдите в массиве медиану. Медианой называется элемент ряда, делящий его на две равные части:
#  в одной находятся элементы, которые не меньше медианы, в другой – не больше медианы.
#  Задачу можно решить без сортировки исходного массива.
#  Но если это слишком сложно, то используйте метод сортировки, который не рассматривался на уроках

import random
from collections import Counter

m = 5
array = [10, 5, 10, 11, 15, 10, 3, 11, 12, 0, 9]
# [random.randint(0, 15) for _ in range(2 * m + 1)]
print(f'Исходный массив: {array}')
min_element = min(array)
# все значения элементов списка лежит в диапазоне:
size_sorted = max(array) - min_element
# формируем массив нулей размером в диапазон разброса значений
sort = [i * 0 for i in range(size_sorted + 1)]
# формируем словарь, в котором подсчитаем количество входждений элементов списка
value_weight = Counter(array)
# сортируем получившиеся пары (значения - количество вхождений) по значению элемента исходного массива
for key, value in value_weight.items():
    # для этого нормируем на минимальный элемент, чтобы забивать массив начиная с нулевого индекса
    index = key - min_element
    sort[index] = (key, value)
# массив получился с остататочными нулями, убираем нули:
sort = [i for i in sort if i != 0]

n = 0
median = array[0]
# в отсортированном списке кортежей высчитываем индекс кортежа, где лежит значение медианы:
for tuple_ in sort:
    n = n + tuple_[1]
    if n >= m:
        median = tuple_[0]
        break
print(f'Медиана исходного массива: {median}')
