Студент

Бунтина Ирина

Задача

Быстрая сортировка

Состояние

Завершено

Баллов

3

Назначено

18.12.2022, 13:03

Завершено

27.12.2022, 05:58

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

Реализовать параллельную версию алгоритма быстрая сортировка. 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. Провести замеры времени выполнения функций для сравнения параллельной версии и последовательной.

Примечания

-1, за отсутствие тестов и за отсутствие аргументации в выборе количества потоков в SchemePolicy.