Как найти медиану параллельно.
Чтение всех других ответов и комментариев от:
Найти медиану параллельно
Iдо сих пор не могу понять, как работает алгоритм выбора.Во-первых, шаг 5 в ответе DuduAlul: «Стоп, если медиана найдена», как я узнаю это?Я всегда доволен ответами на примере, сейчас я сделаю один, на данный момент, возможно, неправильно, но если это будет решено, я надеюсь, что это поможет всем
Давайте предположим, что у нас есть массив из 8 элементов:
{1,5,8,4,10,15,9,6} - (Медиана равна 6 или 8, но мы еще не знаем)
Допустим, это будетразделить между четырьмя процессорами.
{1,5}, {8,4}, {10,15}, {9,6}
Сводка, скажем, - 5. Теперьсоздание групп на основе сводки (левая группа более низких значений и правая группа более высоких значений).
{1 |}, {4 | 8}, {| 10,15}, {| 6,9} -Что с 5?Что является значением в множестве, но также является осью?
Сумма элементов левой группы равна 2, а правой части - 5. Избавляемся от левой стороны и сохраняем количество отброшенных значений.Увеличение поворота на .. 2?Если это правда, то что, если разница между числами очень велика?
Сейчас Pivot 7. Снова расщепление.
{5 |}, {| 8}, {| 10,15}, {6 | 9}
Размер левой стороны равен 2, размер правой стороны равен 4. Отбрасывание левой стороны и увеличение поворота на 2. Теперь это будет 9.
{|}, {8 |}, {| 10,15}, {|}
Снова левая сторона меньше, и ее размер равен 1. Увеличивает значение поворота на 1, теперь это 10.
Снова расщепление.
{|}, {|}, {| 15}, {9 |}.
Размер левой стороны равен размеру правой стороны, что дает ответ 10 в моих вычислениях.Что не так, потому что правильный ответ 6 или 8. Что я сделал не так?