#10 C++ Жемчужины STD - Сортировки
00:00 Введение в операции сортировки -Обсуждение операций сортировки в стандартной библиотеке алгоритмов. -Упоминание о семи различных операциях сортировки. 00:34 Сортировка по диапазону -Объяснение работы команды «Сортировать по диапазону». -Использование оператора «меньше, чем» для сравнения чисел. -Возможность указания собственной операции сравнения через третий параметр. 01:32 Сортировка не встроенных типов -Проблемы с использованием оператора «меньше, чем» для не встроенных типов. -Два варианта решения: изменение поведения std::sort или использование пользовательского функтора. -Пример создания пользовательского функтора через лямбду. 02:31 Стабильная сортировка -Объяснение разницы между стабильной и обычной сортировкой. -Гарантированное сохранение относительного порядка элементов при стабильной сортировке. -Эксперимент, показывающий разницу в результатах между стабильной и обычной сортировкой. 05:29 Производительность сортировок -Обсуждение производительности стабильной и обычной сортировки. -Временная сложность алгоритмов: n log n для стабильной сортировки и n log n при достаточном объёме памяти. -Тестирование скорости сортировки с помощью класса basic timer. 07:54 Сортировка с одинаковыми значениями -Пример сортировки элементов с одинаковыми целочисленными значениями. -Упорядочивание элементов по строкам при совпадении целочисленных значений. 09:03 Проверка состояния сортировки -Функция уже отсортирован для проверки состояния сортировки диапазона. -Функция сортируется до для определения точки сортировки диапазона. -Демонстрация использования этих функций на примере вектора. 10:08 Создание вектора и сортировка диапазона -Создание вектора на основе диапазона итератора. -Печать полного диапазона и отсортированного поддиапазона. -Пример сортировки диапазона с элементами 1, 3, 4. 11:05 Проблема сортировки большого контейнера Сортировка контейнера из 10 миллионов элементов неэффективна. Необходимость сортировки только первых 100 элементов. 11:16 Частичная сортировка -Объяснение работы частичной сортировки. -Параметры частичной сортировки: первый, последний и средний итераторы. -Пример сортировки первых трёх элементов вектора. 13:10 Преимущества частичной сортировки -Сравнение полной и частичной сортировки для 100 элементов. -Частичная сортировка выполняется в 50 раз быстрее. -Упоминание о копии частичной сортировки. 14:06 Алгоритм n-го элемента -Описание алгоритма n-го элемента. -Гарантированное положение n-го элемента в отсортированной последовательности. -Негарантированный порядок элементов до и после n-го элемента. 16:48 Заключение -Подчёркивание важности сортировки в вычислениях. -Упоминание операций бинарного поиска и работы с множествами. -Анонс следующего видео о бинарном поиске.
00:00 Введение в операции сортировки -Обсуждение операций сортировки в стандартной библиотеке алгоритмов. -Упоминание о семи различных операциях сортировки. 00:34 Сортировка по диапазону -Объяснение работы команды «Сортировать по диапазону». -Использование оператора «меньше, чем» для сравнения чисел. -Возможность указания собственной операции сравнения через третий параметр. 01:32 Сортировка не встроенных типов -Проблемы с использованием оператора «меньше, чем» для не встроенных типов. -Два варианта решения: изменение поведения std::sort или использование пользовательского функтора. -Пример создания пользовательского функтора через лямбду. 02:31 Стабильная сортировка -Объяснение разницы между стабильной и обычной сортировкой. -Гарантированное сохранение относительного порядка элементов при стабильной сортировке. -Эксперимент, показывающий разницу в результатах между стабильной и обычной сортировкой. 05:29 Производительность сортировок -Обсуждение производительности стабильной и обычной сортировки. -Временная сложность алгоритмов: n log n для стабильной сортировки и n log n при достаточном объёме памяти. -Тестирование скорости сортировки с помощью класса basic timer. 07:54 Сортировка с одинаковыми значениями -Пример сортировки элементов с одинаковыми целочисленными значениями. -Упорядочивание элементов по строкам при совпадении целочисленных значений. 09:03 Проверка состояния сортировки -Функция уже отсортирован для проверки состояния сортировки диапазона. -Функция сортируется до для определения точки сортировки диапазона. -Демонстрация использования этих функций на примере вектора. 10:08 Создание вектора и сортировка диапазона -Создание вектора на основе диапазона итератора. -Печать полного диапазона и отсортированного поддиапазона. -Пример сортировки диапазона с элементами 1, 3, 4. 11:05 Проблема сортировки большого контейнера Сортировка контейнера из 10 миллионов элементов неэффективна. Необходимость сортировки только первых 100 элементов. 11:16 Частичная сортировка -Объяснение работы частичной сортировки. -Параметры частичной сортировки: первый, последний и средний итераторы. -Пример сортировки первых трёх элементов вектора. 13:10 Преимущества частичной сортировки -Сравнение полной и частичной сортировки для 100 элементов. -Частичная сортировка выполняется в 50 раз быстрее. -Упоминание о копии частичной сортировки. 14:06 Алгоритм n-го элемента -Описание алгоритма n-го элемента. -Гарантированное положение n-го элемента в отсортированной последовательности. -Негарантированный порядок элементов до и после n-го элемента. 16:48 Заключение -Подчёркивание важности сортировки в вычислениях. -Упоминание операций бинарного поиска и работы с множествами. -Анонс следующего видео о бинарном поиске.