Нахождение отсортированной средней 50% последовательности (в Boost Accumulators или в другой структуре данных)

Question

Для последовательности значений, как найти отсортированные средние 50% последовательности в Boost Accumulators?

Например, допустим, у меня есть следующая последовательность,
25, 21, 9, 13, 17, 19, 12, 29, 50, 97, 10, 11 .

Средние 50% -ые данные, которые я хотел бы получить, следующие:
13, 17, 19, 21 .

Конечно, можно отсортировать последовательность, которая теперь становится
9, 10, 11, 12, 13, 17, 19, 21, 25, 29, 50, 97 .

И тогда можно собрать средние 50% -ые данные.

Теперь, внутренняя структура Accumulators хранит и сортирует последовательность?Если да, возможно ли получить значение, которое находится в определенном индексе?

Чтение из здесь , я думаю, что среда Accumulators не хранит исходные данные, и эта структура не подходитдля проблемы, которую я пытаюсь решить.

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

Теперь, возможно ли построить структуру данных, которая бы эффективно поддерживала текущие и отсортированные средние 50% данные таким образом, чтобы размер структуры данных почти никогда не превышал половину размера последовательности?

Подумав некоторое время, я думаю, что возможно не удастся разработать такую ​​структуру данных.При первой же мысли я подумал, что некоторые значения можно забыть / отбросить навсегда, предполагая, что они никогда не появятся в отсортированных средних 50%.Тем не менее, это предположение, вероятно, неверно, и некоторые значения могут появиться в отсортированном среднем 50% в зависимости от , которые еще должны прийти значения в последовательности.

Answer 1

Как отметил @ Адам Розенфельд, вы ищете алгоритм выбора Хоара, который является вариантом быстрой сортировки.

Что он не заметил, так это то, что с некоторой осторожностью выон может поместить нужные вам элементы в нужное место как часть процесса выбора.

Алгоритм выбора разбивает данные на те, которые меньше и больше, чем выбранный элемент.Например, предположим, что у вас есть массив из 100 элементов, и вы хотите 25 ^th .Это расположило бы элементы так, чтобы первые 24 ^th элементов в массиве были меньше, чем 25 ^th , затем были бы 25 ^th , затем чем большеэлементы.Те, кто на каждой стороне, упорядочены только относительно этого одного элемента, но не по сравнению друг с другом.

Вы все еще можете воспользоваться этим, чтобы быстро получить средние 50%: сначала выберите 25-й процентиль.Затем укажите только часть над 25 ^th в качестве входных данных и найдите элемент 2/3 ^rds пути через эту часть.Это даст вам 25 ^th , 75 ^th и (важную часть) все элементы, значения которых между ними также будут расположены между этими элементами (хотя внутриэтот диапазон, порядок будет в основном случайным).

Answer 2

Вы ищете алгоритм выбора .

Используя алгоритм выбора, вы можете найти элементы 25-го и 75-го процентиля вашего набора данных за линейное время. Затем вы просто просматриваете массив и выбираете все элементы, которые находятся между 25-м и 75-м процентилями, чтобы получить средние 50%, которые вы ищете.