Тренировки по алгоритмам 4.0. Лекция 1: Сортировки: быстрая, слиянием и поразрядная

• Михаил Густокашин представляет себя и свою роль преподавателя алгоритмов и структур данных.  

• Начинается четвертый сезон тренировок по алгоритмам от Яндекса.  

• Тема первой лекции - сортировки.  

• Лекция будет плотной и рассматривает общие идеи сортировок.  

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

• Лекция состоит из пяти частей.  

• Начнем с быстрой сортировки, затем рассмотрим сортировку слиянием.  

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

• Завершим лекцию разрядной сортировкой.  

• Быстрая сортировка включает операцию разбиения массива на две части.  

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

• Массив разбивается на две части: числа меньше опорного элемента в левой части, больше - в правой.  

• Массив делится на две части.  

• Элементы меньше икс сортируются в левой части.  

• Элементы больше икс сортируются в правой части.  

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

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

• Вопросы можно задавать в трансляции.  

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

• Массив делится на две части и сортируется рекурсивно.  

• Индексы для сортировки частей массива.  

• Идея проста, но реализация сложна.  

• Быстрая сортировка была придумана давно.  

• Схема Хоара используется для партишина.  

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

• Указатели могут показывать на один элемент.  

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

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

• Массив делится на три части: меньше икс, равные иксу, больше икса.  

• Указатели н, е и г показывают на соответствующие части.  

• Новый элемент обрабатывается и добавляется в нужную группу.  

• Если элемент меньше икс, он добавляется в группу меньших элементов.  

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

• Указатели сдвигаются для поддержания корректной структуры массива.  

• Партишин позволяет писать более понятный код.  

• Он решает проблему отсутствия элементов меньше икса.  

• Группа элементов, равных иксу, не будет пустой.  

• Сложность алгоритма равна n log n, если икс делит массив пополам.  

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

• В худшем случае сложность может стать n^2 при выборе плохого элемента.  

• Порядковая статистика - это элемент на k-м месте в отсортированном массиве.  

• Медиана - это порядковая статистика, находящаяся в середине массива.  

• Для анализа данных важно знать несколько точек на графике зарплат.  

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

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

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

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

• Правее будут элементы больше или равные окаты, левее - меньше или равные.  

• Можно найти k самых больших или k самых маленьких элементов массива за линейное время.  

• Сортировка слиянием естественна для человека.  

• Представьте, что числа на листочках - это гири, которые нужно перекладывать.  

• Основная задача - слияние двух упорядоченных последовательностей в одну.  

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

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

• Процесс продолжается до тех пор, пока одна из последовательностей не закончится.  

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

• Операция слияния занимает линейное время, но требует выделения памяти.  

• Существуют алгоритмы без выделения памяти, но они менее удобны.  

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

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

• Разбиение массива на две половины и сортировка каждой половины.  

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

• Пример рекурсивного процесса с разбиением и сортировкой.  

• Пример рекурсии с разбиением и сортировкой правой половины.  

• Мердж последовательностей для объединения отсортированных частей.  

• Пример с не степенью двойки для разбиения.  

• Сложность алгоритма: O(n log n).  

• На каждом слое выполняется O(n) действий.  

• Количество слоев равно логарифму длины массива.  

• Необходимость дополнительного массива для сортировки слиянием.  

• Использование кольцевого буфера для эффективного управления памятью.  

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

• Вопрос о возможности лучшей сортировки, чем O(n log n).  

• Определение сортировки как перестановки элементов.  

• Количество возможных перестановок равно n!  

• Количество вопросов для определения перестановки равно log n!.  

• Все рассмотренные сортировки задают вопросы с ответами "да" или "нет".  

• Необходимость log n! вопросов для определения перестановки.  

• Логарифм n! равен сумме логарифмов чисел от 1 до n.  

• Цель: доказать, что сумма логарифмов равна n log n.  

• Доказательство невозможности лучшей сортировки, чем O(n log n).  

• Доказательство строгого равенства и асимптотической сложности.  

• Замена слагаемых на логарифмы для упрощения суммы.  

• Доказательство, что сумма не больше n log n.  

• Отбрасывание маленьких логарифмов и замена их на большие.  

• Оценка суммы как n/2 log n/2.  

• Получение оценки асимптотической сложности алгоритма.  

• Различие между устойчивой и неустойчивой сортировками.  

• Пример с физкультурой: устойчивая сортировка сохраняет порядок одинаковых элементов.  

• Неустойчивая сортировка может менять порядок одинаковых элементов.  

• Устойчивость важна при сортировке структур с полями, не участвующими в сравнении.  

• Пример с сортировкой по росту и имени.  

• Устойчивость можно добавить к любому алгоритму, добавив ключ сравнения.  

• Квадратичные сортировки можно сделать устойчивыми.  

• Пример с пузырьковой сортировкой: не менять одинаковые элементы рядом.  

• Устойчивость важна для всех квадратичных сортировок.  

• История поразрядной сортировки, изобретенной в XIX веке.  

• Применение на механических машинах до появления компьютеров.  

• Пример сортировки перфокарт с помощью поразрядной сортировки.  

• Сортировка начинается с наименее значимых единиц и переходит к разряду десятков.  

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

• Пример: числа 720 и 329 отсортированы по разряду единиц и десятков, так как 0 меньше 9.  

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

• Процесс продолжается до разряда сотен, обеспечивая полную сортировку чисел.  

• Ключевая идея: использование устойчивого алгоритма сортировки по одному разряду.  

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

• Подсчет количества вхождений каждого элемента в последовательности.  

• Пример: школьные оценки от 1 до 5, где количество вхождений каждого числа увеличивается при встрече.  

• Пример с плитками для ванной: плитки разных цветов укладываются в определенном порядке.  

• Плитки каждого цвета укладываются на заранее подготовленные места.  

• Массив post помогает определить, с какого места начинать укладку плиток каждого цвета.  

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

• Пример: плитки первого цвета начинаются с позиции 0, второго цвета с позиции 3 и так далее.  

• Это позволяет избежать перекладывания плиток и обеспечивает устойчивую сортировку.  

• Сортировка пар по номеру, а не по алфавиту.  

• Пример: 1 ставится на позицию 0, 3 на позицию 5, 2 на позицию 3.  

• Указатель указывает на следующую позицию для каждой новой плитки.  

• Пример: 3 ставится на позицию 6, 5 на позицию 10, 4 на позицию 11.  

• Указатель увеличивается на единицу для каждой новой плитки.  

• Ошибки в нумерации исправляются, но идея остается той же.  

• Заранее выделяется количество мест для значений.  

• Устойчивая сортировка: элементы с одинаковым ключом остаются в том же порядке.  

• Требует O(n + k) памяти, где k - количество возможных значений.  

• Сортировка по десяти разрядам.  

• Быстрая сортировка подсчета работает за O(n + k).  

• Подходит для небольших наборов данных.  

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

• Поразрядная сортировка может быть быстрее для больших данных.  

• Экономия времени может быть значимой для больших объемов данных.  

• Квадратичные сортировки потребляют O(n) памяти.  

• Быстрая сортировка потребляет O(log n) памяти.  

• Пирамидальная сортировка потребляет O(1) памяти, но неустойчива и медленна.  

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

• Устойчивая сортировка подсчета и поразрядная сортировка требуют O(n + k) памяти.  

• Обзор различных сортировок и их характеристик.  

• Быстрая сортировка работает за O(n log n) и имеет маленькую константу.  

• Тим-сорт улучшает свою производительность на частично отсортированных массивах.  

• Разные партишины могут по-разному вести себя на отсортированных массивах.  

• Пирамидальная сортировка потребляет O(n) памяти и работает без рекурсии.  

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

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

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

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

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

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

• Порядковая статистика определяет элемент на k-м месте после сортировки массива.  

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

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

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

• Порядковая статистика строится на отсортированном массиве.  

• Цель сортировки - поставить каждый элемент на свое место.  

• Хипсорт требует единицу памяти, так как кучу можно строить на том же массиве.  

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

• Если все поля структуры являются ключами сравнения, можно просто перезаписать старые числа новыми.  

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

• Первый тип подвоха - все одинаковые числа.  

• Второй способ избежать подвоха - брать случайное число между элементами.  

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

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

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

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

• Лекция была объемной, но полезной.  

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

• Рекомендуется писать код вручную для лучшего понимания и подготовки к финальному контесту.