Цели работы:
- познакомиться с разными алгоритмами сортировки, узнать их различия, повысить навыки реализации различных алгоритмов, улучшить понимание
Oнотации и усвоить сложность алгоритмов сортировки. - получить навыки написание обобщенного кода, научиться использовать компараторы и предикаты, повысить понимание "внутренностей" STL библиотеки.
На предыдущих занятиях были расмотрены алгоритмы STL, использвание компараторов и предикатов в алгоритмах.
Расмотрим два примера.
В первом примере, вектор строк сортируется в лексикографическом порядке, т.е. используется дефолтный оператор сравнения двух строк.
std::vector<std::string> v = GetStrings();
std::sort(v.begin(), v.end());Во втором примере, используется пользовательский компаратор (с использованием лямбда-функции). В этом пример вектор строк сортируется в порядке их длины.
std::vector<std::string> v = GetStrings();
std::sort(v.begin(), v.end(), [](const std::string& a, const std::string& b) {
return a.size() < b.size();
});Рассмотрим, как создавать собственный код с использованием компаратора.
Во-первых, в большинстве случаем компараторы удобно определять как аргумент шаблона.
Во-вторых, компаратор надо представлять как обычную функцию и использовать её соответсвующим образом.
Реализуем функцию определения отсортирован ли контейнер. В качестве двух первых аргументов передает диапазон контейнера [first, last). Диапазон задается итераторами. Третий аргумент - это компаратор, который позволяет сравнивать элементы.
Компаратор возвращает true, если первый его аргумент "меньше" второго аргумента. Заметим, что "меньше" в кавычках. Потому что в зависимости от реализации компаратора, функция будет считать отсортированность по разному.
template <class ForwardIt, class Compare=std::less<>>
bool is_sorted(ForwardIt first, ForwardIt last, Compare cmp=Compare{}) {
if (first != last) {
auto next = first;
while (++next != last) {
// Сравнение двух элементов.
if (cmp(*next, *first)) {
return false;
}
first = next;
}
}
return true;
}Проверим, что массив отсортирован по возрастанию. Для этого используем компаратор std::less<>:
constexpr bool less()(const T& lhs, const T& rhs) const {
return lhs < rhs;
}std::vector<int> arr = {1, 2, 3, 4, 5, 6};
std::cout << std::boolalpha << is_sorted(arr.begin(), arr.end(), std::less<>{});Проверим, что массив отсортирован по убыванию. ля этого используем компаратор std::greater<>:
constexpr bool greater()(const T& lhs, const T& rhs) const {
return rhs < lhs; // внимание на порядок аргументов.
}std::vector<int> arr = {7, 5, 3, 1};
std::cout << std::boolalpha << is_sorted(arr.begin(), arr.end(), std::greater<>{});Проверим, что массив отсортирован по убыванию с помощью лямбда-функции.
std::vector<int> arr = {7, 5, 3, 1};
std::cout << std::boolalpha << is_sorted(arr.begin(), arr.end(),
[](int a, int b) {
return a > b;
});Выше было сказано, что компараторы/предикаты надо представлять как обычную функцию. Давайте рассмотрим, что можно использовать еще для этой цели.
По факту, можно использовать все для чего определена операция круглых скобок. Т.е. всё для чего мы можем применить var(). Перечислим эти сущности.
Конечно можно использовать в качестве компаратора и любого другого предиката функции.
constexpr bool greater()(const int lhs, const int rhs) const {
return rhs < lhs;
}
std::vector<int> arr = {7, 5, 3, 1};
std::cout << std::boolalpha << is_sorted(arr.begin(), arr.end(), greater);Если углубляться, то конечно же тут используется не функция, а указатель на функцию. Поэтому грамотнее говорить, что в качетсве компаратора используется именно указатель на функцию.
Для произвольного класса можно переопределить operator(). Это позволит вызывать оператор у объекта класса. Рассмотрим пример.
class Polynom {
float operator(float x) const {
// ...
}
};
Polynom poly{1, 2, 3, 4};
float y = poly(0.5f);Т.е таким образом получилось, что если не вдаваться в подробности и не знать, что poly это объект класса, то можно подумать, что poly это некая функция.
Благодаря этому объекты классов, у которых переопределен operator(), можно вызывать как фукнцию и использовать её как предикат/компаратор.
В качестве компаратора и любого другого предиката можно использовать и лямбда-функции.
std::vector<int> arr = {7, 5, 3, 1};
std::cout << std::boolalpha << is_sorted(arr.begin(), arr.end(),
[](int a, int b) {
return a > b;
});Лямбда-функции - это анонимная функции, которые компилятором превращаются в классы с переопределенным оператором круглых скобок.
Объекты класса std::function так же могут быть использованы в качестве предиката.
Шаблон класса std::function это полиморфная обёртка функции общего назначения. Экземпляры класса std::function могут хранить, копировать, и ссылаться на любой вызываемый объект - функцию, лямбда-выражение, привязку выражения или другой объект-функцию.
constexpr bool greater()(const int lhs, const int rhs) const {
return rhs < lhs;
}
std::function<bool(const int, const int)> func;
std::vector<int> arr = {7, 5, 3, 1};
func = greater;
std::cout << std::boolalpha << is_sorted(arr.begin(), arr.end(), func);- Реализуйте слияние двух отсортированных массивов в один отсортированный. Алгоритм должен работать со сложностью по времени
O(N + M), гдеNиMдлины массивов.
template <class It, class Out, class Compare=std::less<>>
Out merge(It first1, It last1, It first2, It last2, Out out, Compare cmp=Compare{});- Реализуйте алгоритм сортировки слиянием.
template <class It, class Out, class Compare=std::less<>>
Out merge_sort(It first, It last, Out out, Compare cmp=Compare{});- Реализуйте алгоритм сортировки слиянием без использования дополнительной памяти
template <class It, class Compare=std::less<>>
void inplace_merge_sort(It first, It last, Compare cmp=Compare{});- Реализуйте пирамидальную сортировку. Описание алгоритма ищите в книге Кормена "Алгоритмы. Построение и анализ (3-е издание)", стр 179, глава 6.
template<class It, class Compare=std::less<>>
void heap_sort(It first, It last, Compare cmp=Compare{});- Реализуйте алгоритм быстрой сортировки.
template <class It, class Compare=std::less<>>
void quick_sort(It first, It last, Compare cmp=Compare{});- Реализуйте сортировку вставками.
template <class It, class Compare=std::less<>>
void insertion_sort(It first, It last, Compare cmp=Compare{});-
Реализуйте модульные тесты. Миниальное покрытие кода должно превышать 85%.
-
Сравните производительность всех реализованных алгоритмов сортировки (
merge_sort,inplace_merge_sort,heap_sort,quick_sort,insertion_sort,std::stable_sort,std::sort). Составьте отчет. Отчет должен включать в себя:- описание алгоритмов;
- блок схемы алгоритмов;
- зависимость времени работы алгоритмов от количества данных;
- вывод.