Введение в программирование 4. QuickSelect, детерминированный QuickSort, LSD

• Вспоминаем, что быстрая сортировка работает за O(n log n) и имеет математическое ожидание времени работы.  

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

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

• Ката порядковая статистика - число, которое после сортировки будет катым в массиве.  

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

• Пример: массив 1, 7, 5, 4, 3, 7, 3, 2, после сортировки - 1, 2, 3, 3, 4, 5, 7, 7.  

• Ката порядковая статистика - 4.  

• Квик-селект - алгоритм, который находит катую порядковую статистику за O(n).  

• Работает следующим образом: если длина массива равна 1, возвращает единственный элемент;  

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

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

• Алгоритм квик-селект работает в среднем за O(n).  

• Случайность обеспечивает равномерное разбиение массива на части.  

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

• Задача: найти катую порядковую статистику за O(n) без случайности.  

• Медиана - порядковая статистика с номером n/2.  

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

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

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

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

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

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

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

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

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

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

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

• Автор предлагает детерминированный алгоритм быстрой сортировки, основанный на детерминированном к-селекте.  

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

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

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

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

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

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

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

• Симптотика: O(n + k), где n - количество чисел, k - количество типов чисел.  

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

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

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

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

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

• Это позволяет определить позицию, куда нужно положить число, равное текущему элементу.  

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

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

• В видео обсуждается сортировка пар чисел, где каждая пара состоит из двух чисел, например, (x, y).  

• Сортировка пар чисел осуществляется с помощью стабильной сортировки по игрику, затем по иксу.  

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

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

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

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

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

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