Сортировки

• Обсуждение различных алгоритмов сортировки, их эффективности и использования в задачах.  

• Обсуждение ручной проверки задач на сортировку.  

• Описание алгоритма сортировки пузырьком, который сравнивает элементы массива и меняет их местами, если они не в правильном порядке.  

• Обсуждение сложности алгоритма и его улучшения.  

• Описание алгоритма сортировки выбором, который выбирает минимальный элемент из массива и меняет его местами с первым элементом.  

• Обсуждение сложности алгоритма и его аналогов для выбора максимального элемента.  

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

• Обсуждение сложности алгоритма и его сходства с сортировкой пузырьком.  

• В лекции обсуждаются квадратичные сортировки, которые могут быть использованы для сортировки больших массивов.  

• Обсуждаются идеи о том, как можно хранить инварианты и как добавлять новые элементы в массив, чтобы сохранить сортировку префикса.  

• В лекции обсуждается формализм синтоики, который используется для оценки времени работы алгоритма.  

• Объясняется, что синтоику обычно считают от максимального числа в массиве, а не от случайных чисел.  

• Приводится пример алгоритма, который работает за корень из числа, и объясняется, почему он работает.  

• В лекции описывается алгоритм сортировки по счету, который состоит из двух этапов: подсчет и вывод.  

• Обсуждается, как создать массив с количеством вхождений числа в исходный массив.  

• Объясняется, почему последний индекс массива должен быть на единицу больше, чем максимальное число в исходном массиве.  

• В видео объясняется, как использовать массив подсчета для подсчета количества вхождений числа в массив.  

• Массив подсчета содержит количество вхождений каждого числа в исходный массив.  

• Объясняется, как использовать массив подсчета для сортировки массива.  

• В видео демонстрируется, как вывести отсортированный массив, используя массив подсчета.  

• Обсуждается, как определить сложность алгоритма, используя нотацию Big O.  

• В видео подчеркивается, что сложность алгоритма равна O(n + m), где n - количество чисел в массиве, а m - максимальное число в массиве.  

• В видео упоминается, что массив подсчета может заменить набор для некоторых задач.  

• Также упоминается, что цифровая сортировка, или радиксная сортировка, является одной из самых быстрых сортировок в мире.  

• Обсуждение операции деления и остатка для получения первой и второй цифры числа.  

• Объяснение, что операция добавления нулей к числу происходит автоматически.  

• Идея сортировки чисел по последней цифре и сохранение порядка чисел в итоговом массиве.  

• Объяснение понятия "стабильная сортировка" и его применение в данном случае.  

• Определение массива радикс итан для чисел, заканчивающихся на цифру 10.  

• Создание массива радикс итан с числами, заканчивающимися на цифру 1.  

• Проход по всем возможным цифрам от 0 до 9 и запись чисел в массив.  

• Перемещение чисел из массива радикс итан в исходный массив.  

• Создается массив чисел и сортируется по последней цифре.  

• Объясняется, как сортировка по предпоследней цифре сохраняет порядок сортировки по последней цифре.  

• Сортировка по предпоследней цифре выполняется стабильно, сохраняя порядок сортировки по последней цифре.  

• Цифры сортируются по возрастанию, сохраняя порядок чисел с одинаковой предпоследней цифрой.  

• Сортировка выполняется по цифре с конца, начиная с единицы и умножая на 10 в степени.  

• Сортировка выполняется стабильно, сохраняя порядок сортировки по предпоследней цифре.  

• Обсуждается оптимизация алгоритма сортировки по цифре с конца для различных систем счисления.  

• Обсуждаются сложности и подводные камни при сортировке на маленьких тестах.  

• Рассматривается функция, которая будет ключевой в сортировке.  

• Функция должна работать только с отсортированными массивами, возвращать массив цен.  

• Задача основана на алгоритме двух показателей.  

• Вводятся два указателя на массивы a и b.  

• Поддерживаются условия: все числа из a, которые стоят раньше текущего индекса уже в c, и все числа из b, которые стоят раньше текущего индекса уже в c.  

• Выбирается между a и b, добавляется в ответ и сдвигает индекс.  

• Обсуждается проблема выхода за пределы массива при добавлении чисел.  

• Рассматривается второй вариант реализации, когда при выходе за пределы массива добавляются числа из другого массива.  

• Обсуждаются условия выхода из цикла и добавление оставшихся чисел.  

• Реализация алгоритма для массивов a и b.  

• Обсуждение алгоритма сортировки, основанного на слиянии.  

• Рекурсивное решение задачи, с терминальным случаем, когда массив имеет длину один или меньше.  

• Разделение массива на две части, сортировка каждой части и объединение результатов с помощью функции слияния.  

• Визуальное представление работы алгоритма: разбиение массива на маленькие кусочки, слияние с помощью функции слияния.  

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

• Рекомендация использовать векторы и индексы для реализации алгоритма.  

• Обсуждение оптимизации и дополнительных деталей на следующей лекции.  

• Видео объясняет алгоритм сортировки массива, сравнивая каждый элемент с остальными и определяя его позицию в массиве.  

• В худшем случае, алгоритм работает медленно, сравнивая каждый элемент с каждым другим элементом, что приводит к квадратичному времени выполнения.  

• В среднем случае, алгоритм выбирает элемент, который находится ближе к центру массива, что приводит к логарифмическому времени выполнения.  

• В видео обсуждается сложность алгоритма, его константы и время выполнения.  

• Алгоритм может быть использован для сортировки массивов, но его сложность может быть улучшена.  

• Видео приводит примеры массивов, для которых алгоритм работает за квадратичное время.  

• Обсуждается, как алгоритм работает, и как он может быть улучшен для более быстрого выполнения.  

• Задача: упорядочить камешки по их весу, используя функцию сравнения.  

• Камешки могут быть различных весов, и их количество может быть большим.  

• Глубина дерева сравнений будет логарифмом от количества камешков.  

• Задача: восстановить перестановку камешков, зная только их веса.  

• Используем сравнение камешков для восстановления перестановки.  

• В лучшем случае, глубина дерева сравнений будет равна половине от количества камешков.  

• Задача: посчитать количество инверсий в перестановке.  

• Инверсия - это пара номеров, где элемент слева больше элемента справа.  

• Используем алгоритм Мержа для подсчета количества инверсий.  

• В видео объясняется, как считать количество инверсий в массиве, используя рекурсию и два курсивных массива.  

• Затем происходит слияние двух массивов и подсчет количества инверсий.  

• Объясняется, как случайным образом выбрать элемент из массива и определить его правильное место в отсортированном списке.  

• Затем создается новый массив, в который помещается выбранный элемент, а остальные элементы сортируются отдельно.  

• В итоге получается отсортированный массив.