Алгоритмы и структуры данных/ базовый поток 4. Merge sort (Сортировка слиянием).

Презентация с лекции: 00:00:00 - интро 00:00:02 Сортировка слиянием • Рассматривается алгоритм сортировки слиянием, который работает быстрее квадратичных алгоритмов сортировки. • Идея алгоритма заключается в слиянии двух отсортированных массивов в один отсортированный массив. 00:02:57 Реализация алгоритма • Задается функция слияния, которая принимает два отсортированных массива и массив для записи результата. • Используется идея двух указателей для слияния массивов. • Время работы алгоритма пропорционально сумме размеров массивов. 00:10:52 Сортировка слиянием на примере • Рассматривается пример сортировки массива из восьми отсортированных массивов размера один. • Массивы сливаются попарно, и на каждом шаге получается два массива размера два, которые сливаются друг с другом. • В итоге получается два массива размера четыре, которые сливаются в один отсортированный массив. 00:14:16 Сортировка массива • Автор объясняет алгоритм сортировки, который работает за время, меньшее, чем квадратичное. • Алгоритм состоит из нескольких шагов, каждый из которых сливает два массива размера один. 00:20:25 Реализация алгоритма • Автор реализует алгоритм на языке программирования, используя массив для хранения временных значений. • После каждого шага сортировки, элементы из массива “c“ переносятся в исходный массив “a“. 00:24:15 Пояснение работы алгоритма • Автор объясняет, почему элементы переносятся из массива “c“ в массив “a“ и как происходит слияние массивов. • Алгоритм работает за время, меньшее, чем двоичный логарифм от размера массива. 00:29:44 Сортировка слиянием • Рассматривается пример сортировки слиянием для массива с элементами 4, 2, 1, 3, 5, 6, 7, 8, 9, 10. • Вводится понятие “жи“ - индекс элемента, который нужно вставить в массив. 00:34:39 Стабильность сортировки слиянием • Сортировка слиянием является стабильной, то есть сохраняет порядок одинаковых элементов. • Пример: сортировка массива 1, 1, 2, 3, 1, 2. 00:41:05 Модификация сортировки слиянием без дополнительной памяти • Задача: придумать алгоритм, который не требует дополнительной памяти для слияния массивов. • Ограничение: сливаемые последовательности должны быть расположены строго друг за другом. 00:42:36 Примеры простых случаев • Массивы с отсортированными элементами легко сливаются друг с другом. • Массивы с разными размерами, но элементы расположены последовательно друг за другом, также легко сливаются. • Если размер одного из массивов равен нулю, можно завершить работу. 00:44:21 Сортировка слиянием • Рассматривается сортировка слиянием, которая является стабильной и использует дополнительную память. • Обсуждается, почему сортировка слиянием является стабильной. 00:55:23 Задача с двумя массивами • Задача: поменять местами два куска массива, не используя дополнительную память. • Решение: использовать реверс для каждого куска и поменять их местами. 00:57:42 Задача с массивами разных размеров • Задача: выровнять два массива разных размеров, не используя дополнительную память. • Решение: использовать реверс для каждого куска и поменять их местами. 01:00:00 Сортировка массива • В видео обсуждается сортировка массива, состоящего из двух отсортированных частей. • Задача состоит в том, чтобы объединить эти две части в один отсортированный массив. 01:01:00 Рекурсия и время работы • Автор объясняет, что сортировка может быть выполнена с помощью рекурсии. • Доказывается, что время работы алгоритма удовлетворяет рекурентному соотношению. 01:12:12 Анализ времени работы • Автор анализирует время работы алгоритма, используя дерево рекурсии. • В результате получается, что время работы удовлетворяет линейному соотношению. 01:16:12 Заключение • В заключении автор обсуждает, что если массив б больше, чем массив а, то алгоритм также работает. 01:17:25 Обсуждение алгоритмов • В видео обсуждается алгоритм поиска центрального элемента в массиве. • Предлагается поменять местами массивы a и b, чтобы упростить код. 01:18:00 Обратная ситуация • Обсуждается обратная ситуация, когда нужно найти элемент в массиве b, зная центральный элемент в массиве a. • Предлагается подумать над вопросом: “Какой элемент нужно искать?“ 01:19:00 Заключение • Видео заканчивается, автор благодарит зрителей за просмотр и предлагает подумать над упражнением. Дата лекции: Лектор: Ибрагимов Булат Ленарович Оператор: Долеско А. Монтажёр: Самсонов В. Плейлист: