Блок задач

12. Многопоточность

Сложность 4

Задача «Быстрая сортировка»

Постановка задачи

Реализовать параллельную версию алгоритма быстрая сортировка. Cхема разбиения должна определяться с помощью SchemePolicy классов. Нижеприведенные сигнатуры функций pquicksort фиксированы и не подлежат изменению.

//pquicksort.hpp
template <class RandomIt, class SchemePolicy>
void pquicksort(RandomIt first, RandomIt last, SchemePolicy&& partition);

template <class RandomIt, class Compare, class SchemePolicy>
void pquicksort(RandomIt first, RandomIt last, Compare comp, SchemePolicy&& partition);

Параллельная версия алгоритма работает лучше, чем последовательная реализация, только если размер диапазона превышает определенный порог, который может варьироваться в зависимости от параметров компиляции, платформы или оборудования. Поэкспериментируйте с различными порогами и размерами диапазонов, чтобы увидеть, как изменяется время выполнения. И установите порог на минимальное количество элементов для выполнения многопоточной реализации.

Требования

  1. Сигнатуры функций pquicksort фиксированы и не подлежат изменению.
  2. Названия header и source файлов следующие: pquicksort.hpp.
  3. Написать unit test'ы для реализованных функций.
  4. Провести замеры времени выполнения функций для сравнения параллельной версии и последовательной.