Найти медиану параллельно

Ответ 1

Использовать алгоритм выбора.

• Разделить массив числа до 100 разделов.
• Каждый процессор должен использовать общий опорный элемент для разделения массива на две группы (влево/вправо)
• то каждый процессор должен отправить размер этих двух групп лидеру
• лидер должен рассчитать, какая группа меньше, и транслировать сообщение, чтобы избавиться от одной из этих групп.
• вернитесь к шагу 2, пока не найдете медианную

это решение имеет avg runtime of O (n) для того, чтобы сделать его асимптотическим временем выполнения O (n), каждый процессор должен разделить числа на группы из 5 элементов, найти медиану каждой группы (используя сортировку вставки) и отправьте этих медианов лидеру, лидер выберет медиану этих медианов (используя один и тот же алгоритм) и что будет стержнем

прочитайте статью wiki - http://en.wikipedia.org/wiki/Selection_algorithm